21 Search Results for "Mitchell, Joseph"

Document
DOI: 10.4230/LIPIcs.WABI.2024.23
AlfaPang: Alignment Free Algorithm for Pangenome Graph Construction

Authors: Adam Cicherski, Anna Lisiecka, and Norbert Dojer

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
The success of pangenome-based approaches to genomics analysis depends largely on the existence of efficient methods for constructing pangenome graphs that are applicable to large genome collections. In the current paper we present AlfaPang, a new pangenome graph building algorithm. AlfaPang is based on a novel alignment-free approach that allows to construct pangenome graphs using significantly less computational resources than state-of-the-art tools. The code of AlfaPang is freely available at https://github.com/AdamCicherski/AlfaPang.
Cite as

Adam Cicherski, Anna Lisiecka, and Norbert Dojer. AlfaPang: Alignment Free Algorithm for Pangenome Graph Construction. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cicherski_et_al:LIPIcs.WABI.2024.23,
  author =	{Cicherski, Adam and Lisiecka, Anna and Dojer, Norbert},
  title =	{{AlfaPang: Alignment Free Algorithm for Pangenome Graph Construction}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.23},
  URN =		{urn:nbn:de:0030-drops-206673},
  doi =		{10.4230/LIPIcs.WABI.2024.23},
  annote =	{Keywords: pangenome, variation graph, genome alignment, population genomics}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.47
Robustly Guarding Polygons

Authors: Rathish Das, Omrit Filtser, Matthew J. Katz, and Joseph S.B. Mitchell

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

Abstract
We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point guards in a polygon is a notoriously challenging area of investigation, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor guarantees.
Cite as

Rathish Das, Omrit Filtser, Matthew J. Katz, and Joseph S.B. Mitchell. Robustly Guarding Polygons. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.SoCG.2024.47,
  author =	{Das, Rathish and Filtser, Omrit and Katz, Matthew J. and Mitchell, Joseph S.B.},
  title =	{{Robustly Guarding Polygons}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{47:1--47:17},
  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.47},
  URN =		{urn:nbn:de:0030-drops-199928},
  doi =		{10.4230/LIPIcs.SoCG.2024.47},
  annote =	{Keywords: geometric optimization, approximation algorithms, guarding}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.27
Optimizing Visibility-Based Search in Polygonal Domains

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

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
Given a geometric domain P, visibility-based search problems seek routes for one or more mobile agents ("watchmen") to move within P in order to be able to see a portion (or all) of P, while optimizing objectives, such as the length(s) of the route(s), the size (e.g., area or volume) of the portion seen, the probability of detecting a target distributed within P according to a prior distribution, etc. The classic watchman route problem seeks a shortest route for an observer, with omnidirectional vision, to see all of P. In this paper we study bicriteria optimization problems for a single mobile agent within a polygonal domain P in the plane, with the criteria of route length and area seen. Specifically, we address the problem of computing a minimum length route that sees at least a specified area of P (minimum length, for a given area quota). We also study the problem of computing a length-constrained route that sees as much area as possible. We provide hardness results and approximation algorithms. In particular, for a simple polygon P we provide the first fully polynomial-time approximation scheme for the problem of computing a shortest route seeing an area quota, as well as a (slightly more efficient) polynomial dual approximation. We also consider polygonal domains P (with holes) and the special case of a planar domain consisting of a union of lines. Our results yield the first approximation algorithms for computing a time-optimal search route in P to guarantee some specified probability of detection of a static target within P, randomly distributed in P according to a given prior distribution.
Cite as

Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, and Valentin Polishchuk. Optimizing Visibility-Based Search in Polygonal Domains. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{huynh_et_al:LIPIcs.SWAT.2024.27,
  author =	{Huynh, Kien C. and Mitchell, Joseph S. B. and Nguyen, Linh and Polishchuk, Valentin},
  title =	{{Optimizing Visibility-Based Search in Polygonal Domains}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.27},
  URN =		{urn:nbn:de:0030-drops-200671},
  doi =		{10.4230/LIPIcs.SWAT.2024.27},
  annote =	{Keywords: Quota watchman route problem, budgeted watchman route problem, visibility-based search, approximation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.18
Dynamic L-Budget Clustering of Curves

Authors: Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, and Sampson Wong

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
A key goal of clustering is data reduction. In center-based clustering of complex objects therefore not only the number of clusters but also the complexity of the centers plays a crucial role. We propose L-Budget Clustering as unifying perspective on this task, optimizing the clustering under the constraint that the summed complexity of all centers is at most L. We present algorithms for clustering planar curves under the Fréchet distance, but note that our algorithms more generally apply to objects in metric spaces if a notion of simplification of objects is applicable. A scenario in which data reduction is of particular importance is when the space is limited. Our main result is an efficient (8 + ε)-approximation algorithm with a (1 + ε)-resource augmentation that maintains an L-budget clustering under insertion of curves using only O(Lε^{-1}) space and O^*(L³log(L) + L²log(r^*/r₀)) time where O^* hides factors of ε^{-1}.
Cite as

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, and Sampson Wong. Dynamic L-Budget Clustering of Curves. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SWAT.2024.18,
  author =	{Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Pl\"{a}tz, Lukas and Thiel, Lea and Wong, Sampson},
  title =	{{Dynamic L-Budget Clustering of Curves}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.18},
  URN =		{urn:nbn:de:0030-drops-200588},
  doi =		{10.4230/LIPIcs.SWAT.2024.18},
  annote =	{Keywords: clustering, streaming algorithm, polygonal curves, Fr\'{e}chet distance, storage efficiency, simplification, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.49
The Geodesic Edge Center of a Simple Polygon

Authors: Anna Lubiw and Anurag Murty Naredla

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
The geodesic edge center of a polygon is a point c inside the polygon that minimizes the maximum geodesic distance from c to any edge of the polygon, where geodesic distance is the shortest path distance inside the polygon. We give a linear-time algorithm to find a geodesic edge center of a simple polygon. This improves on the previous O(n log n) time algorithm by Lubiw and Naredla [European Symposium on Algorithms, 2021]. The algorithm builds on an algorithm to find the geodesic vertex center of a simple polygon due to Pollack, Sharir, and Rote [Discrete & Computational Geometry, 1989] and an improvement to linear time by Ahn, Barba, Bose, De Carufel, Korman, and Oh [Discrete & Computational Geometry, 2016]. The geodesic edge center can easily be found from the geodesic farthest-edge Voronoi diagram of the polygon. Finding that Voronoi diagram in linear time is an open question, although the geodesic nearest edge Voronoi diagram (the medial axis) can be found in linear time. As a first step of our geodesic edge center algorithm, we give a linear-time algorithm to find the geodesic farthest-edge Voronoi diagram restricted to the polygon boundary.
Cite as

Anna Lubiw and Anurag Murty Naredla. The Geodesic Edge Center of a Simple Polygon. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lubiw_et_al:LIPIcs.SoCG.2023.49,
  author =	{Lubiw, Anna and Naredla, Anurag Murty},
  title =	{{The Geodesic Edge Center of a Simple Polygon}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.49},
  URN =		{urn:nbn:de:0030-drops-178994},
  doi =		{10.4230/LIPIcs.SoCG.2023.49},
  annote =	{Keywords: geodesic center of polygon, farthest edges, farthest-segment Voronoi diagram}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.51
On Flipping the Fréchet Distance

Authors: Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
The classical and extensively-studied Fréchet distance between two curves is defined as an inf max, where the infimum is over all traversals of the curves, and the maximum is over all concurrent positions of the two agents. In this article we investigate a "flipped" Fréchet measure defined by a sup min - the supremum is over all traversals of the curves, and the minimum is over all concurrent positions of the two agents. This measure produces a notion of "social distance" between two curves (or general domains), where agents traverse curves while trying to stay as far apart as possible. We first study the flipped Fréchet measure between two polygonal curves in one and two dimensions, providing conditional lower bounds and matching algorithms. We then consider this measure on polygons, where it denotes the minimum distance that two agents can maintain while restricted to travel in or on the boundary of the same polygon. We investigate several variants of the problem in this setting, for some of which we provide linear time algorithms. Finally, we consider this measure on graphs. We draw connections between our proposed flipped Fréchet measure and existing related work in computational geometry, hoping that our new measure may spawn investigations akin to those performed for the Fréchet distance, and into further interesting problems that arise.
Cite as

Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk. On Flipping the Fréchet Distance. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 51:1-51:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.ITCS.2023.51,
  author =	{Filtser, Omrit and Goswami, Mayank and Mitchell, Joseph S. B. and Polishchuk, Valentin},
  title =	{{On Flipping the Fr\'{e}chet Distance}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{51:1--51:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.51},
  URN =		{urn:nbn:de:0030-drops-175548},
  doi =		{10.4230/LIPIcs.ITCS.2023.51},
  annote =	{Keywords: curves, polygons, distancing measure}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.67
The Dispersive Art Gallery Problem

Authors: Christian Rieck and Christian Scheffer

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We introduce a new variant of the art gallery problem that comes from safety issues. In this variant we are not interested in guard sets of smallest cardinality, but in guard sets with largest possible distances between these guards. To the best of our knowledge, this variant has not been considered before. We call it the Dispersive Art Gallery Problem. In particular, in the dispersive art gallery problem we are given a polygon 𝒫 and a real number 𝓁, and want to decide whether 𝒫 has a guard set such that every pair of guards in this set is at least a distance of 𝓁 apart. In this paper, we study the vertex guard variant of this problem for the class of polyominoes. We consider rectangular visibility and distances as geodesics in the L₁-metric. Our results are as follows. We give a (simple) thin polyomino such that every guard set has minimum pairwise distances of at most 3. On the positive side, we describe an algorithm that computes guard sets for simple polyominoes that match this upper bound, i.e., the algorithm constructs worst-case optimal solutions. We also study the computational complexity of computing guard sets that maximize the smallest distance between all pairs of guards within the guard sets. We prove that deciding whether there exists a guard set realizing a minimum pairwise distance for all pairs of guards of at least 5 in a given polyomino is NP-complete. We were also able to find an optimal dynamic programming approach that computes a guard set that maximizes the minimum pairwise distance between guards in tree-shaped polyominoes, i.e., computes optimal solutions; due to space constraints, details can be found in the full version of our paper [Christian Rieck and Christian Scheffer, 2022]. Because the shapes constructed in the NP-hardness reduction are thin as well (but have holes), this result completes the case for thin polyominoes.
Cite as

Christian Rieck and Christian Scheffer. The Dispersive Art Gallery Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 67:1-67:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rieck_et_al:LIPIcs.ISAAC.2022.67,
  author =	{Rieck, Christian and Scheffer, Christian},
  title =	{{The Dispersive Art Gallery Problem}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{67:1--67:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.67},
  URN =		{urn:nbn:de:0030-drops-173522},
  doi =		{10.4230/LIPIcs.ISAAC.2022.67},
  annote =	{Keywords: Art gallery, dispersion, polyominoes, NP-completeness, r-visibility, vertex guards, L₁-metric, worst-case optimal}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.7
1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete

Authors: Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff

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

Abstract
Consider n²-1 unit-square blocks in an n × n square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable - a variation of Rush Hour with only 1 × 1 cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical 1 × 2 and horizontal 2 × 1 movable blocks and 4-color Subway Shuffle.
Cite as

Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7,
  author =	{Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi},
  title =	{{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{7:1--7:14},
  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.7},
  URN =		{urn:nbn:de:0030-drops-127681},
  doi =		{10.4230/LIPIcs.FUN.2021.7},
  annote =	{Keywords: puzzles, sliding blocks, PSPACE-hardness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.1
Planar Bichromatic Bottleneck Spanning Trees

Authors: A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, and Joseph S. B. Mitchell

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

Abstract
Given a set P of n red and blue points in the plane, a planar bichromatic spanning tree of P is a geometric spanning tree of P, such that each edge connects between a red and a blue point, and no two edges intersect. In the bottleneck planar bichromatic spanning tree problem, the goal is to find a planar bichromatic spanning tree T, such that the length of the longest edge in T is minimized. In this paper, we show that this problem is NP-hard for points in general position. Our main contribution is a polynomial-time (8√2)-approximation algorithm, by showing that any bichromatic spanning tree of bottleneck λ can be converted to a planar bichromatic spanning tree of bottleneck at most 8√2 λ.
Cite as

A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, and Joseph S. B. Mitchell. Planar Bichromatic Bottleneck Spanning Trees. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abuaffash_et_al:LIPIcs.ESA.2020.1,
  author =	{Abu-Affash, A. Karim and Bhore, Sujoy and Carmi, Paz and Mitchell, Joseph S. B.},
  title =	{{Planar Bichromatic Bottleneck Spanning Trees}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{1:1--1:16},
  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.1},
  URN =		{urn:nbn:de:0030-drops-128670},
  doi =		{10.4230/LIPIcs.ESA.2020.1},
  annote =	{Keywords: Approximation Algorithms, Bottleneck Spanning Tree, NP-Hardness}
}
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.SEA.2020.5
Probing a Set of Trajectories to Maximize Captured Information

Authors: Sándor P. Fekete, Alexander Hill, Dominik Krupke, Tyler Mayer, Joseph S. B. Mitchell, Ojas Parekh, and Cynthia A. Phillips

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
We study a trajectory analysis problem we call the Trajectory Capture Problem (TCP), in which, for a given input set T of trajectories in the plane, and an integer k≥ 2, we seek to compute a set of k points ("portals") to maximize the total weight of all subtrajectories of T between pairs of portals. This problem naturally arises in trajectory analysis and summarization. We show that the TCP is NP-hard (even in very special cases) and give some first approximation results. Our main focus is on attacking the TCP with practical algorithm-engineering approaches, including integer linear programming (to solve instances to provable optimality) and local search methods. We study the integrality gap arising from such approaches. We analyze our methods on different classes of data, including benchmark instances that we generate. Our goal is to understand the best performing heuristics, based on both solution time and solution quality. We demonstrate that we are able to compute provably optimal solutions for real-world instances.
Cite as

Sándor P. Fekete, Alexander Hill, Dominik Krupke, Tyler Mayer, Joseph S. B. Mitchell, Ojas Parekh, and Cynthia A. Phillips. Probing a Set of Trajectories to Maximize Captured Information. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SEA.2020.5,
  author =	{Fekete, S\'{a}ndor P. and Hill, Alexander and Krupke, Dominik and Mayer, Tyler and Mitchell, Joseph S. B. and Parekh, Ojas and Phillips, Cynthia A.},
  title =	{{Probing a Set of Trajectories to Maximize Captured Information}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.5},
  URN =		{urn:nbn:de:0030-drops-120796},
  doi =		{10.4230/LIPIcs.SEA.2020.5},
  annote =	{Keywords: Algorithm engineering, optimization, complexity, approximation, trajectories}
}
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}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.32
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}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.6
Network Optimization on Partitioned Pairs of Points

Authors: Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Su Jia, Matthew J. Katz, Tyler Mayer, and Joseph S. B. Mitchell

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Given n pairs of points, S = {{p_1, q_1}, {p_2, q_2}, ..., {p_n, q_n}}, in some metric space, we study the problem of two-coloring the points within each pair, red and blue, to optimize the cost of a pair of node-disjoint networks, one over the red points and one over the blue points. In this paper we consider our network structures to be spanning trees, traveling salesman tours or matchings. We consider several different weight functions computed over the network structures induced, as well as several different objective functions. We show that some of these problems are NP-hard, and provide constant factor approximation algorithms in all cases.
Cite as

Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Su Jia, Matthew J. Katz, Tyler Mayer, and Joseph S. B. Mitchell. Network Optimization on Partitioned Pairs of Points. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.ISAAC.2017.6,
  author =	{Arkin, Esther M. and Banik, Aritra and Carmi, Paz and Citovsky, Gui and Jia, Su and Katz, Matthew J. and Mayer, Tyler and Mitchell, Joseph S. B.},
  title =	{{Network Optimization on Partitioned Pairs of Points}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.6},
  URN =		{urn:nbn:de:0030-drops-82700},
  doi =		{10.4230/LIPIcs.ISAAC.2017.6},
  annote =	{Keywords: Network Optimization, TSP tour, Matching, Spanning Tree, Pairs, Partition, Algorithms, Complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.32
TSP With Locational Uncertainty: The Adversarial Model

Authors: Gui Citovsky, Tyler Mayer, and Joseph S. B. Mitchell

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
In this paper we study a natural special case of the Traveling Salesman Problem (TSP) with point-locational-uncertainty which we will call the adversarial TSP problem (ATSP). Given a metric space (X, d) and a set of subsets R = {R_1, R_2, ... , R_n} : R_i subseteq X, the goal is to devise an ordering of the regions, sigma_R, that the tour will visit such that when a single point is chosen from each region, the induced tour over those points in the ordering prescribed by sigma_R is as short as possible. Unlike the classical locational-uncertainty-TSP problem, which focuses on minimizing the expected length of such a tour when the point within each region is chosen according to some probability distribution, here, we focus on the adversarial model in which once the choice of sigma_R is announced, an adversary selects a point from each region in order to make the resulting tour as long as possible. In other words, we consider an offline problem in which the goal is to determine an ordering of the regions R that is optimal with respect to the ``worst'' point possible within each region being chosen by an adversary, who knows the chosen ordering. We give a 3-approximation when R is a set of arbitrary regions/sets of points in a metric space. We show how geometry leads to improved constant factor approximations when regions are parallel line segments of the same lengths, and a polynomial-time approximation scheme (PTAS) for the important special case in which R is a set of disjoint unit disks in the plane.
Cite as

Gui Citovsky, Tyler Mayer, and Joseph S. B. Mitchell. TSP With Locational Uncertainty: The Adversarial Model. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{citovsky_et_al:LIPIcs.SoCG.2017.32,
  author =	{Citovsky, Gui and Mayer, Tyler and Mitchell, Joseph S. B.},
  title =	{{TSP With Locational Uncertainty: The Adversarial Model}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.32},
  URN =		{urn:nbn:de:0030-drops-72334},
  doi =		{10.4230/LIPIcs.SoCG.2017.32},
  annote =	{Keywords: traveling salesperson problem, TSP with neighborhoods, approximation algorithms, uncertainty}
}
  • Refine by Author
  • 13 Mitchell, Joseph S. B.
  • 5 Arkin, Esther M.
  • 5 Polishchuk, Valentin
  • 3 Carmi, Paz
  • 3 Katz, Matthew J.
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 approximation algorithms
  • 2 approximation
  • 1 Air Traffic Management
  • 1 Algorithm engineering
  • 1 Algorithms
  • Show More...

  • Refine by Type
  • 21 document

  • Refine by Publication Year
  • 5 2020
  • 4 2024
  • 2 2009
  • 2 2016
  • 2 2017
  • Show More...

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 About DROPS Imprint Privacy Contact