Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)
Miles Simmons, Ishan Bansal, and Joe Cheriyan. A Bad Example for Jain’s Iterative Rounding Theorem for the Cover Small Cuts Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)
@InProceedings{simmons_et_al:LIPIcs.APPROX/RANDOM.2026.9,
author = {Simmons, Miles and Bansal, Ishan and Cheriyan, Joe},
title = {{A Bad Example for Jain’s Iterative Rounding Theorem for the Cover Small Cuts Problem}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
pages = {9:1--9:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-449-9},
ISSN = {1868-8969},
year = {2026},
volume = {392},
editor = {Singh, Mohit and Gur, Tom},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.9},
URN = {urn:nbn:de:0030-drops-277263},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2026.9},
annote = {Keywords: approximation algorithms, capacitated network design, covering small cuts, edge-connectivity of graphs, f-connectivity problem, iterative rounding method, primal-dual method}
}
Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)
Ishan Bansal, Joe Cheriyan, Sanjeev Khanna, and Miles Simmons. Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{bansal_et_al:LIPIcs.ICALP.2025.20,
author = {Bansal, Ishan and Cheriyan, Joe and Khanna, Sanjeev and Simmons, Miles},
title = {{Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity}},
booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
pages = {20:1--20:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-372-0},
ISSN = {1868-8969},
year = {2025},
volume = {334},
editor = {Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.20},
URN = {urn:nbn:de:0030-drops-233973},
doi = {10.4230/LIPIcs.ICALP.2025.20},
annote = {Keywords: Approximation algorithms, Capacitated network design, Covering small cuts, Edge-connectivity of graphs, f-Connectivity problem, Flexible Graph Connectivity, Knapsack-cover inequalities}
}