71 Search Results for "Mathieu, Claire"

Volume

LIPIcs, Volume 60

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

APPROX/RANDOM 2016, September 7-9, 2016, Paris, France

Editors: Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans

Document
DOI: 10.4230/LIPIcs.ESA.2023.94
Parameterized Matroid-Constrained Maximum Coverage

Authors: François Sellier

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
In this paper, we introduce the concept of Density-Balanced Subset in a matroid, in which independent sets can be sampled so as to guarantee that (i) each element has the same probability to be sampled, and (ii) those events are negatively correlated. These Density-Balanced Subsets are subsets in the ground set of a matroid in which the traditional notion of uniform random sampling can be extended. We then provide an application of this concept to the Matroid-Constrained Maximum Coverage problem. In this problem, given a matroid ℳ = (V, ℐ) of rank k on a ground set V and a coverage function f on V, the goal is to find an independent set S ∈ ℐ maximizing f(S). This problem is an important special case of the much-studied submodular function maximization problem subject to a matroid constraint; this is also a generalization of the maximum k-cover problem in a graph. In this paper, assuming that the coverage function has a bounded frequency μ (i.e., any element of the underlying universe of the coverage function appears in at most μ sets), we design a procedure, parameterized by some integer ρ, to extract in polynomial time an approximate kernel of size ρ ⋅ k that is guaranteed to contain a 1 - (μ - 1)/ρ approximation of the optimal solution. This procedure can then be used to get a Fixed-Parameter Tractable Approximation Scheme (FPT-AS) providing a 1 - ε approximation in time (μ/ε)^O(k) ⋅ |V|^O(1). This generalizes and improves the results of [Manurangsi, 2019] and [Huang and Sellier, 2022], providing the first FPT-AS working on an arbitrary matroid. Moreover, as the kernel has a very simple characterization, it can be constructed in the streaming setting.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.91
A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees

Authors: Claire Mathieu and Hang Zhou

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the root of the tree such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. For the special case when all terminals have equal demands, a long line of research culminated in a quasi-polynomial time approximation scheme [Jayaprakash and Salavatipour, TALG 2023] and a polynomial time approximation scheme [Mathieu and Zhou, TALG 2023]. In this work, we study the general case when the terminals have arbitrary demands. Our main contribution is a polynomial time (1.5+ε)-approximation algorithm for the UCVRP on trees. This is the first improvement upon the 2-approximation algorithm more than 30 years ago. Our approximation ratio is essentially best possible, since it is NP-hard to approximate the UCVRP on trees to better than a 1.5 factor.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.27
An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees

Authors: Marc Dufay, Claire Mathieu, and Hang Zhou

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with integer edge weights, a depot, a set of n terminals, and a distance constraint D. The goal is to find a minimum number of tours starting and ending at the depot such that those tours together cover all the terminals and the length of each tour is at most D. The DVRP on trees is of independent interest, because it is equivalent to the "virtual machine packing" problem on trees studied by Sindelar et al. [SPAA'11]. We design a simple and natural approximation algorithm for the tree DVRP, parameterized by ε > 0. We show that its approximation ratio is α + ε, where α ≈ 1.691, and in addition, that our analysis is essentially tight. The running time is polynomial in n and D. The approximation ratio improves on the ratio of 2 due to Nagarajan and Ravi [Networks'12]. The main novelty of this paper lies in the analysis of the algorithm. It relies on a reduction from the tree DVRP to the bounded space online bin packing problem via a new notion of "reduced length".
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.63
Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm

Authors: Fabrizio Grandoni, Claire Mathieu, and Hang Zhou

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the depot such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. Our main result is a polynomial-time (2+ε)-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.68
Maximum Weight b-Matchings in Random-Order Streams

Authors: Chien-Chung Huang and François Sellier

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We consider the maximum weight b-matching problem in the random-order semi-streaming model. Assuming all weights are small integers drawn from [1,W], we present a 2 - 1/(2W) + ε approximation algorithm, using a memory of O(max(|M_G|, n) ⋅ poly(log(m),W,1/ε)), where |M_G| denotes the cardinality of the optimal matching. Our result generalizes that of Bernstein [Aaron Bernstein, 2020], which achieves a 3/2 + ε approximation for the maximum cardinality simple matching. When W is small, our result also improves upon that of Gamlath et al. [Gamlath et al., 2019], which obtains a 2 - δ approximation (for some small constant δ ∼ 10^{-17}) for the maximum weight simple matching. In particular, for the weighted b-matching problem, ours is the first result beating the approximation ratio of 2. Our technique hinges on a generalized weighted version of edge-degree constrained subgraphs, originally developed by Bernstein and Stein [Aaron Bernstein and Cliff Stein, 2015]. Such a subgraph has bounded vertex degree (hence uses only a small number of edges), and can be easily computed. The fact that it contains a 2 - 1/(2W) + ε approximation of the maximum weight matching is proved using the classical Kőnig-Egerváry’s duality theorem.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.95
A PTAS for Capacitated Vehicle Routing on Trees

Authors: Claire Mathieu and Hang Zhou

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.43
Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

Authors: Claire Mathieu and Hang Zhou

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We give a probabilistic analysis of the unit-demand Euclidean capacitated vehicle routing problem in the random setting, where the input distribution consists of n unit-demand customers modeled as independent, identically distributed uniform random points in the two-dimensional plane. The objective is to visit every customer using a set of routes of minimum total length, such that each route visits at most k customers, where k is the capacity of a vehicle. All of the following results are in the random setting and hold asymptotically almost surely. The best known polynomial-time approximation for this problem is the iterated tour partitioning (ITP) algorithm, introduced in 1985 by Haimovich and Rinnooy Kan. They showed that the ITP algorithm is near-optimal when k is either o(√n) or ω(√n), and they asked whether the ITP algorithm was "also effective in the intermediate range". In this work, we show that when k = √n, the ITP algorithm is at best a (1+c₀)-approximation for some positive constant c₀. On the other hand, the approximation ratio of the ITP algorithm was known to be at most 0.995+α due to Bompadre, Dror, and Orlin, where α is the approximation ratio of an algorithm for the traveling salesman problem. In this work, we improve the upper bound on the approximation ratio of the ITP algorithm to 0.915+α. Our analysis is based on a new lower bound on the optimal cost for the metric capacitated vehicle routing problem, which may be of independent interest.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.68
A Simple Algorithm for Graph Reconstruction

Authors: Claire Mathieu and Hang Zhou

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
How efficiently can we find an unknown graph using distance queries between its vertices? We assume that the unknown graph is connected, unweighted, and has bounded degree. The goal is to find every edge in the graph. This problem admits a reconstruction algorithm based on multi-phase Voronoi-cell decomposition and using Õ(n^{3/2}) distance queries [Kannan et al., 2018]. In our work, we analyze a simple reconstruction algorithm. We show that, on random Δ-regular graphs, our algorithm uses Õ(n) distance queries. As by-products, we can reconstruct those graphs using O(log² n) queries to an all-distances oracle or Õ(n) queries to a betweenness oracle, and we bound the metric dimension of those graphs by log² n. Our reconstruction algorithm has a very simple structure, and is highly parallelizable. On general graphs of bounded degree, our reconstruction algorithm has subquadratic query complexity.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.80
Approximating Maximum Integral Multiflows on Bounded Genus Graphs

Authors: Chien-Chung Huang, Mathieu Mari, Claire Mathieu, and Jens Vygen

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.32
Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint

Authors: Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
Given a set D of n unit disks in the plane and an integer k <= n, the maximum area connected subset problem asks for a set D' subseteq D of size k that maximizes the area of the union of disks, under the constraint that this union is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint. We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a 1/2-approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of epsilon k disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.73
Covering Clients with Types and Budgets

Authors: Dimitris Fotakis, Laurent Gourvès, Claire Mathieu, and Abhinav Srivastav

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
In this paper, we consider a variant of the facility location problem. Imagine the scenario where facilities are categorized into multiple types such as schools, hospitals, post offices, etc. and the cost of connecting a client to a facility is realized by the distance between them. Each client has a total budget on the distance she/he is willing to travel. The goal is to open the minimum number of facilities such that the aggregate distance of each client to multiple types is within her/his budget. This problem closely resembles to the set cover and r-domination problems. Here, we study this problem in different settings. Specifically, we present some positive and negative results in the general setting, where no assumption is made on the distance values. Then we show that better results can be achieved when clients and facilities lie in a metric space.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/DagRep.7.4.1
Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141)

Authors: Bodo Manthey, Claire Mathieu, Heiko Röglin, and Eli Upfal

Published in: Dagstuhl Reports, Volume 7, Issue 4 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17141 "Probabilistic Methods in the Design and Analysis of Algorithms". Probabilistic methods play a central role in theoretical computer science. They are a powerful and widely applied tool used, for example, for designing efficient randomized algorithms and for establishing various lower bounds in complexity theory. They also form the basis of frameworks like average-case and smoothed analysis, in which algorithms are analyzed beyond the classical worst-case perspective. The seminar was on probabilistic methods with a focus on the design and analysis of algorithms. The seminar helped to consolidate the research and to foster collaborations among the researchers who use probabilistic methods in different areas of the design and analysis of algorithms.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.8
Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs

Authors: Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Local search for combinatorial optimization problems is becoming a dominant algorithmic paradigm, with several papers using it to resolve long-standing open problems. In this paper, we prove the following `4-local' version of Hall's theorem for planar graphs: given a bipartite planar graph G = (B, R, E) such that |N(B')| >= |B'| for all |B'| <= 4, there exists a matching of size at least |B|/4 in G; furthermore this bound is tight. Besides immediately implying improved bounds for several problems studied in previous papers, we find this variant of Hall's theorem to be of independent interest in graph theory.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.48
Dynamic Clustering to Minimize the Sum of Radii

Authors: Monika Henzinger, Dariusz Leniowski, and Claire Mathieu

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem. We present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
  • Refine by Author
  • 21 Mathieu, Claire
  • 7 Zhou, Hang
  • 3 Huang, Chien-Chung
  • 3 Marx, Dániel
  • 2 Coja-Oghlan, Amin
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Approximation algorithms analysis
  • 3 Theory of computation → Routing and network design problems
  • 2 Theory of computation → Packing and covering problems
  • 1 Networks → Network algorithms
  • 1 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 10 approximation algorithms
  • 4 capacitated vehicle routing
  • 4 planar graphs
  • 3 approximation
  • 3 graph algorithms
  • Show More...

  • Refine by Type
  • 70 document
  • 1 volume

  • Refine by Publication Year
  • 52 2016
  • 4 2023
  • 3 2017
  • 3 2021
  • 2 2010
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact