20 Search Results for "Arkin, Esther M."

Document
DOI: 10.4230/LIPIcs.STACS.2026.53
Maximum Reachability Orientation of Mixed Graphs

Authors: Florian Hörsch

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We aim to find orientations of mixed graphs optimizing the total reachability, a problem that has applications in causality and biology. For given a digraph D, we use P(D) for the set of ordered pairs of distinct vertices in V(D) and we define κ_D:P(D) → {0,1} by κ_D(u,v) = 1 if v is reachable from u in D, and κ_D(u,v) = 0, otherwise. We use R(D) = ∑_{(u,v) ∈ P(D)}κ_D(u,v). Now, given a mixed graph G, we aim to find an orientation x⃑{G} of G that maximizes R(x⃑{G}). Hakimi, Schmeichel, and Young proved that the problem can be solved in polynomial time when restricted to undirected inputs. They inquired about the complexity in mixed graphs. We answer this question by showing that this problem is NP-hard, and, moreover, APX-hard. We then develop a finer understanding of how quickly the problem becomes difficult when going from undirected to mixed graphs. To this end, we consider the parameterized complexity of the problem with respect to the number k of preoriented arcs of G, a poorly studied form of parameterization. We show that the problem can be solved in time n^{O(k)} and that a (1-ε)-approximation can be computed in time f(k,ε)n^{O(1)} for any ε > 0.
Cite as

Florian Hörsch. Maximum Reachability Orientation of Mixed Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{horsch:LIPIcs.STACS.2026.53,
  author =	{H\"{o}rsch, Florian},
  title =	{{Maximum Reachability Orientation of Mixed Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{53:1--53:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.53},
  URN =		{urn:nbn:de:0030-drops-255421},
  doi =		{10.4230/LIPIcs.STACS.2026.53},
  annote =	{Keywords: orientations, mixed graphs, reachability, parameterized complexity, approximation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.38
Structural Parameters for Steiner Orientation

Authors: Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, and Manolis Vasilakis

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We consider the Steiner Orientation problem, where we are given as input a mixed graph G = (V,E,A) and a set of k demand pairs (s_i,t_i), i ∈ [k]. The goal is to orient the undirected edges of G in a way that the resulting directed graph has a directed path from s_i to t_i for all i ∈ [k]. We adopt the point of view of structural parameterized complexity and investigate the complexity of Steiner Orientation for standard measures, such as treewidth. Our results indicate that Steiner Orientation is a surprisingly hard problem from this point of view. In particular, our main contributions are the following: 1) We show that Steiner Orientation is NP-complete on instances where the underlying graph has feedback vertex number 2, treewidth 2, pathwidth 3, and vertex integrity 6. 2) We present an XP algorithm parameterized by vertex cover number vc of complexity n^O(vc²). Furthermore, we show that this running time is essentially optimal by proving that a running time of n^o(vc²) would refute the ETH. 3) We consider parameterizations by the number of undirected or directed edges (|E| or |A|) and we observe that the trivial 2^|E| n^O(1)-time algorithm for the former parameter is optimal under the SETH. Complementing this, we show that the problem admits a 2^O(|A|) n^O(1)-time algorithm. In addition to the above, we consider the complexity of Steiner Orientation parameterized by tw+k (FPT), distance to clique (FPT), and vc+k (FPT with a polynomial kernel).
Cite as

Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, and Manolis Vasilakis. Structural Parameters for Steiner Orientation. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2025.38,
  author =	{Hanaka, Tesshu and Lampis, Michael and Melissinos, Nikolaos and Nemery, Edouard and Ono, Hirotaka and Vasilakis, Manolis},
  title =	{{Structural Parameters for Steiner Orientation}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.38},
  URN =		{urn:nbn:de:0030-drops-249461},
  doi =		{10.4230/LIPIcs.ISAAC.2025.38},
  annote =	{Keywords: ETH, Steiner Orientation, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.28
Sliding Squares in Parallel

Authors: Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given n square-shaped modules in a (labeled or unlabeled) start configuration and need to find a schedule of sliding moves to transform it into a desired goal configuration, maintaining connectivity of the configuration at all times. Recent work has aimed at minimizing the total number of moves, resulting in fully sequential schedules that can perform reconfiguration in 𝒪(n²) moves, or 𝒪(nP) for arrangements of bounding box perimeter size P. We provide first results in the sliding square model that exploit parallel motion, performing reconfiguration in worst-case optimal makespan of 𝒪(P). We also provide tight bounds on the complexity of the problem by showing that even deciding the possibility of reconfiguration within makespan 1 is NP-complete in the unlabeled case. In the labeled variant, we note that deciding the same for makespan 2 is NP-complete, while makespan 1 is straightforward.
Cite as

Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner. Sliding Squares in Parallel. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2025.28,
  author =	{A. Akitaya, Hugo and Fekete, S\'{a}ndor P. and Kramer, Peter and Molaei, Saba and Rieck, Christian and Stock, Frederick and Wallner, Tobias},
  title =	{{Sliding Squares in Parallel}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.28},
  URN =		{urn:nbn:de:0030-drops-244961},
  doi =		{10.4230/LIPIcs.ESA.2025.28},
  annote =	{Keywords: Sliding squares, parallel motion, reconfigurability, motion planning, multi-agent path finding, makespan, swarm robotics, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.75
An Improved Bound for Plane Covering Paths

Authors: Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist, Michiel Smid, Diane Souvaine, and Leonidas Theocharous

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A covering path for a finite set P of points in the plane is a polygonal path such that every point of P lies on a segment of the path. The vertices of the path need not be at points of P. A covering path is plane if its segments do not cross each other. Let π(n) be the minimum number such that every set of n points in the plane admits a plane covering path with at most π(n) segments. We prove that π(n) ≤ ⌈6n/7⌉. This improves the previous best-known upper bound of ⌈21n/22⌉, due to Biniaz (SoCG 2023). Our proof is constructive and yields a simple O(n log n)-time algorithm for computing a plane covering path.
Cite as

Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist, Michiel Smid, Diane Souvaine, and Leonidas Theocharous. An Improved Bound for Plane Covering Paths. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 75:1-75:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2025.75,
  author =	{A. Akitaya, Hugo and Aloupis, Greg and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Gavoille, Cyril and Iacono, John and Kleist, Linda and Smid, Michiel and Souvaine, Diane and Theocharous, Leonidas},
  title =	{{An Improved Bound for Plane Covering Paths}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{75:1--75:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.75},
  URN =		{urn:nbn:de:0030-drops-245432},
  doi =		{10.4230/LIPIcs.ESA.2025.75},
  annote =	{Keywords: Covering Path, Upper Bound, Simple Algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.23
Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter

Authors: Gianmarco Picarella, Marc van Kreveld, Frank Staals, and Sjoerd de Vries

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We study the problem of computing a convex region with bounded area and diameter that contains the maximum number of points from a given point set P. We show that this problem can be solved in O(n⁶k) time and O(n³k) space, where n is the size of P and k is the maximum number of points in the found region. We experimentally compare this new algorithm with an existing algorithm that does the same but without the diameter constraint, which runs in O(n³k) time. For the new algorithm, we use different diameters. We use both synthetic data and data from an application in cancer detection, which motivated our research.
Cite as

Gianmarco Picarella, Marc van Kreveld, Frank Staals, and Sjoerd de Vries. Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{picarella_et_al:LIPIcs.ESA.2025.23,
  author =	{Picarella, Gianmarco and van Kreveld, Marc and Staals, Frank and de Vries, Sjoerd},
  title =	{{Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.23},
  URN =		{urn:nbn:de:0030-drops-244919},
  doi =		{10.4230/LIPIcs.ESA.2025.23},
  annote =	{Keywords: convex polygon, dynamic programming, implementation}
}
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.39
Sweeping a Domain with Line-Of-Sight Between Covisible Agents

Authors: Kien C. Huynh, Joseph S. B. Mitchell, and Valentin Polishchuk

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

Abstract
We consider sweeping a polygonal domain using variable-length segments whose endpoints can be considered to be mobile agents moving with bounded speeds; a point in the domain is swept when it belongs to one of the segments. The objective is to sweep the domain as quickly as possible. We show that the problem is NP-hard even in simple polygons and even for a single segment (two agents), and give constant-factor approximation algorithms, both for simple polygons and polygons with holes. Our approximations are obtained by introducing a new type of "window partition" of the polygon, which may find other applications. For domains with holes, our results are based on a non-trivial topological argument proving a surprising fact: a connected subset of the domain, whose points are swept but not directly touched by the agents, may contain at most one hole.
Cite as

Kien C. Huynh, Joseph S. B. Mitchell, and Valentin Polishchuk. Sweeping a Domain with Line-Of-Sight Between Covisible Agents. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 39:1-39:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huynh_et_al:LIPIcs.WADS.2025.39,
  author =	{Huynh, Kien C. and Mitchell, Joseph S. B. and Polishchuk, Valentin},
  title =	{{Sweeping a Domain with Line-Of-Sight Between Covisible Agents}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{39:1--39:22},
  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.39},
  URN =		{urn:nbn:de:0030-drops-242706},
  doi =		{10.4230/LIPIcs.WADS.2025.39},
  annote =	{Keywords: Polygon sweeping, collaborating agents, motion coordination, makespan optimization}
}
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
DOI: 10.4230/LIPIcs.SoCG.2025.53
A PTAS for TSP with Neighbourhoods over Parallel Line Segments

Authors: Benyamin Ghaseminia and Mohammad R. Salavatipour

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We consider the Travelling Salesman Problem with Neighbourhoods (TSPN) on the Euclidean plane (ℝ²) and present a Polynomial-Time Approximation Scheme (PTAS) when the neighbourhoods are parallel line segments with lengths between [1, λ] for any constant value λ ≥ 1. In TSPN (which generalizes classic TSP), each client represents a set (or neighbourhood) of points in a metric and the goal is to find a minimum cost TSP tour that visits at least one point from each client set. In the Euclidean setting, each neighbourhood is a region on the plane. TSPN is significantly more difficult than classic TSP even in the Euclidean setting, as it captures group TSP. A notable case of TSPN is when each neighbourhood is a line segment. Although there are PTASs for when neighbourhoods are fat objects (with limited overlap), TSPN over line segments is APX-hard even if all the line segments have unit length. For parallel (unit) line segments, the best approximation factor is 3√2 from more than two decades ago. The PTAS we present in this paper settles the approximability of this case of the problem. Our algorithm finds a (1 + ε)-factor approximation for an instance of the problem for n segments with lengths in [1,λ] in time n^O(λ/ε³).
Cite as

Benyamin Ghaseminia and Mohammad R. Salavatipour. A PTAS for TSP with Neighbourhoods over Parallel Line Segments. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghaseminia_et_al:LIPIcs.SoCG.2025.53,
  author =	{Ghaseminia, Benyamin and Salavatipour, Mohammad R.},
  title =	{{A PTAS for TSP with Neighbourhoods over Parallel Line Segments}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.53},
  URN =		{urn:nbn:de:0030-drops-232058},
  doi =		{10.4230/LIPIcs.SoCG.2025.53},
  annote =	{Keywords: Approximation Scheme, TSP Neighbourhood, Parallel line segments}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2025.85
Finding Shortest Reconfiguration Sequences for Modular Robots (Media Exposition)

Authors: UML Modular Robotics Group, Hugo A. Akitaya, Andrew Clements, Sam Downey, Jonathan Eisenbies, Soham Samanta, Gabriel Shahrouzi, and Frederick Stock

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
This paper introduces a set of tools built to help researchers design algorithms for modular robots. These tools can brute force solutions to specific reconfigurations, visualize movements of modular robots, and can be used to design specific configurations of robots. Multiple models of modular robots are supported, and can be added by users.
Cite as

UML Modular Robotics Group, Hugo A. Akitaya, Andrew Clements, Sam Downey, Jonathan Eisenbies, Soham Samanta, Gabriel Shahrouzi, and Frederick Stock. Finding Shortest Reconfiguration Sequences for Modular Robots (Media Exposition). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 85:1-85:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{umlmodularroboticsgroup_et_al:LIPIcs.SoCG.2025.85,
  author =	{UML Modular Robotics Group and A. Akitaya, Hugo and Clements, Andrew and Downey, Sam and Eisenbies, Jonathan and Samanta, Soham and Shahrouzi, Gabriel and Stock, Frederick},
  title =	{{Finding Shortest Reconfiguration Sequences for Modular Robots}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{85:1--85:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.85},
  URN =		{urn:nbn:de:0030-drops-232371},
  doi =		{10.4230/LIPIcs.SoCG.2025.85},
  annote =	{Keywords: modular reconfigurable robots, sliding cube model, reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.18
Finding a Shortest Curve That Separates Few Objects from Many

Authors: Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present a fixed-parameter tractable (FPT) algorithm to find a shortest curve that encloses a set of k required objects in the plane while paying a penalty for enclosing unwanted objects. The input is a set of interior-disjoint simple polygons in the plane, where k of the polygons are required to be enclosed and the remaining optional polygons have non-negative penalties. The goal is to find a closed curve that is disjoint from the polygon interiors and encloses the k required polygons, while minimizing the length of the curve plus the penalties of the enclosed optional polygons. If the penalties are high, the output is a shortest curve that separates the required polygons from the others. The problem is NP-hard if k is not fixed, even in very special cases. The runtime of our algorithm is O(3^k n³), where n is the number of vertices of the input polygons. We extend the result to a graph version of the problem where the input is a connected plane graph with positive edge weights. There are k required faces; the remaining faces are optional and have non-negative penalties. The goal is to find a closed walk in the graph that encloses the k required faces, while minimizing the weight of the walk plus the penalties of the enclosed optional faces. We also consider an inverted version of the problem where the required objects must lie outside the curve. Our algorithms solve some other well-studied problems, such as geometric knapsack.
Cite as

Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote. Finding a Shortest Curve That Separates Few Objects from Many. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SoCG.2025.18,
  author =	{Biedl, Therese and Colin de Verdi\`{e}re, \'{E}ric and Frati, Fabrizio and Lubiw, Anna and Rote, G\"{u}nter},
  title =	{{Finding a Shortest Curve That Separates Few Objects from Many}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.18},
  URN =		{urn:nbn:de:0030-drops-231701},
  doi =		{10.4230/LIPIcs.SoCG.2025.18},
  annote =	{Keywords: Enclosure, curve, separation, weakly simple polygon, Euler tour}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.47
Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines

Authors: Klaus Heeger and Hendrik Molter

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In this work, we study the computational (parameterized) complexity of P∣ r_j, p_j = p ∣∑ w_j U_j. Here, we are given m identical parallel machines and n jobs with equal processing time, each characterized by a release date, a due date, and a weight. The task is to find a feasible schedule, that is, an assignment of the jobs to starting times on machines, such that no job starts before its release date and no machine processes several jobs at the same time, that minimizes the weighted number of tardy jobs. A job is considered tardy if it finishes after its due date. Our main contribution is showing that P∣r_j, p_j = p∣∑ U_j (the unweighted version of the problem) is NP-hard and W[2]-hard when parameterized by the number of machines. The former resolves an open problem in Note 2.1.19 by Kravchenko and Werner [Journal of Scheduling, 2011] and Open Problem 2 by Sgall [ESA, 2012], and the latter resolves Open Problem 7 by Mnich and van Bevern [Computers & Operations Research, 2018]. Furthermore, our result shows that the known XP-algorithm by Baptiste et al. [4OR, 2004] for P∣r_j, p_j = p∣∑ w_j U_j parameterized by the number of machines is optimal from a classification standpoint. On the algorithmic side, we provide alternative running time bounds for the above-mentioned known XP-algorithm. Our analysis shows that P∣r_j, p_j = p∣∑ w_j U_j is contained in XP when parameterized by the processing time, and that it is contained in FPT when parameterized by the combination of the number of machines and the processing time. Finally, we give an FPT-algorithm for P∣r_j, p_j = p∣∑ w_j U_j parameterized by the number of release dates or the number of due dates. With this work, we lay out the foundation for a systematic study of the parameterized complexity of P∣r_j, p_j = p∣∑ w_j U_j.
Cite as

Klaus Heeger and Hendrik Molter. Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{heeger_et_al:LIPIcs.STACS.2025.47,
  author =	{Heeger, Klaus and Molter, Hendrik},
  title =	{{Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.47},
  URN =		{urn:nbn:de:0030-drops-228736},
  doi =		{10.4230/LIPIcs.STACS.2025.47},
  annote =	{Keywords: Scheduling, Identical Parallel Machines, Weighted Number of Tardy Jobs, Uniform Processing Times, Release Dates, NP-hard Problems, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.5
Edge-Minimum Walk of Modular Length in Polynomial Time

Authors: Antoine Amarilli, Benoît Groz, and Nicole Wein

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study the problem of finding, in a directed graph, an st-walk of length r od q which is edge-minimum, i.e., uses the smallest number of distinct edges. Despite the vast literature on paths and cycles with modularity constraints, to the best of our knowledge we are the first to study this problem. Our main result is a polynomial-time algorithm that solves this task when r and q are constants. We also show how our proof technique gives an algorithm to solve a generalization of the well-known Directed Steiner Network problem, in which connections between endpoint pairs are required to satisfy modularity constraints on their length. Our algorithm is polynomial when the number of endpoint pairs and the modularity constraints on the pairs are constants. In this version of the article, proofs and examples are omitted because of space constraints. Detailed proofs are available in the full version [Antoine Amarilli et al., 2024].
Cite as

Antoine Amarilli, Benoît Groz, and Nicole Wein. Edge-Minimum Walk of Modular Length in Polynomial Time. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amarilli_et_al:LIPIcs.ITCS.2025.5,
  author =	{Amarilli, Antoine and Groz, Beno\^{i}t and Wein, Nicole},
  title =	{{Edge-Minimum Walk of Modular Length in Polynomial Time}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{5:1--5:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.5},
  URN =		{urn:nbn:de:0030-drops-226330},
  doi =		{10.4230/LIPIcs.ITCS.2025.5},
  annote =	{Keywords: Directed Steiner Network, Modularity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.7
Cutting Polygons into Small Pieces with Chords: Laser-Based Localization

Authors: Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into small-size pieces, using the chords of the polygon. Several versions are considered, depending on the definition of the "size" of a piece. In particular, we consider the area, the diameter, and the radius of the largest inscribed circle as a measure of the size of a piece. We also consider different objectives, either minimizing the maximum size of a piece for a given number of chords, or minimizing the number of chords that achieve a given size threshold for the pieces. We give hardness results for polygons with holes and approximation algorithms for multiple variants of the problem.
Cite as

Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth. Cutting Polygons into Small Pieces with Chords: Laser-Based Localization. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.ESA.2020.7,
  author =	{Arkin, Esther M. and Das, Rathish and Gao, Jie and Goswami, Mayank and Mitchell, Joseph S. B. and Polishchuk, Valentin and T\'{o}th, Csaba D.},
  title =	{{Cutting Polygons into Small Pieces with Chords: Laser-Based Localization}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.7},
  URN =		{urn:nbn:de:0030-drops-128736},
  doi =		{10.4230/LIPIcs.ESA.2020.7},
  annote =	{Keywords: Polygon partition, Arrangements, Visibility, Localization}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.7
Computing β-Stretch Paths in Drawings of Graphs

Authors: Esther M. Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen Kobourov, and Joseph S. B. Mitchell

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π=f(P), is β-stretch if π is a simple (non-self-intersecting) curve, and for every pair of distinct points p∈P and q∈P, the length of the sub-curve of π connecting f(p) with f(q) is at most β||f(p)-f(q)‖, where ‖.‖ denotes the Euclidean distance. We introduce and study the β-stretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a β-stretch path P connecting s and t. The βSP also asks that we output P if it exists. The βSP quantifies a notion of "near straightness" for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a β-stretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NP-complete. We complement this result by giving a quasi-polynomial time algorithm, that for a given ε>0, β∈O(poly(log |V(G)|)), and s,t∈V(G), outputs a β-stretch path between s and t, if a (1-ε)β-stretch path between s and t exists in the drawing.
Cite as

Esther M. Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen Kobourov, and Joseph S. B. Mitchell. Computing β-Stretch Paths in Drawings of Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.SWAT.2020.7,
  author =	{Arkin, Esther M. and Sahneh, Faryad Darabi and Efrat, Alon and Frank, Fabian and Fulek, Radoslav and Kobourov, Stephen and Mitchell, Joseph S. B.},
  title =	{{Computing \beta-Stretch Paths in Drawings of Graphs}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.7},
  URN =		{urn:nbn:de:0030-drops-122540},
  doi =		{10.4230/LIPIcs.SWAT.2020.7},
  annote =	{Keywords: stretch factor, dilation, geometric spanners}
}
  • Refine by Type
  • 20 Document/PDF
  • 13 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 12 2025
  • 2 2020
  • 1 2019
  • 1 2018
  • Show More...

  • Refine by Author
  • 6 Arkin, Esther M.
  • 6 Mitchell, Joseph S. B.
  • 4 Polishchuk, Valentin
  • 3 A. Akitaya, Hugo
  • 2 Carmi, Paz
  • Show More...

  • Refine by Series/Journal
  • 19 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 8 Theory of computation → Computational geometry
  • 4 Theory of computation → Parameterized complexity and exact algorithms
  • 3 Theory of computation → Approximation algorithms analysis
  • 2 Mathematics of computing → Combinatorial algorithms
  • 2 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 1 2-point distance queries
  • 1 Algorithms
  • 1 Approximation Scheme
  • 1 Approximation algorithm
  • 1 Approximation algorithms
  • 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