5 Search Results for "Hagedoorn, Mart"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.1
Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics

Authors: Kinter Ren and Mohammad R. Salavatipour

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

Abstract
In this paper we look at various extensions of the classic Traveling Salesman Problem (TSP) on graphs with bounded doubling dimension and bounded treewidth and present approximation schemes for them. Suppose we are given a weighted graph G = (V,E) with a start node s ∈ V, distances on the edges d:E → ℚ^+ and integer k. In k-stroll problem the goal is to find a path from s of minimum length that visits at least k vertices. In k-path we are given an additional end node t ∈ V and the path is supposed to go from s to t. The dual problem to k-stroll is the rooted orienteering in which instead of k we are given a budget B and the goal is to find a walk of length at most B starting at s that visits as many vertices as possible. In the point-to-point orienteering (P2P orienteering) we are given start and end nodes s,t and the walk is supposed to start at s and end at t. In the deadline TSP (which generalizes P2P orienteering) we are given a deadline D(v) for each v ∈ V and the goal is to find a walk starting at s that visits as many vertices as possible before their deadline (where the visit time of a node is the distance travelled from s to that node). The best approximation for rooted orienteering (or P2P orienteering) is (2+ε)-approximation [Chekuri et al., 2012] and O(log n)-approximation for deadline TSP [Nikhil Bansal et al., 2004]. For Euclidean metrics of fixed dimension, Chen and Har-Peled present [Chen and Har-Peled, 2008] a PTAS for rooted orienteering. There is no known approximation scheme for deadline TSP for any metric (not even trees). Our main result is the first approximation scheme for deadline TSP on metrics with bounded doubling dimension (which includes Euclidean metrics). To do so we first we present a quasi-polynomial time approximation scheme for k-path and P2P orienteering on such metrics. More specifically, if G is a metric with doubling dimension κ and aspect ratio Δ, we present a (1+ε)-approximation that runs in time n^{O((logΔ/ε) ^{2κ+1})}. Building upon these, we obtain an approximation scheme for deadline TSP when the distances and deadlines are integer which runs in time n^{O((log Δ/ε) ^{2κ+2})}. The same approach also implies a bicriteria (1+ε,1+ε)-approximation for deadline TSP for when distances and deadlines are in ℚ^+. For graphs with bounded treewidth ω we show how to solve k-path and P2P orienteering exactly in polynomial time and a (1+ε)-approximation for deadline TSP in time n^O((ωlogΔ/ε)²).
Cite as

Kinter Ren and Mohammad R. Salavatipour. Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ren_et_al:LIPIcs.APPROX/RANDOM.2025.1,
  author =	{Ren, Kinter and Salavatipour, Mohammad R.},
  title =	{{Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.1},
  URN =		{urn:nbn:de:0030-drops-243678},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.1},
  annote =	{Keywords: Deadline Traveling Salesman Problem, Orienteering, Doubling Metrics, Approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.34
Link Diameter, Radius and 2-Point Link Distance Queries in Polygonal Domains

Authors: Mart Hagedoorn and Valentin Polishchuk

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We show how to preprocess a polygonal domain with holes so that the link distance (the number of links in a minimum-link path) between two query points in the domain can be reported efficiently. Using our data structures, the link diameter of the domain (i.e., the maximum number of links that may be required in a minimum-link path between two points in the domain) as well as the link center and radius of the domain (i.e., the point minimizing the maximum link distance to the furthest point in the domain and this maximum link distance) can be found in polynomial time. We also give a simpler algorithm for finding the link diameter, not using the link distance query structures. Answering 2-point link distance queries and computing the link diameter/radius/center in polygonal domains have been open questions since these problems were studied for simple polygons in the 90’s.
Cite as

Mart Hagedoorn and Valentin Polishchuk. Link Diameter, Radius and 2-Point Link Distance Queries in Polygonal Domains. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hagedoorn_et_al:LIPIcs.WADS.2025.34,
  author =	{Hagedoorn, Mart and Polishchuk, Valentin},
  title =	{{Link Diameter, Radius and 2-Point Link Distance Queries in Polygonal Domains}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.34},
  URN =		{urn:nbn:de:0030-drops-242659},
  doi =		{10.4230/LIPIcs.WADS.2025.34},
  annote =	{Keywords: Minimum-link paths, link distance, diameter, center, radius, 2-point distance queries}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2024.83
Computing Maximum Polygonal Packings in Convex Polygons Using Best-Fit, Genetic Algorithms and ILPs (CG Challenge)

Authors: Alkan Atak, Kevin Buchin, Mart Hagedoorn, Jona Heinrichs, Karsten Hogreve, Guangping Li, and Patrick Pawelczyk

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

Abstract
Given a convex region P and a set of irregular polygons with associated profits, the Maximum Polygon Packing Problem seeks a non-overlapping packing of a subset of the polygons (without rotations) into P maximizing the profit of the packed polygons. Depending on the size of an instance, we use different algorithmic solutions: integer linear programs for small instances, genetic algorithms for medium-sized instances and a best-fit approach for large instances. For packing rectilinear polygons we provide a dedicated best-fit algorithm.
Cite as

Alkan Atak, Kevin Buchin, Mart Hagedoorn, Jona Heinrichs, Karsten Hogreve, Guangping Li, and Patrick Pawelczyk. Computing Maximum Polygonal Packings in Convex Polygons Using Best-Fit, Genetic Algorithms and ILPs (CG Challenge). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 83:1-83:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{atak_et_al:LIPIcs.SoCG.2024.83,
  author =	{Atak, Alkan and Buchin, Kevin and Hagedoorn, Mart and Heinrichs, Jona and Hogreve, Karsten and Li, Guangping and Pawelczyk, Patrick},
  title =	{{Computing Maximum Polygonal Packings in Convex Polygons Using Best-Fit, Genetic Algorithms and ILPs}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{83:1--83: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.83},
  URN =		{urn:nbn:de:0030-drops-200283},
  doi =		{10.4230/LIPIcs.SoCG.2024.83},
  annote =	{Keywords: Polygon Packing, Nesting Problem, Genetic Algorithm, Integer Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.25
Dots & Boxes Is PSPACE-Complete

Authors: Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, and Max van Mulken

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Exactly 20 years ago at MFCS, Demaine posed the open problem whether the game of Dots & Boxes is PSPACE-complete. Dots & Boxes has been studied extensively, with for instance a chapter in Berlekamp et al. Winning Ways for Your Mathematical Plays, a whole book on the game The Dots and Boxes Game: Sophisticated Child’s Play by Berlekamp, and numerous articles in the Games of No Chance series. While known to be NP-hard, the question of its complexity remained open. We resolve this question, proving that the game is PSPACE-complete by a reduction from a game played on propositional formulas.
Cite as

Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, and Max van Mulken. Dots & Boxes Is PSPACE-Complete. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.MFCS.2021.25,
  author =	{Buchin, Kevin and Hagedoorn, Mart and Kostitsyna, Irina and van Mulken, Max},
  title =	{{Dots \& Boxes Is PSPACE-Complete}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{25:1--25:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.25},
  URN =		{urn:nbn:de:0030-drops-144657},
  doi =		{10.4230/LIPIcs.MFCS.2021.25},
  annote =	{Keywords: Dots \& Boxes, PSPACE-complete, combinatorial game}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.79
Dots & Polygons (Media Exposition)

Authors: Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, and Leo van Schooten

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

Abstract
We present a new game, Dots & Polygons, played on a planar point set. We prove that its NP-hard and discuss strategies for the case when the point set is in convex position.
Cite as

Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, and Leo van Schooten. Dots & Polygons (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 79:1-79:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2020.79,
  author =	{Buchin, Kevin and Hagedoorn, Mart and Kostitsyna, Irina and van Mulken, Max and Rensen, Jolan and van Schooten, Leo},
  title =	{{Dots \& Polygons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{79:1--79:4},
  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.79},
  URN =		{urn:nbn:de:0030-drops-122371},
  doi =		{10.4230/LIPIcs.SoCG.2020.79},
  annote =	{Keywords: Dots \& Boxes, NP-hard, game, cycle packing}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2024
  • 1 2021
  • 1 2020

  • Refine by Author
  • 4 Hagedoorn, Mart
  • 3 Buchin, Kevin
  • 2 Kostitsyna, Irina
  • 2 van Mulken, Max
  • 1 Atak, Alkan
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Packing and covering problems
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 2 Dots & Boxes
  • 1 2-point distance queries
  • 1 Approximation algorithm
  • 1 Deadline Traveling Salesman Problem
  • 1 Doubling Metrics
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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