Sub-exponential approximation schemes for CSPs: from dense to almost sparse

DOI10.4230/LIPICS.STACS.2016.37zbMATH Open1388.68307arXiv1507.04391OpenAlexW2962705766MaRDI QIDQ4601889FDOQ4601889

Vangelis Th. Paschos, Dimitris Fotakis, Michael Lampis

Publication date: 24 January 2018

Abstract: It has long been known, since the classical work of (Arora, Karger, Karpinski, JCSS~99), that MC admits a PTAS on dense graphs, and more generally, kCSP 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-eps)$-approximating any kCSP problem in emph{sub-exponential} time while significantly relaxing the denseness requirement on the input instance. Specifically, we prove that for any constants $deltain(0,1]$ and $eps>0$, we can approximate kCSP problems with $Omega(n^{k-1+delta})$ constraints within a factor of $(1-eps)$ in time $2^{O(n^{1-delta}lnn/ep{s}^3)}$. The framework is quite general and includes classical optimization problems, such as MC, {sc Max}-DICUT, kSAT, and (with a slight extension) $k$-{sc Densest Subgraph}, as special cases. For MC 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$, kSAT 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 emph{for all densities}. Even for MC there exists $r<1$ such that for all $delt{a}^{\prime }>delta>0$, MC instances with $n^{1+delta}$ edges cannot be approximated within a ratio better than $r$ in time $2^{n^{1-delt{a}^{\prime }}}$.

Full work available at URL: https://arxiv.org/abs/1507.04391

Recommendations

• Approximating dense MAX 2-CSPs
• Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
• scientific article; zbMATH DE number 1263204
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Sparsification and subexponential approximation

zbMATH Keywords

samplingrandomized roundingpolynomial and subexponential approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cited In (3)

• Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
• In)approximability of Maximum Minimal FVS
• (In)approximability of maximum minimal FVS

This page was built for publication: Sub-exponential approximation schemes for CSPs: from dense to almost sparse

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601889)