Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Eden Chlamtáč, Yury Makarychev, and Ali Vakilian. Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chlamtac_et_al:LIPIcs.APPROX/RANDOM.2023.11, author = {Chlamt\'{a}\v{c}, Eden and Makarychev, Yury and Vakilian, Ali}, title = {{Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, 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.2023.11}, URN = {urn:nbn:de:0030-drops-188366}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.11}, annote = {Keywords: Red-Blue Set Cover Problem, Circuit Minimum Monotone Satisfying Assignment (MMSA) Problem, LP Rounding} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, and Andrew van der Poel. Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{demaine_et_al:LIPIcs.ESA.2019.37, author = {Demaine, Erik D. and Goodrich, Timothy D. and Kloster, Kyle and Lavallee, Brian and Liu, Quanquan C. and Sullivan, Blair D. and Vakilian, Ali and van der Poel, Andrew}, title = {{Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {37:1--37:15}, 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.37}, URN = {urn:nbn:de:0030-drops-111583}, doi = {10.4230/LIPIcs.ESA.2019.37}, annote = {Keywords: structural rounding, graph editing, approximation algorithms} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu. Approximation Algorithms for Min-Distance Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dalirrooyfard_et_al:LIPIcs.ICALP.2019.46, author = {Dalirrooyfard, Mina and Williams, Virginia Vassilevska and Vyas, Nikhil and Wein, Nicole and Xu, Yinzhan and Yu, Yuancheng}, title = {{Approximation Algorithms for Min-Distance Problems}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {46:1--46:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.46}, URN = {urn:nbn:de:0030-drops-106223}, doi = {10.4230/LIPIcs.ICALP.2019.46}, annote = {Keywords: fine-grained complexity, graph algorithms, diameter, radius, eccentricities} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Merav Parter, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee. Local Computation Algorithms for Spanners. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 58:1-58:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{parter_et_al:LIPIcs.ITCS.2019.58, author = {Parter, Merav and Rubinfeld, Ronitt and Vakilian, Ali and Yodpinyanee, Anak}, title = {{Local Computation Algorithms for Spanners}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {58:1--58:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.58}, URN = {urn:nbn:de:0030-drops-101510}, doi = {10.4230/LIPIcs.ITCS.2019.58}, annote = {Keywords: Local Computation Algorithms, Sub-linear Algorithms, Graph Spanners} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, and Anak Yodpinyanee. Fractional Set Cover in the Streaming Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{indyk_et_al:LIPIcs.APPROX-RANDOM.2017.12, author = {Indyk, Piotr and Mahabadi, Sepideh and Rubinfeld, Ronitt and Ullman, Jonathan and Vakilian, Ali and Yodpinyanee, Anak}, title = {{Fractional Set Cover in the Streaming Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, 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.2017.12}, URN = {urn:nbn:de:0030-drops-75613}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.12}, annote = {Keywords: Streaming Algorithms, Fractional Set Cover, LP relaxation, Multiplicative Weight Update} }
Feedback for Dagstuhl Publishing