78 Search Results for "Bast, Hannah"


Volume

LIPIcs, Volume 112

26th Annual European Symposium on Algorithms (ESA 2018)

ESA 2018, August 20-22, 2018, Helsinki, Finland

Editors: Yossi Azar, Hannah Bast, and Grzegorz Herman

Document
Complete Volume
LIPIcs, Volume 112, ESA'18, Complete Volume

Authors: Yossi Azar, Hannah Bast, and Grzegorz Herman

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


Abstract
LIPIcs, Volume 112, ESA'18, Complete Volume

Cite as

26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@Proceedings{azar_et_al:LIPIcs.ESA.2018,
  title =	{{LIPIcs, Volume 112, ESA'18, Complete Volume}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  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},
  URN =		{urn:nbn:de:0030-drops-97239},
  doi =		{10.4230/LIPIcs.ESA.2018},
  annote =	{Keywords: Computer systems organization, Single instruction, multiple data, Computing methodologies, Graphics processors, Robotic planning, Hardware}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Yossi Azar, Hannah Bast, and Grzegorz Herman

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


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ESA.2018.0,
  author =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{0:i--0:xx},
  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.0},
  URN =		{urn:nbn:de:0030-drops-94631},
  doi =		{10.4230/LIPIcs.ESA.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Algorithms for Inverse Optimization Problems

Authors: Sara Ahmadian, Umang Bhaskar, Laura Sanità, and Chaitanya Swamy

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


Abstract
We study inverse optimization problems, wherein the goal is to map given solutions to an underlying optimization problem to a cost vector for which the given solutions are the (unique) optimal solutions. Inverse optimization problems find diverse applications and have been widely studied. A prominent problem in this field is the inverse shortest path (ISP) problem [D. Burton and Ph.L. Toint, 1992; W. Ben-Ameur and E. Gourdin, 2004; A. Bley, 2007], which finds applications in shortest-path routing protocols used in telecommunications. Here we seek a cost vector that is positive, integral, induces a set of given paths as the unique shortest paths, and has minimum l_infty norm. Despite being extensively studied, very few algorithmic results are known for inverse optimization problems involving integrality constraints on the desired cost vector whose norm has to be minimized. Motivated by ISP, we initiate a systematic study of such integral inverse optimization problems from the perspective of designing polynomial time approximation algorithms. For ISP, our main result is an additive 1-approximation algorithm for multicommodity ISP with node-disjoint commodities, which we show is tight assuming P!=NP. We then consider the integral-cost inverse versions of various other fundamental combinatorial optimization problems, including min-cost flow, max/min-cost bipartite matching, and max/min-cost basis in a matroid, and obtain tight or nearly-tight approximation guarantees for these. Our guarantees for the first two problems are based on results for a broad generalization, namely integral inverse polyhedral optimization, for which we also give approximation guarantees. Our techniques also give similar results for variants, including l_p-norm minimization of the integral cost vector, and distance-minimization from an initial cost vector.

Cite as

Sara Ahmadian, Umang Bhaskar, Laura Sanità, and Chaitanya Swamy. Algorithms for Inverse Optimization Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{ahmadian_et_al:LIPIcs.ESA.2018.1,
  author =	{Ahmadian, Sara and Bhaskar, Umang and Sanit\`{a}, Laura and Swamy, Chaitanya},
  title =	{{Algorithms for Inverse Optimization Problems}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{1:1--1:14},
  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.1},
  URN =		{urn:nbn:de:0030-drops-94646},
  doi =		{10.4230/LIPIcs.ESA.2018.1},
  annote =	{Keywords: Inverse optimization, Shortest paths, Approximation algorithms, Linear programming, Polyhedral theory, Combinatorial optimization}
}
Document
Two-Dimensional Maximal Repetitions

Authors: Amihood Amir, Gad M. Landau, Shoshana Marcus, and Dina Sokol

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


Abstract
Maximal repetitions or runs in strings have a wide array of applications and thus have been extensively studied. In this paper, we extend this notion to 2-dimensions, precisely defining a maximal 2D repetition. We provide initial bounds on the number of maximal 2D repetitions that can occur in a matrix. The main contribution of this paper is the presentation of the first algorithm for locating all maximal 2D repetitions in a matrix. The algorithm is efficient and straightforward, with runtime O(n^2 log n log log n+ rho log n), where n^2 is the size of the input, and rho is the number of 2D repetitions in the output.

Cite as

Amihood Amir, Gad M. Landau, Shoshana Marcus, and Dina Sokol. Two-Dimensional Maximal Repetitions. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.ESA.2018.2,
  author =	{Amir, Amihood and Landau, Gad M. and Marcus, Shoshana and Sokol, Dina},
  title =	{{Two-Dimensional Maximal Repetitions}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{2:1--2:14},
  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.2},
  URN =		{urn:nbn:de:0030-drops-94652},
  doi =		{10.4230/LIPIcs.ESA.2018.2},
  annote =	{Keywords: pattern matching algorithms, repetitions, periodicity, two-dimensional}
}
Document
Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums

Authors: Sunil Arya, Guilherme D. da Fonseca, and David M. Mount

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


Abstract
Approximation problems involving a single convex body in R^d have received a great deal of attention in the computational geometry community. In contrast, works involving multiple convex bodies are generally limited to dimensions d <= 3 and/or do not consider approximation. In this paper, we consider approximations to two natural problems involving multiple convex bodies: detecting whether two polytopes intersect and computing their Minkowski sum. Given an approximation parameter epsilon > 0, we show how to independently preprocess two polytopes A,B subset R^d into data structures of size O(1/epsilon^{(d-1)/2}) such that we can answer in polylogarithmic time whether A and B intersect approximately. More generally, we can answer this for the images of A and B under affine transformations. Next, we show how to epsilon-approximate the Minkowski sum of two given polytopes defined as the intersection of n halfspaces in O(n log(1/epsilon) + 1/epsilon^{(d-1)/2 + alpha}) time, for any constant alpha > 0. Finally, we present a surprising impact of these results to a well studied problem that considers a single convex body. We show how to epsilon-approximate the width of a set of n points in O(n log(1/epsilon) + 1/epsilon^{(d-1)/2 + alpha}) time, for any constant alpha > 0, a major improvement over the previous bound of roughly O(n + 1/epsilon^{d-1}) time.

Cite as

Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{arya_et_al:LIPIcs.ESA.2018.3,
  author =	{Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
  title =	{{Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{3:1--3:14},
  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.3},
  URN =		{urn:nbn:de:0030-drops-94664},
  doi =		{10.4230/LIPIcs.ESA.2018.3},
  annote =	{Keywords: Minkowski sum, convex intersection, width, approximation}
}
Document
On the Worst-Case Complexity of TimSort

Authors: Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau

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


Abstract
TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. In fact, there are two slightly different versions of TimSort that are currently implemented in Python and in Java respectively. We propose a pedagogical and insightful proof that the Python version runs in O(n log n). The approach we use in the analysis also applies to the Java version, although not without very involved technical details. As a byproduct of our study, we uncover a bug in the Java implementation that can cause the sorting method to fail during the execution. We also give a proof that Python's TimSort running time is in O(n + n log rho), where rho is the number of runs (i.e. maximal monotonic sequences), which is quite a natural parameter here and part of the explanation for the good behavior of TimSort on partially sorted inputs.

Cite as

Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau. On the Worst-Case Complexity of TimSort. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.ESA.2018.4,
  author =	{Auger, Nicolas and Jug\'{e}, Vincent and Nicaud, Cyril and Pivoteau, Carine},
  title =	{{On the Worst-Case Complexity of TimSort}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{4:1--4:13},
  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.4},
  URN =		{urn:nbn:de:0030-drops-94678},
  doi =		{10.4230/LIPIcs.ESA.2018.4},
  annote =	{Keywords: Sorting algorithms, Merge sorting algorithms, TimSort, Analysis of algorithms}
}
Document
A New and Improved Algorithm for Online Bin Packing

Authors: János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin

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


Abstract
We revisit the classic online bin packing problem studied in the half-century. In this problem, items of positive sizes no larger than 1 are presented one by one to be packed into subsets called bins of total sizes no larger than 1, such that every item is assigned to a bin before the next item is presented. We use online partitioning of items into classes based on sizes, as in previous work, but we also apply a new method where items of one class can be packed into more than two types of bins, where a bin type is defined according to the number of such items grouped together. Additionally, we allow the smallest class of items to be packed in multiple kinds of bins, and not only into their own bins. We combine this with the approach of packing of sufficiently big items according to their exact sizes. Finally, we simplify the analysis of such algorithms, allowing the analysis to be based on the most standard weight functions. This simplified analysis allows us to study the algorithm which we defined based on all these ideas. This leads us to the design and analysis of the first algorithm of asymptotic competitive ratio strictly below 1.58, specifically, we break this barrier by providing an algorithm AH (Advanced Harmonic) whose asymptotic competitive ratio does not exceed 1.57829. Our main contribution is the introduction of the simple analysis based on weight function to analyze the state of the art online algorithms for the classic online bin packing problem. The previously used analytic tool named weight system was too complicated for the community in this area to adjust it for other problems and other algorithmic tools that are needed in order to improve the current best algorithms. We show that the weight system based analysis is not needed for the analysis of the current algorithms for the classic online bin packing problem. The importance of a simple analysis is demonstrated by analyzing several new features together with all existing techniques, and by proving a better competitive ratio than the previously best one.

Cite as

János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin. A New and Improved Algorithm for Online Bin Packing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{balogh_et_al:LIPIcs.ESA.2018.5,
  author =	{Balogh, J\'{a}nos and B\'{e}k\'{e}si, J\'{o}zsef and D\'{o}sa, Gy\"{o}rgy and Epstein, Leah and Levin, Asaf},
  title =	{{A New and Improved Algorithm for Online Bin Packing}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{5:1--5:14},
  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.5},
  URN =		{urn:nbn:de:0030-drops-94686},
  doi =		{10.4230/LIPIcs.ESA.2018.5},
  annote =	{Keywords: Bin packing, online algorithms, competitive analysis}
}
Document
Practical Access to Dynamic Programming on Tree Decompositions

Authors: Max Bannach and Sebastian Berndt

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


Abstract
Parameterized complexity theory has lead to a wide range of algorithmic breakthroughs within the last decades, but the practicability of these methods for real-world problems is still not well understood. We investigate the practicability of one of the fundamental approaches of this field: dynamic programming on tree decompositions. Indisputably, this is a key technique in parameterized algorithms and modern algorithm design. Despite the enormous impact of this approach in theory, it still has very little influence on practical implementations. The reasons for this phenomenon are manifold. One of them is the simple fact that such an implementation requires a long chain of non-trivial tasks (as computing the decomposition, preparing it,...). We provide an easy way to implement such dynamic programs that only requires the definition of the update rules. With this interface, dynamic programs for various problems, such as 3-coloring, can be implemented easily in about 100 lines of structured Java code. The theoretical foundation of the success of dynamic programming on tree decompositions is well understood due to Courcelle's celebrated theorem, which states that every MSO-definable problem can be efficiently solved if a tree decomposition of small width is given. We seek to provide practical access to this theorem as well, by presenting a lightweight model-checker for a small fragment of MSO. This fragment is powerful enough to describe many natural problems, and our model-checker turns out to be very competitive against similar state-of-the-art tools.

Cite as

Max Bannach and Sebastian Berndt. Practical Access to Dynamic Programming on Tree Decompositions. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.ESA.2018.6,
  author =	{Bannach, Max and Berndt, Sebastian},
  title =	{{Practical Access to Dynamic Programming on Tree Decompositions}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{6:1--6:13},
  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.6},
  URN =		{urn:nbn:de:0030-drops-94692},
  doi =		{10.4230/LIPIcs.ESA.2018.6},
  annote =	{Keywords: fixed-parameter tractability, treewidth, model-checking}
}
Document
Average Whenever You Meet: Opportunistic Protocols for Community Detection

Authors: Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, and Luca Trevisan

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


Abstract
Consider the following asynchronous, opportunistic communication model over a graph G: in each round, one edge is activated uniformly and independently at random and (only) its two endpoints can exchange messages and perform local computations. Under this model, we study the following random process: The first time a vertex is an endpoint of an active edge, it chooses a random number, say +/- 1 with probability 1/2; then, in each round, the two endpoints of the currently active edge update their values to their average. We provide a rigorous analysis of the above process showing that, if G exhibits a two-community structure (for example, two expanders connected by a sparse cut), the values held by the nodes will collectively reflect the underlying community structure over a suitable phase of the above process. Our analysis requires new concentration bounds on the product of certain random matrices that are technically challenging and possibly of independent interest. We then exploit our analysis to design the first opportunistic protocols that approximately recover community structure using only logarithmic (or polylogarithmic, depending on the sparsity of the cut) work per node.

Cite as

Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, and Luca Trevisan. Average Whenever You Meet: Opportunistic Protocols for Community Detection. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:LIPIcs.ESA.2018.7,
  author =	{Becchetti, Luca and Clementi, Andrea and Manurangsi, Pasin and Natale, Emanuele and Pasquale, Francesco and Raghavendra, Prasad and Trevisan, Luca},
  title =	{{Average Whenever You Meet: Opportunistic Protocols for Community Detection}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{7:1--7:13},
  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.7},
  URN =		{urn:nbn:de:0030-drops-94705},
  doi =		{10.4230/LIPIcs.ESA.2018.7},
  annote =	{Keywords: Community Detection, Random Processes, Spectral Analysis}
}
Document
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
Fine-grained Lower Bounds on Cops and Robbers

Authors: Sebastian Brandt, Seth Pettie, and Jara Uitto

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


Abstract
Cops and Robbers is a classic pursuit-evasion game played between a group of g cops and one robber on an undirected N-vertex graph G. We prove that the complexity of deciding the winner in the game under optimal play requires Omega (N^{g-o(1)}) time on instances with O(N log^2 N) edges, conditioned on the Strong Exponential Time Hypothesis. Moreover, the problem of calculating the minimum number of cops needed to win the game is 2^{Omega (sqrt{N})}, conditioned on the weaker Exponential Time Hypothesis. Our conditional lower bound comes very close to a conditional upper bound: if Meyniel's conjecture holds then the cop number can be decided in 2^{O(sqrt{N}log N)} time. In recent years, the Strong Exponential Time Hypothesis has been used to obtain many lower bounds on classic combinatorial problems, such as graph diameter, LCS, EDIT-DISTANCE, and REGEXP matching. To our knowledge, these are the first conditional (S)ETH-hard lower bounds on a strategic game.

Cite as

Sebastian Brandt, Seth Pettie, and Jara Uitto. Fine-grained Lower Bounds on Cops and Robbers. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.ESA.2018.9,
  author =	{Brandt, Sebastian and Pettie, Seth and Uitto, Jara},
  title =	{{Fine-grained Lower Bounds on Cops and Robbers}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{9:1--9:12},
  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.9},
  URN =		{urn:nbn:de:0030-drops-94725},
  doi =		{10.4230/LIPIcs.ESA.2018.9},
  annote =	{Keywords: Cops and Robbers}
}
Document
A Polynomial Kernel for Diamond-Free Editing

Authors: Yixin Cao, Ashutosh Rai, R. B. Sandeep, and Junjie Ye

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


Abstract
Given a fixed graph H, the H-free editing problem asks whether we can edit at most k edges to make a graph contain no induced copy of H. We obtain a polynomial kernel for this problem when H is a diamond. The incompressibility dichotomy for H being a 3-connected graph and the classical complexity dichotomy suggest that except for H being a complete/empty graph, H-free editing problems admit polynomial kernels only for a few small graphs H. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of H-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem.

Cite as

Yixin Cao, Ashutosh Rai, R. B. Sandeep, and Junjie Ye. A Polynomial Kernel for Diamond-Free Editing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ESA.2018.10,
  author =	{Cao, Yixin and Rai, Ashutosh and Sandeep, R. B. and Ye, Junjie},
  title =	{{A Polynomial Kernel for Diamond-Free Editing}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{10:1--10:13},
  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.10},
  URN =		{urn:nbn:de:0030-drops-94732},
  doi =		{10.4230/LIPIcs.ESA.2018.10},
  annote =	{Keywords: Kernelization, Diamond-free, H-free editing, Graph modification problem}
}
Document
Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades

Authors: Corrie Jacobien Carstens, Michael Hamann, Ulrich Meyer, Manuel Penschuck, Hung Tran, and Dorothea Wagner

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


Abstract
Graph randomisation is a crucial task in the analysis and synthesis of networks. It is typically implemented as an edge switching process (ESMC) repeatedly swapping the nodes of random edge pairs while maintaining the degrees involved [Mihail and Zegura, 2003]. Curveball is a novel approach that instead considers the whole neighbourhoods of randomly drawn node pairs. Its Markov chain converges to a uniform distribution, and experiments suggest that it requires less steps than the established ESMC [Carstens et al., 2016]. Since trades however are more expensive, we study Curveball's practical runtime by introducing the first efficient Curveball algorithms: the I/O-efficient EM-CB for simple undirected graphs and its internal memory pendant IM-CB. Further, we investigate global trades [Carstens et al., 2016] processing every node in a single super step, and show that undirected global trades converge to a uniform distribution and perform superior in practice. We then discuss EM-GCB and EM-PGCB for global trades and give experimental evidence that EM-PGCB achieves the quality of the state-of-the-art ESMC algorithm EM-ES [M. Hamann et al., 2017] nearly one order of magnitude faster.

Cite as

Corrie Jacobien Carstens, Michael Hamann, Ulrich Meyer, Manuel Penschuck, Hung Tran, and Dorothea Wagner. Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{carstens_et_al:LIPIcs.ESA.2018.11,
  author =	{Carstens, Corrie Jacobien and Hamann, Michael and Meyer, Ulrich and Penschuck, Manuel and Tran, Hung and Wagner, Dorothea},
  title =	{{Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-94745},
  doi =		{10.4230/LIPIcs.ESA.2018.11},
  annote =	{Keywords: Graph randomisation, Curveball, I/O-efficiency, Parallelism}
}
Document
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity

Authors: Diptarka Chakraborty, Debarati Das, Michal Koucký, and Nitin Saurabh

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


Abstract
A quasi-Gray code of dimension n and length l over an alphabet Sigma is a sequence of distinct words w_1,w_2,...,w_l from Sigma^n such that any two consecutive words differ in at most c coordinates, for some fixed constant c>0. In this paper we are interested in the read and write complexity of quasi-Gray codes in the bit-probe model, where we measure the number of symbols read and written in order to transform any word w_i into its successor w_{i+1}. We present construction of quasi-Gray codes of dimension n and length 3^n over the ternary alphabet {0,1,2} with worst-case read complexity O(log n) and write complexity 2. This generalizes to arbitrary odd-size alphabets. For the binary alphabet, we present quasi-Gray codes of dimension n and length at least 2^n - 20n with worst-case read complexity 6+log n and write complexity 2. This complements a recent result by Raskin [Raskin '17] who shows that any quasi-Gray code over binary alphabet of length 2^n has read complexity Omega(n). Our results significantly improve on previously known constructions and for the odd-size alphabets we break the Omega(n) worst-case barrier for space-optimal (non-redundant) quasi-Gray codes with constant number of writes. We obtain our results via a novel application of algebraic tools together with the principles of catalytic computation [Buhrman et al. '14, Ben-Or and Cleve '92, Barrington '89, Coppersmith and Grossman '75].

Cite as

Diptarka Chakraborty, Debarati Das, Michal Koucký, and Nitin Saurabh. Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ESA.2018.12,
  author =	{Chakraborty, Diptarka and Das, Debarati and Kouck\'{y}, Michal and Saurabh, Nitin},
  title =	{{Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{12:1--12: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.12},
  URN =		{urn:nbn:de:0030-drops-94750},
  doi =		{10.4230/LIPIcs.ESA.2018.12},
  annote =	{Keywords: Gray code, Space-optimal counter, Decision assignment tree, Cell probe model}
}
  • Refine by Author
  • 4 Bast, Hannah
  • 3 Munro, J. Ian
  • 3 van Leeuwen, Erik Jan
  • 2 Azar, Yossi
  • 2 Bhaskar, Umang
  • Show More...

  • Refine by Classification
  • 8 Theory of computation → Design and analysis of algorithms
  • 7 Mathematics of computing → Graph algorithms
  • 7 Theory of computation → Graph algorithms analysis
  • 5 Theory of computation → Approximation algorithms analysis
  • 5 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 3 Kernelization
  • 3 Scheduling
  • 3 online algorithms
  • 3 planar graphs
  • 2 Doubling Dimension
  • Show More...

  • Refine by Type
  • 77 document
  • 1 volume

  • Refine by Publication Year
  • 76 2018
  • 2 2013

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