Document Open Access Logo

Certified Algorithms: Worst-Case Analysis and Beyond

Authors Konstantin Makarychev, Yury Makarychev

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2020.49.pdf
  • Filesize: 488 kB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Theory of computation → Approximation algorithms analysis
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Facility location and clustering
Keywords
  • certified algorithm
  • perturbation resilience
  • Bilu
  • Linial stability
  • beyond-worst-case analysis
  • approximation algorithm
  • integrality

Metrics

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

Abstract

In this paper, we introduce the notion of a certified algorithm. Certified algorithms provide worst-case and beyond-worst-case performance guarantees. First, a γ-certified algorithm is also a γ-approximation algorithm - it finds a γ-approximation no matter what the input is. Second, it exactly solves γ-perturbation-resilient instances (γ-perturbation-resilient instances model real-life instances). Additionally, certified algorithms have a number of other desirable properties: they solve both maximization and minimization versions of a problem (e.g. Max Cut and Min Uncut), solve weakly perturbation-resilient instances, and solve optimization problems with hard constraints.
In the paper, we define certified algorithms, describe their properties, present a framework for designing certified algorithms, provide examples of certified algorithms for Max Cut/Min Uncut, Minimum Multiway Cut, k-medians and k-means. We also present some negative results.

Cite As Get BibTex

Konstantin Makarychev and Yury Makarychev. Certified Algorithms: Worst-Case Analysis and Beyond. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.49

Author Details

Konstantin Makarychev
  • Northwestern University, Evanston, IL, USA
Yury Makarychev
  • Toyota Technological Institute at Chicago, Chicago, IL, USA

Funding

  • Makarychev, Yury: Supported by NSF CCF-1718820.

References

  1. Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. O(√log n) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems. In Proceedings of the Symposium on Theory of Computing, pages 573-581, 2005. Google Scholar
  2. Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, and Chen Dan. Bilu-Linial stability, certified algorithms and the Independent Set problem. In Proceedings of the European Symposium on Algorithms, 2019. Google Scholar
  3. Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev. Algorithms for stable and perturbation-resilient problems. In Proceedings of the Symposium on Theory of Computing, pages 438-451, 2017. Google Scholar
  4. Sanjeev Arora, James Lee, and Assaf Naor. Euclidean distortion and the sparsest cut. Journal of the American Mathematical Society, 21(1):1-21, 2008. Google Scholar
  5. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on computing, 33(3):544-562, 2004. Google Scholar
  6. Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Information Processing Letters, 112(1-2):49-54, 2012. Google Scholar
  7. Maria-Florina Balcan, Nika Haghtalab, and Colin White. k-Center Clustering Under Perturbation Resilience. In International Colloquium on Automata, Languages, and Programming, 2016. Google Scholar
  8. Maria-Florina Balcan and Colin White. Clustering under local stability: Bridging the gap between worst-case and beyond worst-case analysis. arXiv preprint, 2017. URL: http://arxiv.org/abs/1705.07157.
  9. Yonatan Bilu, Amit Daniely, Nati Linial, and Michael Saks. On the practically interesting instances of MAXCUT. In International Symposium on Theoretical Aspects of Computer Science, 2013. Google Scholar
  10. Yonatan Bilu and Nathan Linial. Are Stable Instances Easy? In Innovations in Computer Science, pages 332-341, 2010. Google Scholar
  11. Vincent Cohen-Addad and Chris Schwiegelshohn. On the local structure of stable clustering instances. In Proceedings of the Symposium on Foundations of Computer Science, pages 49-60, 2017. Google Scholar
  12. Zachary Friggstad, Kamyar Khodamoradi, and Mohammad R. Salavatipour. Exact Algorithms and Lower Bounds for Stable Instances of Euclidean K-means. In Proceedings of the Symposium on Discrete Algorithms, pages 2958-2972, 2019. Google Scholar
  13. Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for facility location. arXiv preprint, 2008. URL: http://arxiv.org/abs/0809.2554.
  14. Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. SIAM Journal on Computing, 45(2):530-547, 2016. Google Scholar
  15. Konstantin Makarychev and Yury Makarychev. Bilu-Linial Stability. In T. Hazan, G. Papandreou, and D. Tarlow, editors, Perturbations, Optimization, and Statistics, chapter 13. MIT Press, 2016. Google Scholar
  16. Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Bilu-Linial stable instances of Max Cut and Minimum Multiway Cut. In Proceedings of the Symposium on Discrete Algorithms, pages 890-906, 2014. Google Scholar
  17. Ankit Sharma and Jan Vondrák. Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds. In Proceedings of the Symposium on Theory of Computing, 2014. Google Scholar
  18. Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):385-463, 2004. Google Scholar
  19. David Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. In Proceedings of the Symposium on Theory of Computing, 2006. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact