Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, and Liren Shan. Approximation Algorithm for Norm Multiway Cut. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{carlson_et_al:LIPIcs.ESA.2023.32, author = {Carlson, Charlie and Jafarov, Jafar and Makarychev, Konstantin and Makarychev, Yury and Shan, Liren}, title = {{Approximation Algorithm for Norm Multiway Cut}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {32:1--32:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.32}, URN = {urn:nbn:de:0030-drops-186854}, doi = {10.4230/LIPIcs.ESA.2023.32}, annote = {Keywords: Multiway cut, Approximation algorithms} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, and Yury Makarychev. Two-Sided Kirszbraun Theorem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{backurs_et_al:LIPIcs.SoCG.2021.13, author = {Backurs, Arturs and Mahabadi, Sepideh and Makarychev, Konstantin and Makarychev, Yury}, title = {{Two-Sided Kirszbraun Theorem}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {13:1--13:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.13}, URN = {urn:nbn:de:0030-drops-138129}, doi = {10.4230/LIPIcs.SoCG.2021.13}, annote = {Keywords: Kirszbraun theorem, Lipschitz map, Outer-extension, Two-sided extension} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
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)
@InProceedings{makarychev_et_al:LIPIcs.ITCS.2020.49, author = {Makarychev, Konstantin and Makarychev, Yury}, title = {{Certified Algorithms: Worst-Case Analysis and Beyond}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {49:1--49:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.49}, URN = {urn:nbn:de:0030-drops-117347}, doi = {10.4230/LIPIcs.ITCS.2020.49}, annote = {Keywords: certified algorithm, perturbation resilience, Bilu, Linial stability, beyond-worst-case analysis, approximation algorithm, integrality} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, and Chen Dan. Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{angelidakis_et_al:LIPIcs.ESA.2019.7, author = {Angelidakis, Haris and Awasthi, Pranjal and Blum, Avrim and Chatziafratis, Vaggos and Dan, Chen}, title = {{Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.7}, URN = {urn:nbn:de:0030-drops-111288}, doi = {10.4230/LIPIcs.ESA.2019.7}, annote = {Keywords: Bilu-Linial stability, perturbation resilience, beyond worst-case analysis, Independent Set, Vertex Cover, Multiway Cut} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Konstantin Makarychev and Yury Makarychev. Approximation Algorithms for CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 287-325, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{makarychev_et_al:DFU.Vol7.15301.287, author = {Makarychev, Konstantin and Makarychev, Yury}, title = {{Approximation Algorithms for CSPs}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {287--325}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.287}, URN = {urn:nbn:de:0030-drops-69685}, doi = {10.4230/DFU.Vol7.15301.287}, annote = {Keywords: Constraint satisfaction problems, Approximation algorithms, SDP, UGC} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, and Justin Ward. A Bi-Criteria Approximation Algorithm for k-Means. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{makarychev_et_al:LIPIcs.APPROX-RANDOM.2016.14, author = {Makarychev, Konstantin and Makarychev, Yury and Sviridenko, Maxim and Ward, Justin}, title = {{A Bi-Criteria Approximation Algorithm for k-Means}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {14:1--14:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.14}, URN = {urn:nbn:de:0030-drops-66370}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.14}, annote = {Keywords: k-means clustering, bicriteria approximation algorithms, linear programming, local search} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Konstantin Makarychev. Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 139-147, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{makarychev:LIPIcs.STACS.2013.139, author = {Makarychev, Konstantin}, title = {{Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {139--147}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.139}, URN = {urn:nbn:de:0030-drops-39290}, doi = {10.4230/LIPIcs.STACS.2013.139}, annote = {Keywords: approximation algorithms, approximation resistance, ordering CSPs} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Howard Karloff, Flip Korn, Konstantin Makarychev, and Yuval Rabani. On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 332-343, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{karloff_et_al:LIPIcs.STACS.2011.332, author = {Karloff, Howard and Korn, Flip and Makarychev, Konstantin and Rabani, Yuval}, title = {{On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {332--343}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.332}, URN = {urn:nbn:de:0030-drops-30246}, doi = {10.4230/LIPIcs.STACS.2011.332}, annote = {Keywords: ordered data, explanation problem} }
Feedback for Dagstuhl Publishing