2 citations · 6 across the 15 of their papers we have counts for
4 papers · 1 filter
Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation
Ali Çivril
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 approximati…
Scheme-Theoretic Approach to Computational Complexity. III. SETH
Ali Çivril
We show that there exist infinitely many such that for any constant , any deterministic algorithm to solve -\textsf{SAT} for must perform a…
4/3-Approximation of Graphic TSP
Ali Çivril
We describe a -approximation algorithm for the traveling salesman problem in which the distances between points are induced by graph-theoretical distances in an unweig…
A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
Ali Çivril
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…