Search Results

Documents authored by Gerard, Yan

Document
DOI: 10.4230/LIPIcs.MFCS.2024.19
The Canadian Traveller Problem on Outerplanar Graphs

Authors: Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gerard, Aurélie Lagoutte, Vincent Limouzy, and Lucas Pastor

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
We study the k-Canadian Traveller Problem, where a weighted graph G = (V,E,ω) with a source s ∈ V and a target t ∈ V are given. This problem also has a hidden input E_* ⊊ E of cardinality at most k representing blocked edges. The objective is to travel from s to t with the minimum distance. At the beginning of the walk, the blockages E_* are unknown: the traveller discovers that an edge is blocked when visiting one of its endpoints. Online algorithms, also called strategies, have been proposed for this problem and assessed with the competitive ratio, i.e., the ratio between the distance actually traversed by the traveller divided by the distance he would have traversed knowing the blockages in advance. Even though the optimal competitive ratio is 2k+1 even on unit-weighted planar graphs of treewidth 2, we design a polynomial-time strategy achieving competitive ratio 9 on unit-weighted outerplanar graphs. This value 9 also stands as a lower bound for this family of graphs as we prove that, for any ε > 0, no strategy can achieve a competitive ratio 9-ε. Finally, we show that it is not possible to achieve a constant competitive ratio (independent of G and k) on weighted outerplanar graphs.
Cite as

Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gerard, Aurélie Lagoutte, Vincent Limouzy, and Lucas Pastor. The Canadian Traveller Problem on Outerplanar Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beaudou_et_al:LIPIcs.MFCS.2024.19,
  author =	{Beaudou, Laurent and Berg\'{e}, Pierre and Chernyshev, Vsevolod and Dailly, Antoine and Gerard, Yan and Lagoutte, Aur\'{e}lie and Limouzy, Vincent and Pastor, Lucas},
  title =	{{The Canadian Traveller Problem on Outerplanar Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.19},
  URN =		{urn:nbn:de:0030-drops-205750},
  doi =		{10.4230/LIPIcs.MFCS.2024.19},
  annote =	{Keywords: Canadian Traveller Problem, Online algorithms, Competitive analysis, Outerplanar graphs}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2024.84
Shadoks Approach to Knapsack Polygonal Packing (CG Challenge)

Authors: Guilherme D. da Fonseca and Yan Gerard

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

Abstract
We describe the heuristics used by the Shadoks team in the CG:SHOP 2024 Challenge. Each instance consists of a convex polygon called container and a multiset of items, where each item is a simple polygon and has an associated value. The goal is to pack some of the items inside the container using translations, in order to maximize the sum of their values. Our strategy consists of obtaining good initial solutions and improving them with local search. To obtain the initial solutions we used integer programming and a carefully designed greedy approach.
Cite as

Guilherme D. da Fonseca and Yan Gerard. Shadoks Approach to Knapsack Polygonal Packing (CG Challenge). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 84:1-84:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dafonseca_et_al:LIPIcs.SoCG.2024.84,
  author =	{da Fonseca, Guilherme D. and Gerard, Yan},
  title =	{{Shadoks Approach to Knapsack Polygonal Packing}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{84:1--84:9},
  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.84},
  URN =		{urn:nbn:de:0030-drops-200293},
  doi =		{10.4230/LIPIcs.SoCG.2024.84},
  annote =	{Keywords: Packing, polygons, heuristics, integer programming, computational geometry}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2022.71
Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge)

Authors: Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We explain the heuristics used by the Shadoks team to win first place in the CG:SHOP 2022 challenge that considers the minimum partition into plane subgraphs. The goal is to partition a set of segments into as few subsets as possible such that segments in the same subset do not cross each other. The challenge has given 225 instances containing between 2500 and 75000 segments. For every instance, our solution was the best among all 32 participating teams.
Cite as

Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo. Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 71:1-71:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{crombez_et_al:LIPIcs.SoCG.2022.71,
  author =	{Crombez, Lo\"{i}c and da Fonseca, Guilherme D. and Gerard, Yan and Gonzalez-Lorenzo, Aldo},
  title =	{{Shadoks Approach to Minimum Partition into Plane Subgraphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{71:1--71:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.71},
  URN =		{urn:nbn:de:0030-drops-160794},
  doi =		{10.4230/LIPIcs.SoCG.2022.71},
  annote =	{Keywords: Plane graphs, graph coloring, intersection graph, conflict optimizer, line segments, computational geometry}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2021.63
Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge)

Authors: Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge on motion planning. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them.
Cite as

Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 63:1-63:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{crombez_et_al:LIPIcs.SoCG.2021.63,
  author =	{Crombez, Lo\"{i}c and da Fonseca, Guilherme D. and Gerard, Yan and Gonzalez-Lorenzo, Aldo and Lafourcade, Pascal and Libralesso, Luc},
  title =	{{Shadoks Approach to Low-Makespan Coordinated Motion Planning}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{63:1--63:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.63},
  URN =		{urn:nbn:de:0030-drops-138622},
  doi =		{10.4230/LIPIcs.SoCG.2021.63},
  annote =	{Keywords: heuristics, motion planning, digital geometry, shortest path}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.11
Efficient Algorithms for Battleship

Authors: Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
We consider an algorithmic problem inspired by the Battleship game. In the variant of the problem that we investigate, there is a unique ship of shape S ⊂ ℤ² which has been translated in the lattice ℤ². We assume that a player has already hit the ship with a first shot and the goal is to sink the ship using as few shots as possible, that is, by minimizing the number of missed shots. While the player knows the shape S, which position of S has been hit is not known. Given a shape S of n lattice points, the minimum number of misses that can be achieved in the worst case by any algorithm is called the Battleship complexity of the shape S and denoted c(S). We prove three bounds on c(S), each considering a different class of shapes. First, we have c(S) ≤ n-1 for arbitrary shapes and the bound is tight for parallelogram-free shapes. Second, we provide an algorithm that shows that c(S) = O(log n) if S is an HV-convex polyomino. Third, we provide an algorithm that shows that c(S) = O(log log n) if S is a digital convex set. This last result is obtained through a novel discrete version of the Blaschke-Lebesgue inequality relating the area and the width of any convex body.
Cite as

Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard. Efficient Algorithms for Battleship. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{crombez_et_al:LIPIcs.FUN.2021.11,
  author =	{Crombez, Lo\"{i}c and da Fonseca, Guilherme D. and Gerard, Yan},
  title =	{{Efficient Algorithms for Battleship}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.11},
  URN =		{urn:nbn:de:0030-drops-127728},
  doi =		{10.4230/LIPIcs.FUN.2021.11},
  annote =	{Keywords: Polyomino, digital geometry, decision tree, lattice, HV-convexity, convexity}
}
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