Found 27 Documents (Results 1–27)
2-node-connectivity network design. (English) Zbl 07811869
MSC:
68Qxx
A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation. (English) Zbl 07844714
Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 1820-1833 (2023).
MSC:
68Qxx
Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. (English) Zbl 07693610
An improved approximation algorithm for the minimum \(k\)-edge connected multi-subgraph problem. (English) Zbl 07774442
Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 1612-1620 (2022).
MSC:
68Qxx
Breaching the 2-approximation barrier for the forest augmentation problem. (English) Zbl 07774441
Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 1598-1611 (2022).
MSC:
68Qxx
Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem. (English) Zbl 1525.90418
A simple LP-based approximation algorithm for the matching augmentation problem. (English) Zbl 1497.90164
Aardal, Karen (ed.) et al., Integer programming and combinatorial optimization. 23rd international conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13265, 57-69 (2022).
Flexible graph connectivity. (English) Zbl 1542.68113
Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. (English) Zbl 07765178
Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 370-383 (2021).
MSC:
68Qxx
Approximation algorithms for vertex-connectivity augmentation on the cycle. (English) Zbl 07603881
Koenemann, Jochen (ed.) et al., Approximation and online algorithms. 19th international workshop, WAOA 2021, Lisbon, Portugal, September 6–10, 2021. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12982, 1-22 (2021).
2-node-connectivity network design. (English) Zbl 07495129
Kaklamanis, Christos (ed.) et al., Approximation and online algorithms. 18th international workshop, WAOA 2020, virtual event, September 9–10, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12806, 220-235 (2021).
Approximation algorithms for connectivity augmentation problems. (English) Zbl 07493539
Santhanam, Rahul (ed.) et al., Computer science – theory and applications. 16th international computer science symposium in Russia, CSR 2021, Sochi, Russia, June 28 – July 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12730, 321-338 (2021).
MSC:
68Qxx
Chvátal-Gomory cuts for the Steiner tree problem. (English) Zbl 1464.05039
Reviewer: Xueliang Li (Tianjin)
Flexible graph connectivity. (English) Zbl 1503.90102
Bienstock, Daniel (ed.) et al., Integer programming and combinatorial optimization. 21st international conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12125, 13-26 (2020).
Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. (English) Zbl 07298290
Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 815-825 (2020).
MSC:
68Qxx
The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm. (English) Zbl 1452.90309
How to secure matchings against edge failures. (English) Zbl 1528.68296
Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 38, 16 p. (2019).
Improved approximation for tree augmentation: saving by rewiring. (English) Zbl 1429.68190
Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 632-645 (2018).
Filter Results by …
Document Type
- Journal Articles (15)
- Collection Articles (12)
all
top 5
Author
- Grandoni, Fabrizio (6)
- Nutov, Zeev (5)
- Ameli, Afrouz Jabal (4)
- Traub, Vera (4)
- Zenklusen, Rico (4)
- Hommelsheim, Felix (3)
- Mühlenthaler, Moritz (3)
- Adjiashvili, David (2)
- Byrka, Jarosław (2)
- Cecchetto, Federica (2)
- Cheriyan, Joseph (2)
- Dippel, Jack (2)
- Gálvez, Waldo (2)
- Ravi, Ramamoorthi (2)
- Angelidakis, Haris (1)
- Bamas, Étienne (1)
- Censor-Hillel, Keren (1)
- Cummings, Robert (1)
- Dory, Michal (1)
- Drygala, Marina (1)
- Fiorini, Samuel (1)
- Gaul, Daniela (1)
- Huynh, Tony (1)
- Hyatt-Denesik, Dylan (1)
- Iglesias, Jennifer (1)
- Kalaitzis, Christos (1)
- Karlin, Anna R. (1)
- Khan, Arindam (1)
- Klein, Nathan (1)
- Kortsarz, Guy (1)
- Narayan, Vishnu V. (1)
- Oveis Gharan, Shayan (1)
- Parekh, Ojas D. (1)
- Sanhueza-Matamala, Francisco (1)
- Sanità, Laura (1)
- Schaudt, Oliver (1)
- Schmidt, Daniel R. (1)
- Sornat, Krzysztof (1)
- Soto, José A. (1)
- Svensson, Ola (1)
- Weltge, Stefan (1)
- Zhang, Xinzhi (1)
- Zhu, Jasper (1)
- Zlatin, Michael (1)
all
top 5
Serial
- Math. Program. (5)
- Discrete Appl. Math. (2)
- Oper. Res. Lett. (2)
- SIAM J. Comput. (1)
- Theor. Comput. Sci. (1)
- Algorithmica (1)
- SIAM J. Discrete Math. (1)
- Distrib. Comput. (1)
- Theory Comput. Syst. (1)
Software
- SteinLib (1)
