2026-07-21T19:38:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5738 2024-03-06T10:36:58Z ddc:004 open_access

Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse Fotakis, Dimitris Lampis, Michael Paschos, Vangelis Th. polynomial and subexponential approximation sampling randomized rounding It has long been known, since the classical work of (Arora, Karger, Karpinski, JCSS'99), that MAX-CUT admits a PTAS on dense graphs, and more generally, MAX-k-CSP admits a PTAS on "dense" instances with Omega(n^k) constraints. In this paper we extend and generalize their exhaustive sampling approach, presenting a framework for (1-epsilon)-approximating any MAX-k-CSP problem in sub-exponential time while significantly relaxing the denseness requirement on the input instance. Specifically, we prove that for any constants delta in (0, 1] and epsilon > 0, we can approximate MAX-k-CSP problems with Omega(n^{k-1+delta}) constraints within a factor of (1-epsilon) in time 2^{O(n^{1-delta}*ln(n) / epsilon^3)}. The framework is quite general and includes classical optimization problems, such as MAX-CUT, MAX-DICUT, MAX-k-SAT, and (with a slight extension) k-DENSEST SUBGRAPH, as special cases. For MAX-CUT in particular (where k=2), it gives an approximation scheme that runs in time sub-exponential in n even for "almost-sparse" instances (graphs with n^{1+delta} edges). We prove that our results are essentially best possible, assuming the ETH. First, the density requirement cannot be relaxed further: there exists a constant r < 1 such that for all delta > 0, MAX-k-SAT instances with O(n^{k-1}) clauses cannot be approximated within a ratio better than r in time 2^{O(n^{1-delta})}. Second, the running time of our algorithm is almost tight for all densities. Even for MAX-CUT there exists r<1 such that for all delta' > delta >0, MAX-CUT instances with n^{1+delta} edges cannot be approximated within a ratio better than r in time 2^{n^{1-delta'}}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dimitris Fotakis and Michael Lampis and Vangelis Th. Paschos 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.37 urn:nbn:de:0030-drops-57388 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.37 eng https://creativecommons.org/licenses/by/3.0/legalcode