LIPIcs, Volume 60
APPROX/RANDOM 2016, September 7-9, 2016, Paris, France
Editors: Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
François Sellier. Parameterized Matroid-Constrained Maximum Coverage. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 94:1-94:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{sellier:LIPIcs.ESA.2023.94, author = {Sellier, Fran\c{c}ois}, title = {{Parameterized Matroid-Constrained Maximum Coverage}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {94:1--94:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.94}, URN = {urn:nbn:de:0030-drops-187475}, doi = {10.4230/LIPIcs.ESA.2023.94}, annote = {Keywords: Matroids, approximate kernel, maximum coverage} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Claire Mathieu and Hang Zhou. A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 91:1-91:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{mathieu_et_al:LIPIcs.ICALP.2023.91, author = {Mathieu, Claire and Zhou, Hang}, title = {{A Tight (1.5+\epsilon)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {91:1--91:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.91}, URN = {urn:nbn:de:0030-drops-181430}, doi = {10.4230/LIPIcs.ICALP.2023.91}, annote = {Keywords: approximation algorithms, capacitated vehicle routing, graph algorithms, combinatorial optimization} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Marc Dufay, Claire Mathieu, and Hang Zhou. An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dufay_et_al:LIPIcs.STACS.2023.27, author = {Dufay, Marc and Mathieu, Claire and Zhou, Hang}, title = {{An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {27:1--27:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.27}, URN = {urn:nbn:de:0030-drops-176794}, doi = {10.4230/LIPIcs.STACS.2023.27}, annote = {Keywords: vehicle routing, distance constraint, approximation algorithms, trees} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Fabrizio Grandoni, Claire Mathieu, and Hang Zhou. Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{grandoni_et_al:LIPIcs.ITCS.2023.63, author = {Grandoni, Fabrizio and Mathieu, Claire and Zhou, Hang}, title = {{Unsplittable Euclidean Capacitated Vehicle Routing: A (2+\epsilon)-Approximation Algorithm}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {63:1--63:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.63}, URN = {urn:nbn:de:0030-drops-175660}, doi = {10.4230/LIPIcs.ITCS.2023.63}, annote = {Keywords: capacitated vehicle routing, approximation algorithms, Euclidean plane} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Chien-Chung Huang and François Sellier. Maximum Weight b-Matchings in Random-Order Streams. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{huang_et_al:LIPIcs.ESA.2022.68, author = {Huang, Chien-Chung and Sellier, Fran\c{c}ois}, title = {{Maximum Weight b-Matchings in Random-Order Streams}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {68:1--68:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.68}, URN = {urn:nbn:de:0030-drops-170062}, doi = {10.4230/LIPIcs.ESA.2022.68}, annote = {Keywords: Maximum weight matching, b-matching, streaming, random order} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Claire Mathieu and Hang Zhou. A PTAS for Capacitated Vehicle Routing on Trees. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{mathieu_et_al:LIPIcs.ICALP.2022.95, author = {Mathieu, Claire and Zhou, Hang}, title = {{A PTAS for Capacitated Vehicle Routing on Trees}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {95:1--95:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.95}, URN = {urn:nbn:de:0030-drops-164369}, doi = {10.4230/LIPIcs.ICALP.2022.95}, annote = {Keywords: approximation algorithms, capacitated vehicle routing, graph algorithms, combinatorial optimization} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Claire Mathieu and Hang Zhou. Probabilistic Analysis of Euclidean Capacitated Vehicle Routing. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{mathieu_et_al:LIPIcs.ISAAC.2021.43, author = {Mathieu, Claire and Zhou, Hang}, title = {{Probabilistic Analysis of Euclidean Capacitated Vehicle Routing}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {43:1--43:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.43}, URN = {urn:nbn:de:0030-drops-154769}, doi = {10.4230/LIPIcs.ISAAC.2021.43}, annote = {Keywords: capacitated vehicle routing, iterated tour partitioning, probabilistic analysis, approximation algorithms} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Claire Mathieu and Hang Zhou. A Simple Algorithm for Graph Reconstruction. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 68:1-68:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{mathieu_et_al:LIPIcs.ESA.2021.68, author = {Mathieu, Claire and Zhou, Hang}, title = {{A Simple Algorithm for Graph Reconstruction}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {68:1--68:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.68}, URN = {urn:nbn:de:0030-drops-146496}, doi = {10.4230/LIPIcs.ESA.2021.68}, annote = {Keywords: reconstruction, network topology, random regular graphs, metric dimension} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Chien-Chung Huang, Mathieu Mari, Claire Mathieu, and Jens Vygen. Approximating Maximum Integral Multiflows on Bounded Genus Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 80:1-80:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{huang_et_al:LIPIcs.ICALP.2021.80, author = {Huang, Chien-Chung and Mari, Mathieu and Mathieu, Claire and Vygen, Jens}, title = {{Approximating Maximum Integral Multiflows on Bounded Genus Graphs}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {80:1--80:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.80}, URN = {urn:nbn:de:0030-drops-141491}, doi = {10.4230/LIPIcs.ICALP.2021.80}, annote = {Keywords: Multi-commodity flows, approximation algorithms, bounded genus graphs} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa. Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2019.32, author = {Huang, Chien-Chung and Mari, Mathieu and Mathieu, Claire and Mitchell, Joseph S. B. and Mustafa, Nabil H.}, title = {{Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {32:1--32:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.32}, URN = {urn:nbn:de:0030-drops-112471}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.32}, annote = {Keywords: approximation algorithm, submodular function optimisation, unit disk graph, connectivity constraint} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Dimitris Fotakis, Laurent Gourvès, Claire Mathieu, and Abhinav Srivastav. Covering Clients with Types and Budgets. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 73:1-73:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fotakis_et_al:LIPIcs.ISAAC.2018.73, author = {Fotakis, Dimitris and Gourv\`{e}s, Laurent and Mathieu, Claire and Srivastav, Abhinav}, title = {{Covering Clients with Types and Budgets}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {73:1--73:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.73}, URN = {urn:nbn:de:0030-drops-100213}, doi = {10.4230/LIPIcs.ISAAC.2018.73}, annote = {Keywords: Facility Location, Geometric Set Cover, Local Search} }
Published in: Dagstuhl Reports, Volume 7, Issue 4 (2018)
Bodo Manthey, Claire Mathieu, Heiko Röglin, and Eli Upfal. Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141). In Dagstuhl Reports, Volume 7, Issue 4, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{manthey_et_al:DagRep.7.4.1, author = {Manthey, Bodo and Mathieu, Claire and R\"{o}glin, Heiko and Upfal, Eli}, title = {{Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141)}}, pages = {1--22}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {7}, number = {4}, editor = {Manthey, Bodo and Mathieu, Claire and R\"{o}glin, Heiko and Upfal, Eli}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.4.1}, URN = {urn:nbn:de:0030-drops-75452}, doi = {10.4230/DagRep.7.4.1}, annote = {Keywords: analysis of algorithms, average-case analysis, random graphs, randomized algorithms, smoothed analysis, sub-linear algorithms} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa. Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{antunes_et_al:LIPIcs.ESA.2017.8, author = {Antunes, Daniel and Mathieu, Claire and Mustafa, Nabil H.}, title = {{Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {8:1--8:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.8}, URN = {urn:nbn:de:0030-drops-78293}, doi = {10.4230/LIPIcs.ESA.2017.8}, annote = {Keywords: Planar graphs, Local search, Hall's theorem, Combinatorial optimization, Expansion} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Monika Henzinger, Dariusz Leniowski, and Claire Mathieu. Dynamic Clustering to Minimize the Sum of Radii. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 48:1-48:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{henzinger_et_al:LIPIcs.ESA.2017.48, author = {Henzinger, Monika and Leniowski, Dariusz and Mathieu, Claire}, title = {{Dynamic Clustering to Minimize the Sum of Radii}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {48:1--48:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.48}, URN = {urn:nbn:de:0030-drops-78749}, doi = {10.4230/LIPIcs.ESA.2017.48}, annote = {Keywords: dynamic algorithm, clustering, approximation, doubling dimension} }
Feedback for Dagstuhl Publishing