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} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Alessio Conte, Roberto Grossi, Mamadou Moustapha Kanté, Andrea Marino, Takeaki Uno, and Kunihiro Wasa. Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{conte_et_al:LIPIcs.MFCS.2019.73, author = {Conte, Alessio and Grossi, Roberto and Kant\'{e}, Mamadou Moustapha and Marino, Andrea and Uno, Takeaki and Wasa, Kunihiro}, title = {{Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {73:1--73:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.73}, URN = {urn:nbn:de:0030-drops-110174}, doi = {10.4230/LIPIcs.MFCS.2019.73}, annote = {Keywords: Graph algorithms, enumeration, listing and counting, Steiner trees, induced subgraphs} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized Complexity Dichotomy for Steiner Multicut. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 157-170, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bringmann_et_al:LIPIcs.STACS.2015.157, author = {Bringmann, Karl and Hermelin, Danny and Mnich, Matthias and van Leeuwen, Erik Jan}, title = {{Parameterized Complexity Dichotomy for Steiner Multicut}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {157--170}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.157}, URN = {urn:nbn:de:0030-drops-49115}, doi = {10.4230/LIPIcs.STACS.2015.157}, annote = {Keywords: graph cut problems, Steiner cut, fixed-parameter tractability} }
Feedback for Dagstuhl Publishing