Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Ce Jin, Michael Kapralov, Sepideh Mahabadi, and Ali Vakilian. Streaming Algorithms for Connectivity Augmentation. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 93:1-93:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jin_et_al:LIPIcs.ICALP.2024.93, author = {Jin, Ce and Kapralov, Michael and Mahabadi, Sepideh and Vakilian, Ali}, title = {{Streaming Algorithms for Connectivity Augmentation}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {93:1--93:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.93}, URN = {urn:nbn:de:0030-drops-202367}, doi = {10.4230/LIPIcs.ICALP.2024.93}, annote = {Keywords: streaming algorithms, connectivity augmentation} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Kevin Hua, Daniel Li, Jaewoo Park, and Thatchaphol Saranurak. Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 87:1-87:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hua_et_al:LIPIcs.ICALP.2024.87, author = {Hua, Kevin and Li, Daniel and Park, Jaewoo and Saranurak, Thatchaphol}, title = {{Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {87:1--87:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.87}, URN = {urn:nbn:de:0030-drops-202302}, doi = {10.4230/LIPIcs.ICALP.2024.87}, annote = {Keywords: Graphs, Flows, Randomized Algorithms, Vertex Connectivity} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Ishan Bansal, Joseph Cheriyan, Logan Grout, and Sharat Ibrahimpur. Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bansal_et_al:LIPIcs.ICALP.2023.15, author = {Bansal, Ishan and Cheriyan, Joseph and Grout, Logan and Ibrahimpur, Sharat}, title = {{Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {15:1--15:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.15}, URN = {urn:nbn:de:0030-drops-180678}, doi = {10.4230/LIPIcs.ICALP.2023.15}, annote = {Keywords: Approximation algorithms, Edge-connectivity of graphs, f-Connectivity problem, Flexible Graph Connectivity, Minimum cuts, Network design, Primal-dual method, Small cuts} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Chandra Chekuri and Rhea Jain. Approximation Algorithms for Network Design in Non-Uniform Fault Models. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chekuri_et_al:LIPIcs.ICALP.2023.36, author = {Chekuri, Chandra and Jain, Rhea}, title = {{Approximation Algorithms for Network Design in Non-Uniform Fault Models}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {36:1--36:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.36}, URN = {urn:nbn:de:0030-drops-180885}, doi = {10.4230/LIPIcs.ICALP.2023.36}, annote = {Keywords: non-uniform faults, network design, approximation algorithm} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Joseph Cheriyan, Robert Cummings, Jack Dippel, and Jasper Zhu. An Improved Approximation Algorithm for the Matching Augmentation Problem. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cheriyan_et_al:LIPIcs.ISAAC.2021.38, author = {Cheriyan, Joseph and Cummings, Robert and Dippel, Jack and Zhu, Jasper}, title = {{An Improved Approximation Algorithm for the Matching Augmentation Problem}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {38:1--38:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.38}, URN = {urn:nbn:de:0030-drops-154714}, doi = {10.4230/LIPIcs.ISAAC.2021.38}, annote = {Keywords: 2-Edge connected graph, 2-edge covers, approximation algorithms, connectivity augmentation, forest augmentation problem, matching augmentation problem, network design} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Sylvia Boyd, Joseph Cheriyan, Arash Haddadan, and Sharat Ibrahimpur. Approximation Algorithms for Flexible Graph Connectivity. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{boyd_et_al:LIPIcs.FSTTCS.2021.9, author = {Boyd, Sylvia and Cheriyan, Joseph and Haddadan, Arash and Ibrahimpur, Sharat}, title = {{Approximation Algorithms for Flexible Graph Connectivity}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.9}, URN = {urn:nbn:de:0030-drops-155206}, doi = {10.4230/LIPIcs.FSTTCS.2021.9}, annote = {Keywords: Approximation Algorithms, Combinatorial Optimization, Network Design, Edge-Connectivity of Graphs, Reliability of Networks} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, and Lu Wang. A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{boyd_et_al:LIPIcs.APPROX/RANDOM.2020.61, author = {Boyd, Sylvia and Cheriyan, Joseph and Cummings, Robert and Grout, Logan and Ibrahimpur, Sharat and Szigeti, Zolt\'{a}n and Wang, Lu}, title = {{A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {61:1--61:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.61}, URN = {urn:nbn:de:0030-drops-126643}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.61}, annote = {Keywords: 2-Edge Connectivity, Approximation Algorithms, Subtour LP for TSP} }
Feedback for Dagstuhl Publishing