2 Search Results for "Meunier, Frédéric"

Document
DOI: 10.4230/LIPIcs.SoCG.2020.31
No-Dimensional Tverberg Theorems and Algorithms

Authors: Aruni Choudhary and Wolfgang Mulzer

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Tverberg’s theorem states that for any k ≥ 2 and any set P ⊂ ℝ^d of at least (d + 1)(k - 1) + 1 points, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem lies in the complexity class PPAD ∩ PLS, but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa [SODA 2019] gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set P ⊂ ℝ^d and any k ∈ {2, … , n} in O(nd ⌈log k⌉) time a k-partition of P such that there is a ball of radius O((k/√n)diam(P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, and that there are no approximation algorithms that are truly polynomial in any dimension, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria’s method [Israel Journal Math., 1992] to reduce the Tverberg problem to the Colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem.
Cite as

Aruni Choudhary and Wolfgang Mulzer. No-Dimensional Tverberg Theorems and Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 31:1-31:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.SoCG.2020.31,
  author =	{Choudhary, Aruni and Mulzer, Wolfgang},
  title =	{{No-Dimensional Tverberg Theorems and Algorithms}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.31},
  URN =		{urn:nbn:de:0030-drops-121893},
  doi =		{10.4230/LIPIcs.SoCG.2020.31},
  annote =	{Keywords: Tverberg’s theorem, Colorful Carath\'{e}odory Theorem, Tensor lifting}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.34
Online Train Shunting

Authors: Vianney Boeuf and Frédéric Meunier

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
At the occasion of ATMOS 2012, Tim Nonner and Alexander Souza defined a new train shunting problem that can roughly be described as follows. We are given a train visiting stations in a given order and cars located at some source stations. Each car has a target station. During the trip of the train, the cars are added to the train at their source stations and removed from it at their target stations. An addition or a removal of a car in the strict interior of the train incurs a cost higher than when the operation is performed at the end of the train. The problem consists in minimizing the total cost, and thus, at each source station of a car, the position the car takes in the train must be carefully decided. Among other results, Nonner and Souza showed that this problem is polynomially solvable by reducing the problem to the computation of a minimum independent set in a bipartite graph. They worked in the offline setting, i.e. the sources and the targets of all cars are known before the trip of the train starts. We study the online version of the problem, in which cars become known at their source stations. We derive a 2-competitive algorithm and prove than no better ratios are achievable. Other related questions are also addressed.
Cite as

Vianney Boeuf and Frédéric Meunier. Online Train Shunting. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 34-45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{boeuf_et_al:OASIcs.ATMOS.2014.34,
  author =	{Boeuf, Vianney and Meunier, Fr\'{e}d\'{e}ric},
  title =	{{Online Train Shunting}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{34--45},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.34},
  URN =		{urn:nbn:de:0030-drops-47512},
  doi =		{10.4230/OASIcs.ATMOS.2014.34},
  annote =	{Keywords: Bipartite graph, competitive analysis, online algorithm, train shunting problem, vertex cover}
}
  • Refine by Author
  • 1 Boeuf, Vianney
  • 1 Choudhary, Aruni
  • 1 Meunier, Frédéric
  • 1 Mulzer, Wolfgang

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Bipartite graph
  • 1 Colorful Carathéodory Theorem
  • 1 Tensor lifting
  • 1 Tverberg’s theorem
  • 1 competitive analysis
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2014
  • 1 2020

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact