Document Open Access Logo

Guruswami-Sinop Rounding without Higher Level Lasserre

Authors Amit Deshpande, Rakesh Venkat

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.105.pdf
  • Filesize: 472 kB
  • 10 pages

Document Identifiers

Author Details

Amit Deshpande
Rakesh Venkat

Cite AsGet BibTex

Amit Deshpande and Rakesh Venkat. Guruswami-Sinop Rounding without Higher Level Lasserre. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 105-114, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.105

Abstract

Guruswami and Sinop give a O(1/delta) approximation guarantee for the non-uniform Sparsest Cut problem by solving O(r)-level Lasserre semidefinite constraints, provided that the generalized eigenvalues of the Laplacians of the cost and demand graphs satisfy a certain spectral condition, namely, the (r+1)-th generalized eigenvalue is at least OPT/(1-delta). Their key idea is a rounding technique that first maps a vector-valued solution to [0,1] using appropriately scaled projections onto Lasserre vectors. In this paper, we show that similar projections and analysis can be obtained using only l_2^2 triangle inequality constraints. This results in a O(r/delta^2) approximation guarantee for the non-uniform Sparsest Cut problem by adding only l_2^2 triangle inequality constraints to the usual semidefinite program, provided that the same spectral condition, the (r+1)-th generalized eigenvalue is at least OPT/(1-delta), holds.
Keywords
  • Sparsest Cut
  • Lasserre Hierarchy
  • Metric embeddings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Alon and V. D. Milman. λ₁, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38(1):73-88, 1985. Google Scholar
  2. Sanjeev Arora, Rong Ge, and Ali Kemal Sinop. Towards a Better Approximation for Sparsest Cut? In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 270-279, Los Alamitos, CA, USA, 2013. IEEE Computer Society. Google Scholar
  3. Sanjeev Arora, James R. Lee, and Assaf Naor. Euclidean distortion and the Sparsest Cut. In In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 553-562. ACM Press, 2005. Google Scholar
  4. Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander Flows, Geometric Embeddings and Graph Partitioning. J. ACM, 56(2):5:1-5:37, April 2009. Google Scholar
  5. Baruch Awerbuch and David Peleg. Sparse partitions (extended abstract). In FOCS, pages 503-513, 1990. Google Scholar
  6. Sandeep N. Bhatt and Frank Thomson Leighton. A Framework for Solving VLSI Graph Layout Problems. J. Comput. Syst. Sci., 28(2):300-343, 1984. Google Scholar
  7. Jeff Cheeger, Bruce Kleiner, and Assaf Naor. A (log n)^Ω(1) Integrality Gap for the Sparsest Cut SDP. In FOCS, pages 555-564, 2009. Google Scholar
  8. Venkatesan Guruswami and Ali Kemal Sinop. Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. In FOCS, pages 482-491, 2011. Google Scholar
  9. Venkatesan Guruswami and Ali Kemal Sinop. Faster SDP Hierarchy Solvers for Local Rounding Algorithms. In FOCS, pages 197-206, 2012. Google Scholar
  10. Venkatesan Guruswami and Ali Kemal Sinop. Optimal column-based low-rank matrix reconstruction. In SODA, pages 1207-1214, 2012. Google Scholar
  11. Venkatesan Guruswami and Ali Kemal Sinop. Approximating Non-Uniform Sparsest Cut Via Generalized Spectra. In SODA, pages 295-305, 2013. Google Scholar
  12. Venkatesan Guruswami and Ali Kemal Sinop. Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs. CoRR, abs/1312.3024, 2013. Google Scholar
  13. Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11:796-817, 2001. Google Scholar
  14. Monique Laurent. A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming. Mathematics of Operations Research, 28(3):470-496, 2003. Google Scholar
  15. Frank Thomson Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787-832, 1999. Google Scholar
  16. Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888-905, 2000. Google Scholar
  17. Ali Kemal Sinop and Leo Grady. Uninitialized, globally optimal, graph-based rectilinear shape segmentation the opposing metrics method. In ICCV, pages 1-8, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact