Zobrazeno 1 - 10
of 45
pro vyhledávání: '"Çivril, Ali"'
Autor:
Çivril, Ali
We provide algorithms for the minimum 2-edge-connected spanning subgraph problem and the minimum 2-vertex-connected spanning subgraph problem with approximation ratio $\frac{9}{7}$. This improves upon a recent algorithm with ratio slightly smaller th
Externí odkaz:
http://arxiv.org/abs/2407.10526
Autor:
Çivril, Ali
We describe a $\frac{3}{2}$-approximation algorithm for the Forest Augmentation Problem (\textsf{FAP}), which is a special case of the Weighted 2-Edge-Connected Spanning Subgraph Problem (\textsf{Weighted 2-ECSS}). This significantly improves upon th
Externí odkaz:
http://arxiv.org/abs/2407.11101
Autor:
Çivril, Ali
We provide a new approach for establishing hardness of approximation results, based on the theory recently introduced by the author. It allows one to directly show that approximating a problem beyond a certain threshold requires super-polynomial time
Externí odkaz:
http://arxiv.org/abs/2305.05676
Autor:
Çivril, Ali
We show that there exist infinitely many $n \in \mathbb{Z}^+$ such that for any constant $\epsilon > 0$, any deterministic algorithm to solve $k$-\textsf{SAT} for $k \geq 3$ must perform at least $(2^{k-\frac{3}{2}-\epsilon})^{\frac{n}{k+1}}$ operati
Externí odkaz:
http://arxiv.org/abs/2305.05415
Autor:
Çivril, Ali
We describe a $\frac{4}{3}$-approximation algorithm for the traveling salesman problem in which the distances between points are induced by graph-theoretical distances in an unweighted graph. The algorithm is based on finding a minimum cost perfect m
Externí odkaz:
http://arxiv.org/abs/2305.05411
Autor:
Çivril, Ali
We provide algorithms for the minimum 2-edge-connected spanning subgraph problem and the minimum 2-vertex-connected spanning subgraph problem with approximation ratio both $\frac{4}{3}$. Using a common theme, the algorithms and their analyses are ver
Externí odkaz:
http://arxiv.org/abs/2305.05398
Autor:
Çivril, Ali
We show that the problem of determining the feasibility of quadratic systems over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$ requires exponential time. This separates P and NP over these fields/rings in the BCSS model of computation.
Comment:
Comment:
Externí odkaz:
http://arxiv.org/abs/2107.07387
Autor:
Çivril, Ali
We lay the foundations of a new theory for algorithms and computational complexity by parameterizing the instances of a computational problem as a moduli scheme. Considering the geometry of the scheme associated to 3-SAT, we separate P and NP. In par
Externí odkaz:
http://arxiv.org/abs/2107.07386
Autor:
Çivril, Ali
Publikováno v:
Journal of Combinatorial Optimization, 38(4):1196-1212, 2019
The classical algorithm of Agrawal, Klein and Ravi [SIAM J. Comput., 24 (1995), pp. 440-456], stated in the setting of the primal-dual schema by Goemans and Williamson [SIAM J. Comput., 24 (1995), pp. 296-317] uses the undirected cut relaxation for t
Externí odkaz:
http://arxiv.org/abs/1911.07234
Autor:
Çivril, Ali
We present a new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem. Its approximation ratio is $\frac{4}{3}$, which matches the current best ratio. The approximation ratio of the algorithm is $\frac{6}{5}$ on subcubic
Externí odkaz:
http://arxiv.org/abs/1911.07232