Search Results

Documents authored by Mari, Mathieu


Document
Online Multi-Level Aggregation with Delays and Stochastic Arrivals

Authors: Mathieu Mari, Michał Pawłowski, Runtian Ren, and Piotr Sankowski

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)


Abstract
This paper presents a new research direction for online Multi-Level Aggregation (MLA) with delays. Given an edge-weighted rooted tree T as input, a sequence of requests arriving at its vertices needs to be served in an online manner. A request r is characterized by two parameters: its arrival time t(r) > 0 and location l(r) being a vertex in tree T. Once r arrives, we can either serve it immediately or postpone this action until any time t > t(r). A request that has not been served at its arrival time is called pending up to the moment it gets served. We can serve several pending requests at the same time, paying a service cost equal to the weight of the subtree containing the locations of all the requests served and the root of T. Postponing the service of a request r to time t > t(r) generates an additional delay cost of t - t(r). The goal is to serve all requests in an online manner such that the total cost (i.e., the total sum of service and delay costs) is minimized. The MLA problem is a generalization of several well-studied problems, including the TCP Acknowledgment (trees of depth 1), Joint Replenishment (depth 2), and Multi-Level Message Aggregation (arbitrary depth). The current best algorithm achieves a competitive ratio of O(d²), where d denotes the depth of the tree. Here, we consider a stochastic version of MLA where the requests follow a Poisson arrival process. We present a deterministic online algorithm that achieves a constant ratio of expectations, meaning that the ratio between the expected costs of the solution generated by our algorithm and the optimal offline solution is bounded by a constant. Our algorithm is obtained by carefully combining two strategies. In the first one, we plan periodic oblivious visits to the subset of frequent vertices, whereas, in the second one, we greedily serve the pending requests in the remaining vertices. This problem is complex enough to demonstrate a very rare phenomenon that "single-minded" or "sample-average" strategies are not enough in stochastic optimization.

Cite as

Mathieu Mari, Michał Pawłowski, Runtian Ren, and Piotr Sankowski. Online Multi-Level Aggregation with Delays and Stochastic Arrivals. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 49:1-49:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{mari_et_al:LIPIcs.ISAAC.2024.49,
  author =	{Mari, Mathieu and Paw{\l}owski, Micha{\l} and Ren, Runtian and Sankowski, Piotr},
  title =	{{Online Multi-Level Aggregation with Delays and Stochastic Arrivals}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{49:1--49:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.49},
  URN =		{urn:nbn:de:0030-drops-221768},
  doi =		{10.4230/LIPIcs.ISAAC.2024.49},
  annote =	{Keywords: online algorithms, online network design, stochastic model, Poisson arrivals}
}
Document
Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions

Authors: Fabrizio Grandoni, Edin Husić, Mathieu Mari, and Antoine Tinguely

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)


Abstract
In the maximum independent set of convex polygons problem, we are given a set of n convex polygons in the plane with the objective of selecting a maximum cardinality subset of non-overlapping polygons. Here we study a special case of the problem where the edges of the polygons can take at most d fixed directions. We present an 8d/3-approximation algorithm for this problem running in time O((nd)^O(d4^d)). The previous-best polynomial-time approximation (for constant d) was a classical n^ε approximation by Fox and Pach [SODA'11] that has recently been improved to a OPT^ε-approximation algorithm by Cslovjecsek, Pilipczuk and Węgrzycki [SODA '24], which also extends to an arbitrary set of convex polygons. Our result builds on, and generalizes the recent constant factor approximation algorithms for the maximum independent set of axis-parallel rectangles problem (which is a special case of our problem with d = 2) by Mitchell [FOCS'21] and Gálvez, Khan, Mari, Mömke, Reddy, and Wiese [SODA'22].

Cite as

Fabrizio Grandoni, Edin Husić, Mathieu Mari, and Antoine Tinguely. Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{grandoni_et_al:LIPIcs.SoCG.2024.61,
  author =	{Grandoni, Fabrizio and Husi\'{c}, Edin and Mari, Mathieu and Tinguely, Antoine},
  title =	{{Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{61:1--61:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.61},
  URN =		{urn:nbn:de:0030-drops-200066},
  doi =		{10.4230/LIPIcs.SoCG.2024.61},
  annote =	{Keywords: Approximation algorithms, packing, independent set, polygons}
}
Document
A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items

Authors: Mathieu Mari, Timothé Picavet, and Michał Pilipczuk

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal is to pack as many of these rectangles inside the box without overlap. Naturally, this problem is NP-complete. Recently, Grandoni et al. [ESA'19] showed that it is also 𝖶[1]-hard when parameterized by the size k of the sought packing, and they presented a parameterized approximation scheme (PAS) for the variant where we are allowed to rotate the rectangles by 90° before packing them into the box. Obtaining a PAS for the original 2D-Knapsack problem, without rotation, appears to be a challenging open question. In this work, we make progress towards this goal by showing a PAS under the following assumptions: - both the box and all the input rectangles have integral, polynomially bounded sidelengths; - every input rectangle is wide - its width is greater than its height; and - the aspect ratio of the box is bounded by a constant. Our approximation scheme relies on a mix of various parameterized and approximation techniques, including color coding, rounding, and searching for a structured near-optimum packing using dynamic programming.

Cite as

Mathieu Mari, Timothé Picavet, and Michał Pilipczuk. A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{mari_et_al:LIPIcs.IPEC.2023.33,
  author =	{Mari, Mathieu and Picavet, Timoth\'{e} and Pilipczuk, Micha{\l}},
  title =	{{A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{33:1--33:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.33},
  URN =		{urn:nbn:de:0030-drops-194529},
  doi =		{10.4230/LIPIcs.IPEC.2023.33},
  annote =	{Keywords: Parameterized complexity, Approximation scheme, Geometric knapsack, Color coding, Dynamic programming, Computational geometry}
}
Document
Track A: Algorithms, Complexity and Games
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.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
Fixed-Parameter Algorithms for Unsplittable Flow Cover

Authors: Andrés Cristi, Mathieu Mari, and Andreas Wiese

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e. There is a polynomial time 4-approximation for the problem [Bar-Noy et al., STOC 2000] and also a QPTAS [Höhn et al., ICALP 2014]. In this paper we study fixed-parameter algorithms for the problem. We show that it is W[1]-hard but it becomes FPT if we can slightly violate the edge demands (resource augmentation) and also if there are at most k different task sizes. Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of f(k)⋅ n^O_ε(1) that outputs a solution with at most (1+ε)k tasks or assert that there is no solution with at most k tasks. In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times.

Cite as

Andrés Cristi, Mathieu Mari, and Andreas Wiese. Fixed-Parameter Algorithms for Unsplittable Flow Cover. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{cristi_et_al:LIPIcs.STACS.2020.42,
  author =	{Cristi, Andr\'{e}s and Mari, Mathieu and Wiese, Andreas},
  title =	{{Fixed-Parameter Algorithms for Unsplittable Flow Cover}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.42},
  URN =		{urn:nbn:de:0030-drops-119037},
  doi =		{10.4230/LIPIcs.STACS.2020.42},
  annote =	{Keywords: Unsplittable Flow Cover, fixed parameter algorithms, approximation algorithms}
}
Document
APPROX
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.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}
}
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