Article

Optimal Sherali-Adams Gaps from Pairwise Independence

Authors:

Konstantinos Georgiou,

Madhur TulsianiAuthors Info & Claims

APPROX '09 / RANDOM '09: Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Pages 125 - 139

https://doi.org/10.1007/978-3-642-03685-9_10

Published: 21 August 2009 Publication History

Abstract

This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(<em>P</em> )). We show that if the set of assignments accepted by <em>P</em> contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on <em>n</em> variables cannot be approximated better than the trivial (random) approximation, even using ***(<em>n</em> ) levels of the Sherali-Adams LP hierarchy.

It was recently shown [3] that under the Unique Game Conjecture, CSPs with predicates with this condition cannot be approximated better than the trivial approximation. Our results can be viewed as an unconditional analogue of this result in the restricted computational model defined by the Sherali-Adams hierarchy. We also introduce a new generalization of techniques to define consistent "local distributions" over partial assignments to variables in the problem, which is often the crux of proving lower bounds for such hierarchies.

References

[1]

Alekhnovich, M., Arora, S., Tourlakis, I.: Towards strong nonapproximability results in the Lovász-Schrijver hierarchy. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, ACM Press, New York (2005).

Digital Library

[2]

Arora, S., Bollobás, B., Lovász, L., Tourlakis, I.: Proving integrality gaps without knowing the linear program. Theory of Computing 2(2), 19-51 (2006).

[3]

Austrin, P., Mossel, E.: Approximation resistant predicates from pairwise independence. In: IEEE Conference on Computational Complexity, pp. 249-258. IEEE Computer Society Press, Los Alamitos (2008).

Digital Library

[4]

Bateni, M.H., Charikar, M., Guruswami, V.: MaxMin allocation via degree lower-bounded arborescences. In: STOC 2009. ACM Press, New York (2009).

Digital Library

[5]

Buresh-Oppenheim, J., Galesi, N., Hoory, S., Magen, A., Pitassi, T.: Rank bounds and integrality gaps for cutting planes procedures. Theory of Computing 2(4), 65-90 (2006).

[6]

Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: STOC 2009. ACM Press, New York (2009).

Digital Library

[7]

Chlamtac, E.: Approximation algorithms using hierarchies of semidefinite programming relaxations. In: FOCS: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 691-701 (2007).

Digital Library

[8]

Chlamtac, E., Singh, G.: Improved approximation guarantees through higher levels of SDP hierarchies. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol. 5171, pp. 49-62. Springer, Heidelberg (2008).

Digital Library

[9]

Engebretsen, L., Holmerin, J.: More efficient queries in pCPs for NP and improved approximation hardness of maximum CSP. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 194-205. Springer, Heidelberg (2005).

Digital Library

[10]

Feige, U., Krauthgamer, R.: The probable value of the Lovász-Schrijver relaxations for maximum independent set. SICOMP: SIAM Journal on Computing 32(2), 345- 370 (2003).

Digital Library

[11]

de la Vega, W.F., Kenyon-Mathieu, C.: Linear programming relaxations of maxcut. In: SODA 2007: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 53-61. Society for Industrial and Applied Mathematics (2007).

Digital Library

[12]

Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovász-Schrijver hierarchy. In: Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, pp. 702-712 (2007).

Digital Library

[13]

Guruswami, V., Raghavendra, P.: Constraint satisfaction over a non-boolean domain: Approximation algorithms and unique-games hardness. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol. 5171, pp. 77-90. Springer, Heidelberg (2008).

Digital Library

[14]

Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 293-303. Springer, Heidelberg (2001).

Digital Library

[15]

Laurent, M.: A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28(3), 470-496 (2003).

Digital Library

[16]

Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization 1(2), 166-190 (1991).

Digital Library

[17]

Magen, A., Moharrami, M.: Sherali-Adams based polynomial approximation schemes for NP-hard problems on planar and minor-free graphs (manuscript) (2008).

[18]

Mathieu, C., Sinclair, A.: Sherali-Adams relaxations of the matching polytope. In: STOC 2009. ACM Press, New York (2009).

Digital Library

[19]

Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000, Portland, Oregon, May 21-23, 2000, pp. 191-199. ACM Press, New York (2000).

Digital Library

[20]

Samorodnitsky, A., Trevisan, L.: Gowers uniformity, influence of variables, and PCPs. In: STOC 2006, pp. 11-20 (2006).

Digital Library

[21]

Schoenebeck, G.: Linear level lasserre lower bounds for certain k-CSPs. In: FOCS, pp. 593-602. IEEE Computer Society Press, Los Alamitos (2008).

Digital Library

[22]

Schoenebeck, G., Trevisan, L., Tulsiani, M.: A linear round lower bound for Lovász-Schrijver SDP relaxations of vertex cover. In: IEEE Conference on Computational Complexity, pp. 205-216. IEEE Computer Society Press, Los Alamitos (2007).

Digital Library

[23]

Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lovász-Schrijver LP relaxations of vertex cover and max cut. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007. ACM Press, New York (2007).

Digital Library

[24]

Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411-430 (1990).

Digital Library

[25]

Tourlakis, I.: Towards optimal integrality gaps for hypergraph vertex cover in the Lovász-Schrijver hierarchy. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol. 3624, pp. 233-244. Springer, Heidelberg (2005).

Digital Library

[26]

Tourlakis, I.: New lower bounds for vertex cover in the Lovász-Schrijver hierarchy. In: Proceedings of the 21st IEEE Conference on Computational Complexity, pp. 170-182. IEEE Computer Society Press, Los Alamitos (2006).

Digital Library

[27]

Tulsiani, M.: CSP gaps and reductions in the Lasserre hierarchy. In: STOC 2009. ACM Press, New York (2009).

Digital Library

Cited By

Sofronova ASokolov D(2021)Branching programs with bounded repetitions and flow formulasProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.17Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.17
Ghazi BLee EIndyk P(2015)LP/SDP hierarchy lower bounds for decoding random LDPC codesProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722217(1326-1342)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722217
Fiorini SMassar SPokutta STiwary Hde Wolf R(2015)Exponential Lower Bounds for Polytopes in Combinatorial OptimizationJournal of the ACM10.1145/271630762:2(1-23)Online publication date: 6-May-2015
https://dl.acm.org/doi/10.1145/2716307
Show More Cited By

Recommendations

Extending SDP integrality gaps to sherali-adams with applications to quadratic programming and maxcutgain
IPCO'10: Proceedings of the 14th international conference on Integer Programming and Combinatorial Optimization

We show how under certain conditions one can extend constructions of integrality gaps for semidefinite relaxations into ones that hold for stronger systems: those SDP to which the so-called k-level constraints of the Sherali-Adams hierarchy are added. ...
Integrality gaps for Sherali-Adams relaxations
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

We prove strong lower bounds on integrality gaps of Sherali-Adams relaxations for MAX CUT, Vertex Cover, Sparsest Cut and other problems. Our constructions show gaps for Sherali-Adams relaxations that survive n^δ rounds of lift and project. For MAX CUT ...
Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer science

We consider approximation schemes for the maximum constraint satisfaction problems and the maximum assignment problems. Though they are NP-Hard in general, if the instance is "dense" or "locally dense", then they are known to have approximation schemes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

APPROX '09 / RANDOM '09: Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

August 2009

737 pages

ISBN:9783642036842

Editors:
Irit Dinur
Dept. of Applied Math and Computer Science, The Weizmann Institute of Science, Rehovot, Israel 76100
,
Klaus Jansen
Institute for Computer Science and Applied Mathematics, University of Kiel, Kiel, Germany 24098
,
Joseph Naor
Technion, Computer Science Department, Haifa, Israel 32000
,
José Rolim
University of Geneva, Centre Universitaire d'Informatique, Carouge, Switzerland 1227

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 August 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sofronova ASokolov D(2021)Branching programs with bounded repetitions and flow formulasProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.17Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.17
Ghazi BLee EIndyk P(2015)LP/SDP hierarchy lower bounds for decoding random LDPC codesProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722217(1326-1342)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722217
Fiorini SMassar SPokutta STiwary Hde Wolf R(2015)Exponential Lower Bounds for Polytopes in Combinatorial OptimizationJournal of the ACM10.1145/271630762:2(1-23)Online publication date: 6-May-2015
https://dl.acm.org/doi/10.1145/2716307
Fiorini SPashkovich K(2015)Uncapacitated flow-based extended formulationsMathematical Programming: Series A and B10.1007/s10107-015-0862-9153:1(117-131)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/s10107-015-0862-9
Bhaskara ACharikar MVijayaraghavan AGuruswami VZhou Y(2012)Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraphProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095150(388-405)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095150
Fiorini SMassar SPokutta STiwary Hde Wolf RKarloff HPitassi T(2012)Linear vs. semidefinite extended formulationsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2213988(95-106)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2213988
Karlin AMathieu CNguyen C(2011)Integrality gaps of linear and semi-definite programming relaxations for KnapsackProceedings of the 15th international conference on Integer programming and combinatoral optimization10.5555/2018158.2018182(301-314)Online publication date: 15-Jun-2011
https://dl.acm.org/doi/10.5555/2018158.2018182
Benabbas SMagen A(2010)Extending SDP integrality gaps to sherali-adams with applications to quadratic programming and maxcutgainProceedings of the 14th international conference on Integer Programming and Combinatorial Optimization10.1007/978-3-642-13036-6_23(299-312)Online publication date: 9-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-13036-6_23
Austrin PBenabbas SMagen A(2010)On quadratic threshold CSPsProceedings of the 9th Latin American conference on Theoretical Informatics10.1007/978-3-642-12200-2_30(332-343)Online publication date: 19-Apr-2010
https://dl.acm.org/doi/10.1007/978-3-642-12200-2_30

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents