Search Results

Documents authored by Klein, Philip N.

Document
DOI: 10.4230/LIPIcs.FORC.2021.3
On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting

Authors: Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, and Christopher Wolfram

Published in: LIPIcs, Volume 192, 2nd Symposium on Foundations of Responsible Computing (FORC 2021)

Abstract
Redistricting is the problem of dividing up a state into a given number k of regions (called districts) where the voters in each district are to elect a representative. The three primary criteria are: that each district be connected, that the populations of the districts be equal (or nearly equal), and that the districts are "compact". There are multiple competing definitions of compactness, usually minimizing some quantity. One measure that has been recently been used is number of cut edges. In this formulation of redistricting, one is given atomic regions out of which each district must be built (e.g., in the U.S., census blocks). The populations of the atomic regions are given. Consider the graph with one vertex per atomic region and an edge between atomic regions with a shared boundary of positive length. Define the weight of a vertex to be the population of the corresponding region. A districting plan is a partition of vertices into k pieces so that the parts have nearly equal weights and each part is connected. The districts are considered compact to the extent that the plan minimizes the number of edges crossing between different parts. There are two natural computational problems: find the most compact districting plan, and sample districting plans (possibly under a compactness constraint) uniformly at random. Both problems are NP-hard so we consider restricting the input graph to have branchwidth at most w. (A planar graph’s branchwidth is bounded, for example, by its diameter.) If both k and w are bounded by constants, the problems are solvable in polynomial time. In this paper, we give lower and upper bounds that characterize the complexity of these problems in terms of parameters k and w. For simplicity of notation, assume that each vertex has unit weight. We would ideally like algorithms whose running times are of the form O(f(k,w) n^c) for some constant c independent of k and w (in which case the problems are said to be fixed-parameter tractable with respect to those parameters). We show that, under standard complexity-theoretic assumptions, no such algorithms exist. However, the problems are fixed-parameter tractable with respect to each of these parameters individually: there exist algorithms with running times of the form O(f(k) n^{O(w)}) and O(f(w) n^{k+1}). The first result was previously known. The new one, however, is more relevant to the application to redistricting, at least for coarse instances. Indeed, we have implemented a version of the algorithm and have used to successfully find optimally compact solutions to all redistricting instances for France (except Paris, which operates under different rules) under various population-balance constraints. For these instances, the values for w are modest and the values for k are very small.
Cite as

Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, and Christopher Wolfram. On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting. In 2nd Symposium on Foundations of Responsible Computing (FORC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 192, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cohenaddad_et_al:LIPIcs.FORC.2021.3,
  author =	{Cohen-Addad, Vincent and Klein, Philip N. and Marx, D\'{a}niel and Wheeler, Archer and Wolfram, Christopher},
  title =	{{On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting}},
  booktitle =	{2nd Symposium on Foundations of Responsible Computing (FORC 2021)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-187-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{192},
  editor =	{Ligett, Katrina and Gupta, Swati},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2021.3},
  URN =		{urn:nbn:de:0030-drops-138718},
  doi =		{10.4230/LIPIcs.FORC.2021.3},
  annote =	{Keywords: redistricting, algorithms, planar graphs, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.8
Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension

Authors: Amariah Becker, Philip N. Klein, and David Saulpic

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
The concept of bounded highway dimension was developed to capture observed properties of road networks. We show that a graph of bounded highway dimension with a distinguished root vertex can be embedded into a graph of bounded treewidth in such a way that u-to-v distance is preserved up to an additive error of epsilon times the u-to-root plus v-to-root distances. We show that this embedding yields a PTAS for Bounded-Capacity Vehicle Routing in graphs of bounded highway dimension. In this problem, the input specifies a depot and a set of clients, each with a location and demand; the output is a set of depot-to-depot tours, where each client is visited by some tour and each tour covers at most Q units of client demand. Our PTAS can be extended to handle penalties for unvisited clients. We extend this embedding result to handle a set S of root vertices. This result implies a PTAS for Multiple Depot Bounded-Capacity Vehicle Routing: the tours can go from one depot to another. The embedding result also implies that, for fixed k, there is a PTAS for k-Center in graphs of bounded highway dimension. In this problem, the goal is to minimize d so that there exist k vertices (the centers) such that every vertex is within distance d of some center. Similarly, for fixed k, there is a PTAS for k-Median in graphs of bounded highway dimension. In this problem, the goal is to minimize the sum of distances to the k centers.
Cite as

Amariah Becker, Philip N. Klein, and David Saulpic. Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.ESA.2018.8,
  author =	{Becker, Amariah and Klein, Philip N. and Saulpic, David},
  title =	{{Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.8},
  URN =		{urn:nbn:de:0030-drops-94710},
  doi =		{10.4230/LIPIcs.ESA.2018.8},
  annote =	{Keywords: Highway Dimension, Capacitated Vehicle Routing, Graph Embeddings}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.12
A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs

Authors: Amariah Becker, Philip N. Klein, and David Saulpic

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
The Capacitated Vehicle Routing problem is a generalization of the Traveling Salesman problem in which a set of clients must be visited by a collection of capacitated tours. Each tour can visit at most Q clients and must start and end at a specified depot. We present the first approximation scheme for Capacitated Vehicle Routing for non-Euclidean metrics. Specifically we give a quasi-polynomial-time approximation scheme for Capacitated Vehicle Routing with fixed capacities on planar graphs. We also show how this result can be extended to bounded-genus graphs and polylogarithmic capacities, as well as to variations of the problem that include multiple depots and charging penalties for unvisited clients.
Cite as

Amariah Becker, Philip N. Klein, and David Saulpic. A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.ESA.2017.12,
  author =	{Becker, Amariah and Klein, Philip N. and Saulpic, David},
  title =	{{A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.12},
  URN =		{urn:nbn:de:0030-drops-78781},
  doi =		{10.4230/LIPIcs.ESA.2017.12},
  annote =	{Keywords: Capacitated Vehicle Routing, Approximation Algorithms, Planar Graphs}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.8
Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs

Authors: Amariah Becker, Eli Fox-Epstein, Philip N. Klein, and David Meierfrankenfeld

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
We present an implementation of a linear-time approximation scheme for the traveling salesman problem on planar graphs with edge weights. We observe that the theoretical algorithm involves constants that are too large for practical use. Our implementation, which is not subject to the theoretical algorithm's guarantee, can quickly find good tours in very large planar graphs.
Cite as

Amariah Becker, Eli Fox-Epstein, Philip N. Klein, and David Meierfrankenfeld. Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SEA.2017.8,
  author =	{Becker, Amariah and Fox-Epstein, Eli and Klein, Philip N. and Meierfrankenfeld, David},
  title =	{{Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.8},
  URN =		{urn:nbn:de:0030-drops-76305},
  doi =		{10.4230/LIPIcs.SEA.2017.8},
  annote =	{Keywords: Traveling Salesman, Approximation Schemes, Planar Graph Algorithms, Algorithm Engineering}
}
Document
DOI: 10.4230/DagRep.6.5.94
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221)

Authors: Jeff Erickson, Philip N. Klein, Dániel Marx, and Claire Mathieu

Published in: Dagstuhl Reports, Volume 6, Issue 5 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16221 “Algorithms for Optimization Problems in Planar Graphs”. The seminar was held from May 29 to June 3, 2016. This report contains abstracts for the recent developments in planar graph algorithms discussed during the seminar as well as summaries of open problems in this area of research.
Cite as

Jeff Erickson, Philip N. Klein, Dániel Marx, and Claire Mathieu. Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). In Dagstuhl Reports, Volume 6, Issue 5, pp. 94-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{erickson_et_al:DagRep.6.5.94,
  author =	{Erickson, Jeff and Klein, Philip N. and Marx, D\'{a}niel and Mathieu, Claire},
  title =	{{Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221)}},
  pages =	{94--113},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{5},
  editor =	{Erickson, Jeff and Klein, Philip N. and Marx, D\'{a}niel and Mathieu, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.5.94},
  URN =		{urn:nbn:de:0030-drops-67227},
  doi =		{10.4230/DagRep.6.5.94},
  annote =	{Keywords: Algorithms, planar graphs, theory, approximation, fixed-parameter tractable, network flow, network design, kernelization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.554
Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs

Authors: Philip N. Klein, Claire Mathieu, and Hang Zhou

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
In correlation clustering, the input is a graph with edge-weights, where every edge is labelled either + or - according to similarity of its endpoints. The goal is to produce a partition of the vertices that disagrees with the edge labels as little as possible. In two-edge-connected augmentation, the input is a graph with edge-weights and a subset R of edges of the graph. The goal is to produce a minimum weight subset S of edges of the graph, such that for every edge in R, its endpoints are two-edge-connected in R\cup S. For planar graphs, we prove that correlation clustering reduces to two-edge-connected augmentation, and that both problems have a polynomial-time approximation scheme.
Cite as

Philip N. Klein, Claire Mathieu, and Hang Zhou. Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 554-567, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{klein_et_al:LIPIcs.STACS.2015.554,
  author =	{Klein, Philip N. and Mathieu, Claire and Zhou, Hang},
  title =	{{Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{554--567},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.554},
  URN =		{urn:nbn:de:0030-drops-49411},
  doi =		{10.4230/LIPIcs.STACS.2015.554},
  annote =	{Keywords: correlation clustering, two-edge-connected augmentation, polynomial-time approximation scheme, planar graphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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