Volume
LIPIcs, Volume 162
17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)
Event
SWAT 2020, June 22-24, 2020, Tórshavn, Faroe IslandsEditor
Publication Details
- published at: 2020-06-12
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-150-4
- DBLP: db/conf/swat/swat2020
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 162, SWAT 2020, Complete Volume
Abstract
LIPIcs, Volume 162, SWAT 2020, Complete Volume
Cite as
17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 1-606, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@Proceedings{albers:LIPIcs.SWAT.2020,
title = {{LIPIcs, Volume 162, SWAT 2020, Complete Volume}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {1--606},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020},
URN = {urn:nbn:de:0030-drops-122469},
doi = {10.4230/LIPIcs.SWAT.2020},
annote = {Keywords: LIPIcs, Volume 162, SWAT 2020, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{albers:LIPIcs.SWAT.2020.0,
author = {Albers, Susanne},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {0:i--0:x},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.0},
URN = {urn:nbn:de:0030-drops-122476},
doi = {10.4230/LIPIcs.SWAT.2020.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Parameterized Complexity of PCA (Invited Talk)
Abstract
We discuss some recent progress in the study of Principal Component Analysis (PCA) from the perspective of Parameterized Complexity.
Cite as
Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov. Parameterized Complexity of PCA (Invited Talk). In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 1:1-1:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{fomin_et_al:LIPIcs.SWAT.2020.1,
author = {Fomin, Fedor V. and Golovach, Petr A. and Simonov, Kirill},
title = {{Parameterized Complexity of PCA}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {1:1--1:5},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.1},
URN = {urn:nbn:de:0030-drops-122487},
doi = {10.4230/LIPIcs.SWAT.2020.1},
annote = {Keywords: parameterized complexity, Robust PCA, outlier detection}
}
Document
Invited Talk
Landscape of Locality (Invited Talk)
Abstract
The theory of distributed computing aims at understanding which tasks can be solved efficiently in large distributed systems. This forms the basis for our understanding of the modern world, which heavily depends on world-wide communication networks and large-scale distributed computer systems.
In distributed computing the key computational resource is communication, and we seek to find out which computational problems can be solved with only a few communication steps. This is directly connected to the concept of locality: in T synchronous communication rounds, all nodes in a network can gather all information in their radius-T neighborhoods, but not any further. Hence the distributed time complexity of a graph problem can be defined in two equivalent ways: it is the number of communication rounds needed to solve the problem, and it is the distance up to which individual nodes need to see in order to choose their own part of the solution.
While the locality of graph problems has been studied already since the 1980s, only in the past four years we have started to take big leaps in understanding what the landscape of distributed time complexity looks like and with what kind of tools and techniques we can study it.
One concept that has been a driving force in the recent developments is the notion of locally verifiable problems. These are graph problems in which a solution is feasible if and only if it looks valid in all constant-radius neighborhoods; put otherwise, these are problems that could be solved efficiently with a nondeterministic distributed algorithm, and hence they form a natural distributed analogue of class NP. Now the key question is this: if a problem is locally verifiable, is it also locally solvable, and if not, what can we say about its distributed time complexity?
Naor and Stockmeyer [SIAM J. Comput. 1995] formalized the idea of locally verifiable problems by introducing the class of LCL problems (locally checkable labeling problems). While the concept is old, and over the years we have seen results related to the locality of many specific LCLs, little was known about the distributed complexity of LCLs in general. By 2015, we had only seen examples of LCLs with localities O(1), Θ(log^* n), and Θ(n), and it was wide open whether these three classes are all that there is.
All this started to change rapidly after we proved [Brandt et al., STOC 2016] that there are natural examples of LCLs that have a locality strictly between ω(log^* n) and o(n). The same paper also paved the way for the development of a new general-purpose proof technique for analyzing the locality of locally verifiable problems, namely round elimination.
Now after four years of work and a number of papers by several research teams working in the area, we have reached a point in which there is a near-complete picture of the landscape of LCL problems - and it looks nothing like what we would have expected.
Cite as
Jukka Suomela. Landscape of Locality (Invited Talk). In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{suomela:LIPIcs.SWAT.2020.2,
author = {Suomela, Jukka},
title = {{Landscape of Locality}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {2:1--2:1},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.2},
URN = {urn:nbn:de:0030-drops-122490},
doi = {10.4230/LIPIcs.SWAT.2020.2},
annote = {Keywords: Theory of distributed computing, Network algorithms, Locality, Distributed time complexity}
}
Document
Preclustering Algorithms for Imprecise Points
Abstract
We study the problem of preclustering a set B of imprecise points in ℝ^d: we wish to cluster the regions specifying the potential locations of the points such that, no matter where the points are located within their regions, the resulting clustering approximates the optimal clustering for those locations. We consider k-center, k-median, and k-means clustering, and obtain the following results.
Let B:={b₁,…,b_n} be a collection of disjoint balls in ℝ^d, where each ball b_i specifies the possible locations of an input point p_i. A partition 𝒞 of B into subsets is called an (f(k),α)-preclustering (with respect to the specific k-clustering variant under consideration) if (i) 𝒞 consists of f(k) preclusters, and (ii) for any realization P of the points p_i inside their respective balls, the cost of the clustering on P induced by 𝒞 is at most α times the cost of an optimal k-clustering on P. We call f(k) the size of the preclustering and we call α its approximation ratio. We prove that, even in ℝ^1, one may need at least 3k-3 preclusters to obtain a bounded approximation ratio - this holds for the k-center, the k-median, and the k-means problem - and we present a (3k,1) preclustering for the k-center problem in ℝ^1. We also present various preclusterings for balls in ℝ^d with d⩾2, including a (3k,α)-preclustering with α≈13.9 for the k-center and the k-median problem, and α≈254.7 for the k-means problem.
Cite as
Mohammad Ali Abam, Mark de Berg, Sina Farahzad, Mir Omid Haji Mirsadeghi, and Morteza Saghafian. Preclustering Algorithms for Imprecise Points. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{abam_et_al:LIPIcs.SWAT.2020.3,
author = {Abam, Mohammad Ali and de Berg, Mark and Farahzad, Sina and Mirsadeghi, Mir Omid Haji and Saghafian, Morteza},
title = {{Preclustering Algorithms for Imprecise Points}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {3:1--3:12},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.3},
URN = {urn:nbn:de:0030-drops-122503},
doi = {10.4230/LIPIcs.SWAT.2020.3},
annote = {Keywords: Geometric clustering, k-center, k-means, k-median, imprecise points, approximation algorithms}
}
Document
Parameter Analysis for Guarding Terrains
Abstract
The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also attracted attention from the viewpoint of Parameterized complexity. In this paper, we focus on the parameterized complexity of Terrain Guarding (both discrete and continuous) with respect to two natural parameters. First we show that, when parameterized by the number r of reflex vertices in the input terrain, the problem has a polynomial kernel. We also show that, when parameterized by the number c of minima in the terrain, Discrete Orthogonal Terrain Guarding has an XP algorithm.
Cite as
Akanksha Agrawal, Sudeshna Kolay, and Meirav Zehavi. Parameter Analysis for Guarding Terrains. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{agrawal_et_al:LIPIcs.SWAT.2020.4,
author = {Agrawal, Akanksha and Kolay, Sudeshna and Zehavi, Meirav},
title = {{Parameter Analysis for Guarding Terrains}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {4:1--4:18},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.4},
URN = {urn:nbn:de:0030-drops-122514},
doi = {10.4230/LIPIcs.SWAT.2020.4},
annote = {Keywords: Terrain Guarding, Reflex Vertices, Terrain Minima, FPT Algorithm, XP Algorithm, Kernelization}
}
Document
Vertex Downgrading to Minimize Connectivity
Abstract
We consider the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given source to a sink. We introduce and study a general downgrading variant of the interdiction problem where the capacity of an arc is a function of the subset of its endpoints that are downgraded, and the goal is to minimize the downgraded capacity of a minimum source-sink cut subject to a node downgrading budget. This models the case when both ends of an arc must be downgraded to remove it, for example. For this generalization, we provide a bicriteria (4,4)-approximation that downgrades nodes with total weight at most 4 times the budget and provides a solution where the downgraded connectivity from the source to the sink is at most 4 times that in an optimal solution. We accomplish this with an LP relaxation and rounding using a ball-growing algorithm based on the LP values. We further generalize the downgrading problem to one where each vertex can be downgraded to one of k levels, and the arc capacities are functions of the pairs of levels to which its ends are downgraded. We generalize our LP rounding to get a (4k,4k)-approximation for this case.
Cite as
Hassene Aissi, Da Qi Chen, and R. Ravi. Vertex Downgrading to Minimize Connectivity. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{aissi_et_al:LIPIcs.SWAT.2020.5,
author = {Aissi, Hassene and Chen, Da Qi and Ravi, R.},
title = {{Vertex Downgrading to Minimize Connectivity}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {5:1--5:15},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.5},
URN = {urn:nbn:de:0030-drops-122527},
doi = {10.4230/LIPIcs.SWAT.2020.5},
annote = {Keywords: Vertex Interdiction, Vertex Downgrading, Network Interdiction, Approximation Algorithm}
}
Document
Sea-Rise Flooding on Massive Dynamic Terrains
Abstract
Predicting floods caused by storm surges is a crucial task. Since the rise of ocean water can create floods that extend far onto land, the flood damage can be severe. By developing efficient flood prediction algorithms that use very detailed terrain models and accurate sea-level forecasts, users can plan mitigations such as flood walls and gates to minimize the damage from storm surge flooding.
In this paper we present a data structure for predicting floods from dynamic sea-level forecast data on dynamic massive terrains. The forecast data is dynamic in the sense that new forecasts are released several times per day; the terrain is dynamic in the sense that the terrain model may be updated to plan flood mitigations.
Since accurate flood risk computations require using very detailed terrain models, and such terrain models can easily exceed the size of the main memory in a regular computer, our data structure is I/O-efficient, that is, it minimizes the number of I/Os (i.e. block transfers) between main memory and disk. For a terrain represented as a raster of N cells, it can be constructed using O(N/B log_M/B N/B) I/Os, it can compute the flood risk in a given small region using O(log_B N) I/Os, and it can handle updating the terrain elevation in a given small region using O(log²_B N) I/Os, where B is the block size and M is the capacity of main memory.
Cite as
Lars Arge, Mathias Rav, Morten Revsbæk, Yujin Shin, and Jungwoo Yang. Sea-Rise Flooding on Massive Dynamic Terrains. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{arge_et_al:LIPIcs.SWAT.2020.6,
author = {Arge, Lars and Rav, Mathias and Revsb{\ae}k, Morten and Shin, Yujin and Yang, Jungwoo},
title = {{Sea-Rise Flooding on Massive Dynamic Terrains}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {6:1--6:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.6},
URN = {urn:nbn:de:0030-drops-122539},
doi = {10.4230/LIPIcs.SWAT.2020.6},
annote = {Keywords: Computational geometry, I/O-algorithms, merge tree, dynamic terrain}
}
Document
Computing β-Stretch Paths in Drawings of Graphs
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-dev.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
Submodular Clustering in Low Dimensions
Abstract
We study a clustering problem where the goal is to maximize the coverage of the input points by k chosen centers. Specifically, given a set of n points P ⊆ ℝ^d, the goal is to pick k centers C ⊆ ℝ^d that maximize the service ∑_{p∈P}φ(𝖽(p,C)) to the points P, where 𝖽(p,C) is the distance of p to its nearest center in C, and φ is a non-increasing service function φ: ℝ+ → ℝ+. This includes problems of placing k base stations as to maximize the total bandwidth to the clients - indeed, the closer the client is to its nearest base station, the more data it can send/receive, and the target is to place k base stations so that the total bandwidth is maximized. We provide an n^{ε^-O(d)} time algorithm for this problem that achieves a (1-ε)-approximation. Notably, the runtime does not depend on the parameter k and it works for an arbitrary non-increasing service function φ: ℝ+ → ℝ+.
Cite as
Arturs Backurs and Sariel Har-Peled. Submodular Clustering in Low Dimensions. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{backurs_et_al:LIPIcs.SWAT.2020.8,
author = {Backurs, Arturs and Har-Peled, Sariel},
title = {{Submodular Clustering in Low Dimensions}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {8:1--8:14},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.8},
URN = {urn:nbn:de:0030-drops-122551},
doi = {10.4230/LIPIcs.SWAT.2020.8},
annote = {Keywords: clustering, covering, PTAS}
}
Document
Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time
Abstract
We analyze a reduction rule for computing kernels for the hitting set problem: In a hypergraph, the link of a set c of vertices consists of all edges that are supersets of c. We call such a set critical if its link has certain easy-to-check size properties. The rule states that the link of a critical c can be replaced by c. It is known that a simple linear-time algorithm for computing hitting set kernels (number of edges) at most k^d (k is the hitting set size, d is the maximum edge size) can be derived from this rule. We parallelize this algorithm and obtain the first AC⁰ kernel algorithm that outputs polynomial-size kernels. Previously, such algorithms were not even known for artificial problems. An interesting application of our methods lies in traditional, non-parameterized approximation theory: Our results imply that uniform AC⁰-circuits can compute a hitting set whose size is polynomial in the size of an optimal hitting set.
Cite as
Max Bannach, Malte Skambath, and Till Tantau. Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bannach_et_al:LIPIcs.SWAT.2020.9,
author = {Bannach, Max and Skambath, Malte and Tantau, Till},
title = {{Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {9:1--9:16},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.9},
URN = {urn:nbn:de:0030-drops-122566},
doi = {10.4230/LIPIcs.SWAT.2020.9},
annote = {Keywords: Kernelization, Approximation, Hitting Set, Constant-Depth Circuits}
}
Document
Graph Realizations: Maximum Degree in Vertex Neighborhoods
Abstract
The classical problem of degree sequence realizability asks whether or not a given sequence of n positive integers is equal to the degree sequence of some n-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information profiles, such as the vertex neighborhood profiles.
In this paper, we initiate the study of neighborhood degree profiles, wherein, our focus is on the natural problem of realizing maximum neighborhood degrees. More specifically, we ask the following question: "Given a sequence D of n non-negative integers 0≤ d₁≤ ⋯ ≤ d_n, does there exist a simple graph with vertices v₁,…, v_n such that for every 1≤ i ≤ n, the maximum degree in the neighborhood of v_i is exactly d_i?"
We provide in this work various results for maximum-neighborhood-degree for general n vertex graphs. Our results are first of its kind that studies extremal neighborhood degree profiles. For closed as well as open neighborhood degree profiles, we provide a complete realizability criteria. We also provide tight bounds for the number of maximum neighbouring degree profiles of length n that are realizable. Our conditions are verifiable in linear time and our realizations can be constructed in polynomial time.
Cite as
Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Graph Realizations: Maximum Degree in Vertex Neighborhoods. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{barnoy_et_al:LIPIcs.SWAT.2020.10,
author = {Bar-Noy, Amotz and Choudhary, Keerti and Peleg, David and Rawitz, Dror},
title = {{Graph Realizations: Maximum Degree in Vertex Neighborhoods}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {10:1--10:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.10},
URN = {urn:nbn:de:0030-drops-122572},
doi = {10.4230/LIPIcs.SWAT.2020.10},
annote = {Keywords: Graph realization, neighborhood profile, extremum-degree}
}
Document
A Dynamic Space-Efficient Filter with Constant Time Operations
Abstract
A dynamic dictionary is a data structure that maintains sets of cardinality at most n from a given universe and supports insertions, deletions, and membership queries. A filter approximates membership queries with a one-sided error that occurs with probability at most ε. The goal is to obtain dynamic filters that are space-efficient (the space is 1+o(1) times the information-theoretic lower bound) and support all operations in constant time with high probability. One approach to designing filters is to reduce to the retrieval problem. When the size of the universe is polynomial in n, this approach yields a space-efficient dynamic filter as long as the error parameter ε satisfies log(1/ε) = ω(log log n). For the case that log(1/ε) = O(log log n), we present the first space-efficient dynamic filter with constant time operations in the worst case (whp). In contrast, the space-efficient dynamic filter of Pagh et al. [Anna Pagh et al., 2005] supports insertions and deletions in amortized expected constant time. Our approach employs the classic reduction of Carter et al. [Carter et al., 1978] on a new type of dictionary construction that supports random multisets.
Cite as
Ioana O. Bercea and Guy Even. A Dynamic Space-Efficient Filter with Constant Time Operations. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bercea_et_al:LIPIcs.SWAT.2020.11,
author = {Bercea, Ioana O. and Even, Guy},
title = {{A Dynamic Space-Efficient Filter with Constant Time Operations}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {11:1--11:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.11},
URN = {urn:nbn:de:0030-drops-122582},
doi = {10.4230/LIPIcs.SWAT.2020.11},
annote = {Keywords: Data Structures}
}
Document
A Simple Algorithm for Minimum Cuts in Near-Linear Time
Abstract
We consider the minimum cut problem in undirected, weighted graphs. We give a simple algorithm to find a minimum cut that 2-respects (cuts two edges of) a spanning tree T of a graph G. This procedure can be used in place of the complicated subroutine given in Karger’s near-linear time minimum cut algorithm [Karger, 2000]. We give a self-contained version of Karger’s algorithm with the new procedure, which is easy to state and relatively simple to implement. It produces a minimum cut on an m-edge, n-vertex graph in O(m log³ n) time with high probability, matching the complexity of Karger’s approach.
Cite as
Nalin Bhardwaj, Antonio J. Molina Lovett, and Bryce Sandlund. A Simple Algorithm for Minimum Cuts in Near-Linear Time. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bhardwaj_et_al:LIPIcs.SWAT.2020.12,
author = {Bhardwaj, Nalin and Molina Lovett, Antonio J. and Sandlund, Bryce},
title = {{A Simple Algorithm for Minimum Cuts in Near-Linear Time}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {12:1--12:18},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.12},
URN = {urn:nbn:de:0030-drops-122594},
doi = {10.4230/LIPIcs.SWAT.2020.12},
annote = {Keywords: minimum cut, sparsification, near-linear time, packing}
}
Document
Parameterized Study of Steiner Tree on Unit Disk Graphs
Abstract
We study the Steiner Tree problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R⊆ V(G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V⧵ R. The vertices of R are referred to as terminals and the vertices of V(G)⧵ R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in n^{O(√{t+k})} time. We also show that the Steiner Tree problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2^{O(k)}n^{O(1)}. In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs [Fomin et al., 2019]. We mention that the algorithmic results can be made to work for Steiner Tree on disk graphs with bounded aspect ratio. Finally, we prove that Steiner Tree on disk graphs parameterized by k is W[1]-hard.
Cite as
Sujoy Bhore, Paz Carmi, Sudeshna Kolay, and Meirav Zehavi. Parameterized Study of Steiner Tree on Unit Disk Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bhore_et_al:LIPIcs.SWAT.2020.13,
author = {Bhore, Sujoy and Carmi, Paz and Kolay, Sudeshna and Zehavi, Meirav},
title = {{Parameterized Study of Steiner Tree on Unit Disk Graphs}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {13:1--13:18},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.13},
URN = {urn:nbn:de:0030-drops-122607},
doi = {10.4230/LIPIcs.SWAT.2020.13},
annote = {Keywords: Unit Disk Graphs, FPT, Subexponential exact algorithms, NP-Hardness, W-Hardness}
}
Document
Bounded-Angle Minimum Spanning Trees
Abstract
Motivated by the connectivity problem in wireless networks with directional antennas, we study bounded-angle spanning trees. Let P be a set of points in the plane and let α be an angle. An α-ST of P is a spanning tree of the complete Euclidean graph on P with the property that all edges incident to each point p ∈ P lie in a wedge of angle α centered at p. We study the following closely related problems for α = 120 degrees (however, our approximation ratios hold for any α ⩾ 120 degrees).
1) The α-minimum spanning tree problem asks for an α-ST of minimum sum of edge lengths. Among many interesting results, Aschner and Katz (ICALP 2014) proved the NP-hardness of this problem and presented a 6-approximation algorithm. Their algorithm finds an α-ST of length at most 6 times the length of the minimum spanning tree (MST). By adopting a somewhat similar approach and using different proof techniques we improve this ratio to 16/3.
2) To examine what is possible with non-uniform wedge angles, we define an ̅α-ST to be a spanning tree with the property that incident edges to all points lie in wedges of average angle α. We present an algorithm to find an ̅α-ST whose largest edge-length and sum of edge lengths are at most 2 and 1.5 times (respectively) those of the MST. These ratios are better than any achievable when all wedges have angle α. Our algorithm runs in linear time after computing the MST.
Cite as
Ahmad Biniaz, Prosenjit Bose, Anna Lubiw, and Anil Maheshwari. Bounded-Angle Minimum Spanning Trees. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{biniaz_et_al:LIPIcs.SWAT.2020.14,
author = {Biniaz, Ahmad and Bose, Prosenjit and Lubiw, Anna and Maheshwari, Anil},
title = {{Bounded-Angle Minimum Spanning Trees}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {14:1--14:22},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.14},
URN = {urn:nbn:de:0030-drops-122616},
doi = {10.4230/LIPIcs.SWAT.2020.14},
annote = {Keywords: bounded-angle MST, directional antenna, approximation algorithms}
}
Document
Low-Stretch Spanning Trees of Graphs with Bounded Width
Abstract
We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph G with a linear arrangement of bandwidth b can be embedded into a distribution T of spanning trees such that the expected stretch of each edge of G is O(b²). Our proof implies a linear time algorithm for sampling from T. Therefore, we have a linear time algorithm that finds a spanning tree of G with average stretch O(b²) with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of G with average stretch O(b³). For graphs of cutwidth c, we construct a spanning tree with stretch O(c²) in linear time. Finally, when G has treewidth k we provide a dynamic programming algorithm computing a minimum stretch spanning tree of G that runs in polynomial time with respect to the number of vertices of G.
Cite as
Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, and Amir Nayyeri. Low-Stretch Spanning Trees of Graphs with Bounded Width. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{borradaile_et_al:LIPIcs.SWAT.2020.15,
author = {Borradaile, Glencora and Chambers, Erin Wolf and Eppstein, David and Maxwell, William and Nayyeri, Amir},
title = {{Low-Stretch Spanning Trees of Graphs with Bounded Width}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {15:1--15:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.15},
URN = {urn:nbn:de:0030-drops-122622},
doi = {10.4230/LIPIcs.SWAT.2020.15},
annote = {Keywords: Treewidth, low-stretch spanning tree, fundamental cycle basis}
}
Document
Parameterized Complexity of Two-Interval Pattern Problem
Abstract
A 2-interval is the union of two disjoint intervals on the real line. Two 2-intervals D₁ and D₂ are disjoint if their intersection is empty (i.e., no interval of D₁ intersects any interval of D₂). There can be three different relations between two disjoint 2-intervals; namely, preceding (<), nested (⊏) and crossing (≬). Two 2-intervals D₁ and D₂ are called R-comparable for some R∈{<,⊏,≬}, if either D₁RD₂ or D₂RD₁. A set 𝒟 of disjoint 2-intervals is ℛ-comparable, for some ℛ⊆{<,⊏,≬} and ℛ≠∅, if every pair of 2-intervals in ℛ are R-comparable for some R∈ℛ. Given a set of 2-intervals and some ℛ⊆{<,⊏,≬}, the objective of the {2-interval pattern problem} is to find a largest subset of 2-intervals that is ℛ-comparable.
The 2-interval pattern problem is known to be W[1]-hard when |ℛ|=3 and NP-hard when |ℛ|=2 (except for ℛ={<,⊏}, which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing that it is W[1]-hard for both ℛ={⊏,≬} and ℛ={<,≬} (when parameterized by the size of an optimal solution). This answers the open question posed by Vialette [Encyclopedia of Algorithms, 2008].
Cite as
Prosenjit Bose, Saeed Mehrabi, and Debajyoti Mondal. Parameterized Complexity of Two-Interval Pattern Problem. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 16:1-16:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bose_et_al:LIPIcs.SWAT.2020.16,
author = {Bose, Prosenjit and Mehrabi, Saeed and Mondal, Debajyoti},
title = {{Parameterized Complexity of Two-Interval Pattern Problem}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {16:1--16:10},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.16},
URN = {urn:nbn:de:0030-drops-122630},
doi = {10.4230/LIPIcs.SWAT.2020.16},
annote = {Keywords: Interval graphs, Two-interval pattern problem, Comparability, Multicoloured clique problem, Parameterized complexity, W\lbrack1\rbrack-hardness}
}
Document
Recoloring Interval Graphs with Limited Recourse Budget
Abstract
We consider the problem of coloring an interval graph dynamically. Intervals arrive one after the other and have to be colored immediately such that no two intervals of the same color overlap. In each step only a limited number of intervals may be recolored to maintain a proper coloring (thus interpolating between the well-studied online and offline settings). The number of allowed recolorings per step is the so-called recourse budget. Our main aim is to prove both upper and lower bounds on the required recourse budget for interval graphs, given a bound on the allowed number of colors.
For general interval graphs with n vertices and chromatic number k it is known that some recoloring is needed even if we have 2k colors available. We give an algorithm that maintains a 2k-coloring with an amortized recourse budget of 𝒪(log n). For maintaining a k-coloring with k ≤ n, we give an amortized upper bound of 𝒪(k⋅ k! ⋅ √n), and a lower bound of Ω(k) for k ∈ 𝒪(√n), which can be as large as Ω(√n).
For unit interval graphs it is known that some recoloring is needed even if we have k+1 colors available. We give an algorithm that maintains a (k+1)-coloring with at most 𝒪(k²) recolorings per step in the worst case. We also give a lower bound of Ω(log n) on the amortized recourse budget needed to maintain a k-coloring.
Additionally, for general interval graphs we show that if one does not insist on maintaining an explicit coloring, one can have a k-coloring algorithm which does not incur a factor of 𝒪(k ⋅ k! ⋅ √n) in the running time. For this we provide a data structure, which allows for adding intervals in 𝒪(k² log³ n) amortized time per update and querying for the color of a particular interval in 𝒪(log n) time. Between any two updates, the data structure answers consistently with some optimal coloring. The data structure maintains the coloring implicitly, so the notion of recourse budget does not apply to it.
Cite as
Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, and Anna Zych-Pawlewicz. Recoloring Interval Graphs with Limited Recourse Budget. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bosek_et_al:LIPIcs.SWAT.2020.17,
author = {Bosek, Bart{\l}omiej and Disser, Yann and Feldmann, Andreas Emil and Pawlewicz, Jakub and Zych-Pawlewicz, Anna},
title = {{Recoloring Interval Graphs with Limited Recourse Budget}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {17:1--17:23},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.17},
URN = {urn:nbn:de:0030-drops-122649},
doi = {10.4230/LIPIcs.SWAT.2020.17},
annote = {Keywords: Colouring, Dynamic Algorithms, Recourse Budget, Interval Graphs}
}
Document
Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives
Abstract
We study the problem of determining the exact number of defective items in an adaptive group testing by using a minimum number of tests. We improve the existing algorithm and prove a lower bound that shows that the number of tests in our algorithm is optimal up to small additive terms.
Cite as
Nader H. Bshouty, Catherine A. Haddad-Zaknoon, Raghd Boulos, Foad Moalem, Jalal Nada, Elias Noufi, and Yara Zaknoon. Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bshouty_et_al:LIPIcs.SWAT.2020.18,
author = {Bshouty, Nader H. and Haddad-Zaknoon, Catherine A. and Boulos, Raghd and Moalem, Foad and Nada, Jalal and Noufi, Elias and Zaknoon, Yara},
title = {{Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {18:1--18:12},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.18},
URN = {urn:nbn:de:0030-drops-122658},
doi = {10.4230/LIPIcs.SWAT.2020.18},
annote = {Keywords: Group Testing, Randomized Algorithm}
}
Document
On the Hardness of Computing an Average Curve
Abstract
We study the complexity of clustering curves under k-median and k-center objectives in the metric space of the Fréchet distance and related distance measures. Building upon recent hardness results for the minimum-enclosing-ball problem under the Fréchet distance, we show that also the 1-median problem is NP-hard. Furthermore, we show that the 1-median problem is W[1]-hard with the number of curves as parameter. We show this under the discrete and continuous Fréchet and Dynamic Time Warping (DTW) distance. This yields an independent proof of an earlier result by Bulteau et al. from 2018 for a variant of DTW that uses squared distances, where the new proof is both simpler and more general. On the positive side, we give approximation algorithms for problem variants where the center curve may have complexity at most 𝓁 under the discrete Fréchet distance. In particular, for fixed k, 𝓁 and ε, we give (1+ε)-approximation algorithms for the (k,𝓁)-median and (k,𝓁)-center objectives and a polynomial-time exact algorithm for the (k,𝓁)-center objective.
Cite as
Kevin Buchin, Anne Driemel, and Martijn Struijs. On the Hardness of Computing an Average Curve. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{buchin_et_al:LIPIcs.SWAT.2020.19,
author = {Buchin, Kevin and Driemel, Anne and Struijs, Martijn},
title = {{On the Hardness of Computing an Average Curve}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {19:1--19:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.19},
URN = {urn:nbn:de:0030-drops-122662},
doi = {10.4230/LIPIcs.SWAT.2020.19},
annote = {Keywords: Curves, Clustering, Algorithms, Hardness, Approximation}
}
Document
Sparse Regression via Range Counting
Abstract
The sparse regression problem, also known as best subset selection problem, can be cast as follows: Given a set S of n points in ℝ^d, a point y∈ ℝ^d, and an integer 2 ≤ k ≤ d, find an affine combination of at most k points of S that is nearest to y. We describe a O(n^{k-1} log^{d-k+2} n)-time randomized (1+ε)-approximation algorithm for this problem with d and ε constant. This is the first algorithm for this problem running in time o(n^k). Its running time is similar to the query time of a data structure recently proposed by Har-Peled, Indyk, and Mahabadi (ICALP'18), while not requiring any preprocessing. Up to polylogarithmic factors, it matches a conditional lower bound relying on a conjecture about affine degeneracy testing. In the special case where k = d = O(1), we provide a simple O_δ(n^{d-1+δ})-time deterministic exact algorithm, for any δ > 0. Finally, we show how to adapt the approximation algorithm for the sparse linear regression and sparse convex regression problems with the same running time, up to polylogarithmic factors.
Cite as
Jean Cardinal and Aurélien Ooms. Sparse Regression via Range Counting. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{cardinal_et_al:LIPIcs.SWAT.2020.20,
author = {Cardinal, Jean and Ooms, Aur\'{e}lien},
title = {{Sparse Regression via Range Counting}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {20:1--20:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.20},
URN = {urn:nbn:de:0030-drops-122677},
doi = {10.4230/LIPIcs.SWAT.2020.20},
annote = {Keywords: Sparse Linear Regression, Orthogonal Range Searching, Affine Degeneracy Testing, Nearest Neighbors, Hyperplane Arrangements}
}
Document
Drawing Graphs with Circular Arcs and Right-Angle Crossings
Abstract
In a RAC drawing of a graph, vertices are represented by points in the plane, adjacent vertices are connected by line segments, and crossings must form right angles. Graphs that admit such drawings are RAC graphs. RAC graphs are beyond-planar graphs and have been studied extensively. In particular, it is known that a RAC graph with n vertices has at most 4n-10 edges.
We introduce a superclass of RAC graphs, which we call arc-RAC graphs. A graph is arc-RAC if it admits a drawing where edges are represented by circular arcs and crossings form right angles. We provide a Turán-type result showing that an arc-RAC graph with n vertices has at most 14n-12 edges and that there are n-vertex arc-RAC graphs with 4.5n - O(√n) edges.
Cite as
Steven Chaplick, Henry Förster, Myroslav Kryven, and Alexander Wolff. Drawing Graphs with Circular Arcs and Right-Angle Crossings. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{chaplick_et_al:LIPIcs.SWAT.2020.21,
author = {Chaplick, Steven and F\"{o}rster, Henry and Kryven, Myroslav and Wolff, Alexander},
title = {{Drawing Graphs with Circular Arcs and Right-Angle Crossings}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {21:1--21:14},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.21},
URN = {urn:nbn:de:0030-drops-122687},
doi = {10.4230/LIPIcs.SWAT.2020.21},
annote = {Keywords: circular arcs, right-angle crossings, edge density, charging argument}
}
Document
Clustering Moving Entities in Euclidean Space
Abstract
Clustering is a fundamental problem of spatio-temporal data analysis. Given a set 𝒳 of n moving entities, each of which corresponds to a sequence of τ time-stamped points in ℝ^d, a k-clustering of 𝒳 is a partition of 𝒳 into k disjoint subsets that optimizes a given objective function. In this paper, we consider two clustering problems, k-Center and k-MM, where the goal is to minimize the maximum value of the objective function over the duration of motion for the worst-case input 𝒳. We show that both problems are NP-hard when k is an arbitrary input parameter, even when the motion is restricted to ℝ. We provide an exact algorithm for the 2-MM clustering problem in ℝ^d that runs in O(τ d n²) time. The running time can be improved to O(τ n log{n}) when the motion is restricted to ℝ. We show that the 2-Center clustering problem is NP-hard in ℝ². Our 2-MM clustering algorithm provides a 1.15-approximate solution to the 2-Center clustering problem in ℝ². Moreover, finding a (1.15-ε)-approximate solution remains NP-hard for any ε >0. For both the k-MM and k-Center clustering problems in ℝ^d, we provide a 2-approximation algorithm that runs in O(τ d n k) time.
Cite as
Stephane Durocher and Md Yeakub Hassan. Clustering Moving Entities in Euclidean Space. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{durocher_et_al:LIPIcs.SWAT.2020.22,
author = {Durocher, Stephane and Hassan, Md Yeakub},
title = {{Clustering Moving Entities in Euclidean Space}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {22:1--22:14},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.22},
URN = {urn:nbn:de:0030-drops-122698},
doi = {10.4230/LIPIcs.SWAT.2020.22},
annote = {Keywords: trajectories, clustering, moving entities, k-CENTER, algorithms}
}
Document
Trajectory Visibility
Abstract
We study the problem of testing whether there exists a time at which two entities moving along different piece-wise linear trajectories among polygonal obstacles are mutually visible. We study several variants, depending on whether or not the obstacles form a simple polygon, trajectories may intersect the polygon edges, and both or only one of the entities are moving.
For constant complexity trajectories contained in a simple polygon with n vertices, we provide an 𝒪(n) time algorithm to test if there is a time at which the entities can see each other. If the polygon contains holes, we present an 𝒪(n log n) algorithm. We show that this is tight.
We then consider storing the obstacles in a data structure, such that queries consisting of two line segments can be efficiently answered. We show that for all variants it is possible to answer queries in sublinear time using polynomial space and preprocessing time.
As a critical intermediate step, we provide an efficient solution to a problem of independent interest: preprocess a convex polygon such that we can efficiently test intersection with a quadratic curve segment. If the obstacles form a simple polygon, this allows us to answer visibility queries in 𝒪(n³/4log³ n) time using 𝒪(nlog⁵ n) space. For more general obstacles the query time is 𝒪(log^k n), for a constant but large value k, using 𝒪(n^{3k}) space. We provide more efficient solutions when one of the entities remains stationary.
Cite as
Patrick Eades, Ivor van der Hoog, Maarten Löffler, and Frank Staals. Trajectory Visibility. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{eades_et_al:LIPIcs.SWAT.2020.23,
author = {Eades, Patrick and van der Hoog, Ivor and L\"{o}ffler, Maarten and Staals, Frank},
title = {{Trajectory Visibility}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {23:1--23:22},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.23},
URN = {urn:nbn:de:0030-drops-122701},
doi = {10.4230/LIPIcs.SWAT.2020.23},
annote = {Keywords: trajectories, visibility, data structures, semi-algebraic range searching}
}
Document
Simplifying Activity-On-Edge Graphs
Abstract
We formalize the simplification of activity-on-edge graphs used for visualizing project schedules, where the vertices of the graphs represent project milestones, and the edges represent either tasks of the project or timing constraints between milestones. In this framework, a timeline of the project can be constructed as a leveled drawing of the graph, where the levels of the vertices represent the time at which each milestone is scheduled to happen. We focus on the following problem: given an activity-on-edge graph representing a project, find an equivalent activity-on-edge graph—one with the same critical paths—that has the minimum possible number of milestone vertices among all equivalent activity-on-edge graphs. We provide an O(mn²)-time algorithm for solving this graph minimization problem.
Cite as
David Eppstein, Daniel Frishberg, and Elham Havvaei. Simplifying Activity-On-Edge Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{eppstein_et_al:LIPIcs.SWAT.2020.24,
author = {Eppstein, David and Frishberg, Daniel and Havvaei, Elham},
title = {{Simplifying Activity-On-Edge Graphs}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {24:1--24:14},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.24},
URN = {urn:nbn:de:0030-drops-122718},
doi = {10.4230/LIPIcs.SWAT.2020.24},
annote = {Keywords: directed acyclic graph, activity-on-edge graph, critical path, project planning, milestone minimization, graph visualization}
}
Document
Generalized Metric Repair on Graphs
Abstract
Many modern data analysis algorithms either assume or are considerably more efficient if the distances between the data points satisfy a metric. However, as real data sets are noisy, they often do not possess this fundamental property. For this reason, Gilbert and Jain [A. Gilbert and L. Jain, 2017] and Fan et al. [C. Fan et al., 2018] introduced the closely related sparse metric repair and metric violation distance problems. Given a matrix, representing all distances, the goal is to repair as few entries as possible to ensure they satisfy a metric. This problem was shown to be APX-hard, and an O(OPT^{1/3})-approximation was given, where OPT is the optimal solution size.
In this paper, we generalize the problem, by describing distances by a possibly incomplete positively weighted graph, where again our goal is to find the smallest number of weight modifications so that they satisfy a metric. This natural generalization is more flexible as it takes into account different relationships among the data points. We demonstrate the inherent combinatorial structure of the problem, and give an approximation-preserving reduction from MULTICUT, which is hard to approximate within any constant factor assuming UGC. Conversely, we show that for any fixed constant ς, for the large class of ς-chordal graphs, the problem is fixed parameter tractable, answering an open question from previous work. Call a cycle broken if it contains an edge whose weight is larger than the sum of all its other edges, and call the amount of this difference its deficit. We present approximation algorithms, one depending on the maximum number of edges in a broken cycle, and one depending on the number of distinct deficit values, both quantities which may naturally be small. Finally, we give improved analysis of previous algorithms for complete graphs.
Cite as
Chenglin Fan, Anna C. Gilbert, Benjamin Raichel, Rishi Sonthalia, and Gregory Van Buskirk. Generalized Metric Repair on Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 25:1-25:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{fan_et_al:LIPIcs.SWAT.2020.25,
author = {Fan, Chenglin and Gilbert, Anna C. and Raichel, Benjamin and Sonthalia, Rishi and Van Buskirk, Gregory},
title = {{Generalized Metric Repair on Graphs}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {25:1--25:22},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.25},
URN = {urn:nbn:de:0030-drops-122727},
doi = {10.4230/LIPIcs.SWAT.2020.25},
annote = {Keywords: Approximation, FPT, Hardness, Metric Spaces}
}
Document
Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
Abstract
Given an undirected graph G and integers c and k, the Maximum Edge-Colorable Subgraph problem asks whether we can delete at most k edges in G to obtain a graph that has a proper edge coloring with at most c colors. We show that Maximum Edge-Colorable Subgraph admits, for every fixed c, a linear-size problem kernel when parameterized by the edge deletion distance of G to a graph with maximum degree c-1. This parameterization measures the distance to instances that, due to Vizing’s famous theorem, are trivial yes-instances. For c≤ 4, we also provide a linear-size kernel for the same parameterization for Multi Strong Triadic Closure, a related edge coloring problem with applications in social network analysis. We provide further results for Maximum Edge-Colorable Subgraph parameterized by the vertex deletion distance to graphs where every component has order at most c and for the list-colored versions of both problems.
Cite as
Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{gruttemeier_et_al:LIPIcs.SWAT.2020.26,
author = {Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils},
title = {{Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {26:1--26:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.26},
URN = {urn:nbn:de:0030-drops-122731},
doi = {10.4230/LIPIcs.SWAT.2020.26},
annote = {Keywords: Graph coloring, social networks, parameterized complexity, kernelization}
}
Document
Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies
Abstract
We consider the Π-free Deletion problem parameterized by the size of a vertex cover, for a range of graph properties Π. Given an input graph G, this problem asks whether there is a subset of at most k vertices whose removal ensures the resulting graph does not contain a graph from Π as induced subgraph. Many vertex-deletion problems such as Perfect Deletion, Wheel-free Deletion, and Interval Deletion fit into this framework. We introduce the concept of characterizing a graph property Π by low-rank adjacencies, and use it as the cornerstone of a general kernelization theorem for Π-Free Deletion parameterized by the size of a vertex cover. The resulting framework captures problems such as AT-Free Deletion, Wheel-free Deletion, and Interval Deletion. Moreover, our new framework shows that the vertex-deletion problem to perfect graphs has a polynomial kernel when parameterized by vertex cover, thereby resolving an open question by Fomin et al. [JCSS 2014]. Our main technical contribution shows how linear-algebraic dependence of suitably defined vectors over 𝔽₂ implies graph-theoretic statements about the presence of forbidden induced subgraphs.
Cite as
Bart M. P. Jansen and Jari J. H. de Kroon. Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{jansen_et_al:LIPIcs.SWAT.2020.27,
author = {Jansen, Bart M. P. and de Kroon, Jari J. H.},
title = {{Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {27:1--27:15},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.27},
URN = {urn:nbn:de:0030-drops-122748},
doi = {10.4230/LIPIcs.SWAT.2020.27},
annote = {Keywords: kernelization, vertex-deletion, graph modification, structural parameterization}
}
Document
Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations
Abstract
Locality Sensitive Hashing (LSH) is an effective method to index a set of points such that we can efficiently find the nearest neighbors of a query point. We extend this method to our novel Set-query LSH (SLSH), such that it can find the nearest neighbors of a set of points, given as a query.
Let s(x,y) be the similarity between two points x and y. We define a similarity between a set Q and a point x by aggregating the similarities s(p,x) for all p∈ Q. For example, we can take s(p,x) to be the angular similarity between p and x (i.e., 1-(∠(x,p)/π)), and aggregate by arithmetic or geometric averaging, or taking the lowest similarity.
We develop locality sensitive hash families and data structures for a large set of such arithmetic and geometric averaging similarities, and analyze their collision probabilities. We also establish an analogous framework and hash families for distance functions. Specifically, we give a structure for the euclidean distance aggregated by either averaging or taking the maximum.
We leverage SLSH to solve a geometric extension of the approximate near neighbors problem. In this version, we consider a metric for which the unit ball is an ellipsoid and its orientation is specified with the query.
An important application that motivates our work is group recommendation systems. Such a system embeds movies and users in the same feature space, and the task of recommending a movie for a group to watch together, translates to a set-query Q using an appropriate similarity.
Cite as
Haim Kaplan and Jay Tenenbaum. Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kaplan_et_al:LIPIcs.SWAT.2020.28,
author = {Kaplan, Haim and Tenenbaum, Jay},
title = {{Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {28:1--28:18},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.28},
URN = {urn:nbn:de:0030-drops-122756},
doi = {10.4230/LIPIcs.SWAT.2020.28},
annote = {Keywords: Locality sensitive hashing, nearest neighbors, similarity search, group recommendations, distance functions, similarity functions, ellipsoid}
}
Document
Fast Multi-Subset Transform and Weighted Sums over Acyclic Digraphs
Abstract
The zeta and Moebius transforms over the subset lattice of n elements and the so-called subset convolution are examples of unary and binary operations on set functions. While their direct computation requires O(3ⁿ) arithmetic operations, less naive algorithms only use 2ⁿ poly(n) operations, nearly linear in the input size. Here, we investigate a related n-ary operation that takes n set functions as input and maps them to a new set function. This operation, we call multi-subset transform, is the core ingredient in the known inclusion - exclusion recurrence for weighted sums over acyclic digraphs, which extends Robinson’s recurrence for the number of labelled acyclic digraphs. Prior to this work, the best known complexity bound for computing the multi-subset transform was the direct O(3ⁿ). By reducing the task to rectangular matrix multiplication, we improve the complexity to O(2.985ⁿ).
Cite as
Mikko Koivisto and Antti Röyskö. Fast Multi-Subset Transform and Weighted Sums over Acyclic Digraphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{koivisto_et_al:LIPIcs.SWAT.2020.29,
author = {Koivisto, Mikko and R\"{o}ysk\"{o}, Antti},
title = {{Fast Multi-Subset Transform and Weighted Sums over Acyclic Digraphs}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {29:1--29:12},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.29},
URN = {urn:nbn:de:0030-drops-122768},
doi = {10.4230/LIPIcs.SWAT.2020.29},
annote = {Keywords: Bayesian networks, Moebius transform, Rectangular matrix multiplication, Subset convolution, Weighted counting of acyclic digraphs, Zeta transform}
}
Document
Exact Exponential Algorithms for Two Poset Problems
Abstract
Partially ordered sets (posets) are fundamental combinatorial objects with important applications in computer science. Perhaps the most natural algorithmic task, given a size-n poset, is to compute its number of linear extensions. In 1991 Brightwell and Winkler showed this problem to be #P-hard. In spite of extensive research, the fastest known algorithm is still the straightforward O(n 2ⁿ)-time dynamic programming (an adaptation of the Bellman-Held-Karp algorithm for the TSP). Very recently, Dittmer and Pak showed that the problem remains #P-hard for two-dimensional posets, and no algorithm was known to break the 2ⁿ-barrier even in this special case. The question of whether the two-dimensional problem is easier than the general case was raised decades ago by Möhring, Felsner and Wernisch, and others. In this paper we show that the number of linear extensions of a two-dimensional poset can be computed in time O(1.8286ⁿ).
The related jump number problem asks for a linear extension of a poset, minimizing the number of neighboring incomparable pairs. The problem has applications in scheduling, and has been widely studied. In 1981 Pulleyblank showed it to be NP-complete. We show that the jump number problem can be solved (in arbitrary posets) in time O(1.824ⁿ). This improves (slightly) the previous best bound of Kratsch and Kratsch.
Cite as
László Kozma. Exact Exponential Algorithms for Two Poset Problems. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kozma:LIPIcs.SWAT.2020.30,
author = {Kozma, L\'{a}szl\'{o}},
title = {{Exact Exponential Algorithms for Two Poset Problems}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {30:1--30:15},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.30},
URN = {urn:nbn:de:0030-drops-122773},
doi = {10.4230/LIPIcs.SWAT.2020.30},
annote = {Keywords: poset, linear extension, jump number, exponential time}
}
Document
Space-Efficient Data Structures for Lattices
Abstract
A lattice is a partially-ordered set in which every pair of elements has a unique meet (greatest lower bound) and join (least upper bound). We present new data structures for lattices that are simple, efficient, and nearly optimal in terms of space complexity.
Our first data structure can answer partial order queries in constant time and find the meet or join of two elements in O(n^{3/4}) time, where n is the number of elements in the lattice. It occupies O(n^{3/2}log n) bits of space, which is only a Θ(log n) factor from the Θ(n^{3/2})-bit lower bound for storing lattices. The preprocessing time is O(n²). This structure admits a simple space-time tradeoff so that, for any c ∈ [1/2, 1], the data structure supports meet and join queries in O(n^{1-c/2}) time, occupies O(n^{1+c}log n) bits of space, and can be constructed in O(n² + n^{1+3c/2}) time.
Our second data structure uses O(n^{3/2}log n) bits of space and supports meet and join in O(d (log n)/(log d)) time, where d is the maximum degree of any element in the transitive reduction graph of the lattice. This structure is much faster for lattices with low-degree elements.
This paper also identifies an error in a long-standing solution to the problem of representing lattices. We discuss the issue with this previous work.
Cite as
J. Ian Munro, Bryce Sandlund, and Corwin Sinnamon. Space-Efficient Data Structures for Lattices. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{munro_et_al:LIPIcs.SWAT.2020.31,
author = {Munro, J. Ian and Sandlund, Bryce and Sinnamon, Corwin},
title = {{Space-Efficient Data Structures for Lattices}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {31:1--31:22},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.31},
URN = {urn:nbn:de:0030-drops-122782},
doi = {10.4230/LIPIcs.SWAT.2020.31},
annote = {Keywords: Lattice, Partially-ordered set, Space-efficient data structure, Succinct data structure}
}
Document
Online Embedding of Metrics
Abstract
We study deterministic online embeddings of metric spaces into normed spaces of various dimensions and into trees. We establish some upper and lower bounds on the distortion of such embedding, and pose some challenging open questions.
Cite as
Ilan Newman and Yuri Rabinovich. Online Embedding of Metrics. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{newman_et_al:LIPIcs.SWAT.2020.32,
author = {Newman, Ilan and Rabinovich, Yuri},
title = {{Online Embedding of Metrics}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {32:1--32:13},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.32},
URN = {urn:nbn:de:0030-drops-122792},
doi = {10.4230/LIPIcs.SWAT.2020.32},
annote = {Keywords: Metric spaces, online embedding}
}
Document
Primal-Dual 2-Approximation Algorithm for the Monotonic Multiple Depot Heterogeneous Traveling Salesman Problem
Abstract
We study a Multiple Depot Heterogeneous Traveling Salesman Problem (MDHTSP) where the cost of the traveling between any two targets depends on the type of the vehicle. The travel costs are assumed to be symmetric, satisfy the triangle inequality, and are monotonic, i.e., the travel costs between any two targets monotonically increases with the index of the vehicles. Exploiting the monotonic structure of the travel costs, we present a 2-approximation algorithm based on the primal-dual method.
Cite as
S. Rathinam, R. Ravi, J. Bae, and K. Sundar. Primal-Dual 2-Approximation Algorithm for the Monotonic Multiple Depot Heterogeneous Traveling Salesman Problem. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{rathinam_et_al:LIPIcs.SWAT.2020.33,
author = {Rathinam, S. and Ravi, R. and Bae, J. and Sundar, K.},
title = {{Primal-Dual 2-Approximation Algorithm for the Monotonic Multiple Depot Heterogeneous Traveling Salesman Problem}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {33:1--33:13},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.33},
URN = {urn:nbn:de:0030-drops-122805},
doi = {10.4230/LIPIcs.SWAT.2020.33},
annote = {Keywords: Approximation Algorithm, Heterogeneous Traveling Salesman Problem, Primal-dual Method}
}
Document
On the Parameterized Complexity of Grid Contraction
Abstract
For a family of graphs 𝒢, the 𝒢-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists F ⊆ E(G) of size at most k such that G/F belongs to 𝒢. Here, G/F is the graph obtained from G by contracting all the edges in F. In this article, we initiate the study of Grid Contraction from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time c^k ⋅ |V(G)|^{{O}(1)}, for this problem. We complement this result by proving that unless ETH fails, there is no algorithm for Grid Contraction with running time c^{o(k)} ⋅ |V(G)|^{{O}(1)}. We also present a polynomial kernel for this problem.
Cite as
Saket Saurabh, Uéverton dos Santos Souza, and Prafullkumar Tale. On the Parameterized Complexity of Grid Contraction. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{saurabh_et_al:LIPIcs.SWAT.2020.34,
author = {Saurabh, Saket and Souza, U\'{e}verton dos Santos and Tale, Prafullkumar},
title = {{On the Parameterized Complexity of Grid Contraction}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {34:1--34:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.34},
URN = {urn:nbn:de:0030-drops-122810},
doi = {10.4230/LIPIcs.SWAT.2020.34},
annote = {Keywords: Grid Contraction, FPT, Kernelization, Lower Bound}
}
Document
Simplification of Polyline Bundles
Abstract
We propose and study a generalization to the well-known problem of polyline simplification. Instead of a single polyline, we are given a set of l polylines possibly sharing some line segments and bend points. Our goal is to minimize the number of bend points in the simplified bundle with respect to some error tolerance δ (measuring Fréchet distance) but under the additional constraint that shared parts have to be simplified consistently. We show that polyline bundle simplification is NP-hard to approximate within a factor n^(1/3 - ε) for any ε > 0 where n is the number of bend points in the polyline bundle. This inapproximability even applies to instances with only l=2 polylines. However, we identify the sensitivity of the solution to the choice of δ as a reason for this strong inapproximability. In particular, we prove that if we allow δ to be exceeded by a factor of 2 in our solution, we can find a simplified polyline bundle with no more than 𝒪(log (l + n)) ⋅ OPT bend points in polytime, providing us with an efficient bi-criteria approximation. As a further result, we show fixed-parameter tractability in the number of shared bend points.
Cite as
Joachim Spoerhase, Sabine Storandt, and Johannes Zink. Simplification of Polyline Bundles. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{spoerhase_et_al:LIPIcs.SWAT.2020.35,
author = {Spoerhase, Joachim and Storandt, Sabine and Zink, Johannes},
title = {{Simplification of Polyline Bundles}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {35:1--35: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.35},
URN = {urn:nbn:de:0030-drops-122821},
doi = {10.4230/LIPIcs.SWAT.2020.35},
annote = {Keywords: Polyline Simplification, Bi-criteria Approximation, Hardness of Approximation, Geometric Set Cover}
}
Document
Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
Abstract
An ordered binary decision diagram (OBDD) is a directed acyclic graph that represents a Boolean function. Since OBDDs have many nice properties as data structures, they have been extensively studied for decades in both theoretical and practical fields, such as VLSI (Very Large Scale Integration) design, formal verification, machine learning, and combinatorial problems. Arguably, the most crucial problem in using OBDDs is that they may vary exponentially in size depending on their variable ordering (i.e., the order in which the variables are to be read) when they represent the same function. Indeed, it is NP hard to find an optimal variable ordering that minimizes an OBDD for a given function. Friedman and Supowit provided a clever deterministic algorithm with time/space complexity O^∗(3ⁿ), where n is the number of variables of the function, which is much better than the trivial brute-force bound O^∗(n!2ⁿ). This paper shows that a further speedup is possible with quantum computers by presenting a quantum algorithm that produces a minimum OBDD together with the corresponding variable ordering in O^∗(2.77286ⁿ) time and space with an exponentially small error probability. Moreover, this algorithm can be adapted to constructing other minimum decision diagrams such as zero-suppressed BDDs.
Cite as
Seiichiro Tani. Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{tani:LIPIcs.SWAT.2020.36,
author = {Tani, Seiichiro},
title = {{Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {36:1--36:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.36},
URN = {urn:nbn:de:0030-drops-122832},
doi = {10.4230/LIPIcs.SWAT.2020.36},
annote = {Keywords: Binary Decision Diagram, Variable Ordering, Quantum Algorithm}
}