Volume
LIPIcs, Volume 75
16th International Symposium on Experimental Algorithms (SEA 2017)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Experimental Algorithms (SEA)
Event
SEA 2017, June 21-23, 2017, London, UKEditors
Publication Details
- published at: 2017-08-07
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-036-1
- DBLP: db/conf/wea/sea2017
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 75, SEA'17, Complete Volume
Abstract
LIPIcs, Volume 75, SEA'17, Complete Volume
Cite as
16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@Proceedings{iliopoulos_et_al:LIPIcs.SEA.2017,
title = {{LIPIcs, Volume 75, SEA'17, Complete Volume}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017},
URN = {urn:nbn:de:0030-drops-76644},
doi = {10.4230/LIPIcs.SEA.2017},
annote = {Keywords: Analysis of Algorithms and Problem Complexity, Algorithms}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization, External Reviewers
Abstract
Front Matter, Table of Contents, Preface, Conference Organization, External Reviewers
Cite as
16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{iliopoulos_et_al:LIPIcs.SEA.2017.0,
author = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
title = {{Front Matter, Table of Contents, Preface, Conference Organization, External Reviewers}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {0:i--0:xiv},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.0},
URN = {urn:nbn:de:0030-drops-76006},
doi = {10.4230/LIPIcs.SEA.2017.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization, External Reviewers}
}
Document
Designing Energy-Efficient Heat Recovery Networks using Mixed-Integer Nonlinear Optimisation
Abstract
Many industrial processes involve heating and cooling liquids: a quarter of the EU 2012 energy consumption came from industry and industry uses 73% of this energy on heating and cooling. We discuss mixed-integer nonlinear optimisation and its applications to energy efficiency. Our particular emphasis is on algorithms and solution techniques enabling optimisation for large-scale industrial networks.
As a first application, optimising heat exchangers networks may increase efficiency in industrial plants. We develop deterministic global optimisation algorithms for a mixed-integer nonlinear optimisation model that simultaneously incorporates utility cost, equipment area, and hot/cold stream matches. We automatically recognise and exploit special mathematical structures common in heat recovery. We also computationally demonstrate the impact on the global optimisation solver ANTIGONE and benchmark large-scale test cases against heuristic approaches.
As a second application, we discuss special structure in nonconvex quadratically-constrained optimisation problems, particularly through the lens of stream mixing and intermediate blending on process systems engineering networks. We take a parametric approach to uncovering topological structure and sparsity of the standard pooling problem in its p-formulation. We show that the sparse patterns of active topological structure are associated with a piecewise objective function. Finally, the presentation explains the conditions under which sparsity vanishes and where the combinatorial complexity emerges to cross over the P/NP boundary. We formally present the results obtained and their derivations for various specialised instances.
Cite as
Radu Baltean-Lugojan, Christodoulos A. Floudas, Ruth Misener, and Miten Mistry. Designing Energy-Efficient Heat Recovery Networks using Mixed-Integer Nonlinear Optimisation. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{balteanlugojan_et_al:LIPIcs.SEA.2017.1,
author = {Baltean-Lugojan, Radu and Floudas, Christodoulos A. and Misener, Ruth and Mistry, Miten},
title = {{Designing Energy-Efficient Heat Recovery Networks using Mixed-Integer Nonlinear Optimisation}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {1:1--1:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.1},
URN = {urn:nbn:de:0030-drops-76288},
doi = {10.4230/LIPIcs.SEA.2017.1},
annote = {Keywords: Heat exchanger network, Mixed-integer nonlinear optimisation, Log mean temperature difference, Deterministic global optimisation}
}
Document
Dictionaries Revisited
Abstract
Dictionaries are probably the most well studied class of data structures. A dictionary supports insertions, deletions, membership queries, and usually successor, predecessor, and extract-min. Given their centrality to both the theory and practice of data structures, surprisingly basic questions about them remain unsolved and sometimes even unposed. This talk focuses on questions that arise from the disparity between the way large-scale dictionaries are analyzed and the way they are used in practice.
Cite as
Martin Farach-Colton. Dictionaries Revisited. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{farachcolton:LIPIcs.SEA.2017.2,
author = {Farach-Colton, Martin},
title = {{Dictionaries Revisited}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {2:1--2:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.2},
URN = {urn:nbn:de:0030-drops-76336},
doi = {10.4230/LIPIcs.SEA.2017.2},
annote = {Keywords: B+-trees, file system, write optimization}
}
Document
Engineering Streaming Algorithms
Abstract
Streaming algorithms must process a large quantity of small updates quickly to allow queries about the input to be answered from a small summary. Initial work on streaming algorithms laid out theoretical results, and subsequent efforts have involved engineering these for practical use. Informed by experiments, streaming algorithms have been widely implemented and used in practice. This talk will survey this line of work, and identify some lessons learned.
Cite as
Graham Cormode. Engineering Streaming Algorithms. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{cormode:LIPIcs.SEA.2017.3,
author = {Cormode, Graham},
title = {{Engineering Streaming Algorithms}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {3:1--3:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.3},
URN = {urn:nbn:de:0030-drops-76270},
doi = {10.4230/LIPIcs.SEA.2017.3},
annote = {Keywords: Data stream algorithms}
}
Document
Better Process Mapping and Sparse Quadratic Assignment
Abstract
Communication and topology aware process mapping is a powerful approach to reduce communication time in parallel applications with known communication patterns on large, distributed memory systems. We address the problem as a quadratic assignment problem (QAP), and present algorithms to construct initial mappings of processes to processors as well as fast local search algorithms to further improve the mappings. By exploiting assumptions that typically hold for applications and modern supercomputer systems such as sparse communication patterns and hierarchically organized communication systems, we arrive at significantly more powerful algorithms for these special QAPs. Our multilevel construction algorithms employ recently developed, perfectly balanced graph partitioning techniques and excessively exploit the given communication system hierarchy. We present improvements to a local search algorithm of Brandfass et al. (2013), and decrease the running time by reducing the time needed to perform swaps in the assignment as well as by carefully constraining local search neighborhoods. Experiments indicate that our algorithms not only dramatically speed up local search, but due to the multilevel approach also find much better solutions in practice.
Cite as
Christian Schulz and Jesper Larsson Träff. Better Process Mapping and Sparse Quadratic Assignment. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{schulz_et_al:LIPIcs.SEA.2017.4,
author = {Schulz, Christian and Tr\"{a}ff, Jesper Larsson},
title = {{Better Process Mapping and Sparse Quadratic Assignment}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {4:1--4:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.4},
URN = {urn:nbn:de:0030-drops-76034},
doi = {10.4230/LIPIcs.SEA.2017.4},
annote = {Keywords: rank reordering, graph algorithms, process mapping, graph partitioning}
}
Document
The Isomap Algorithm in Distance Geometry
Abstract
The fundamental problem of distance geometry consists in finding a realization of a given weighted graph in a Euclidean space of given dimension, in such a way that vertices are realized as points and edges as straight segments having the same lengths as their given weights. This problem arises in structural proteomics, wireless sensor networks, and clock synchronization protocols to name a few applications. The well-known Isomap method is a dimensionality reduction heuristic which projects finite but high dimensional metric spaces into the "most significant" lower dimensional ones, where significance is measured by the magnitude of the corresponding eigenvalues. We start from a simple observation, namely that Isomap can also be used to provide approximate realizations of weighted graphs very efficiently, and then derive and benchmark six new heuristics.
Cite as
Leo Liberti and Claudia D'Ambrosio. The Isomap Algorithm in Distance Geometry. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{liberti_et_al:LIPIcs.SEA.2017.5,
author = {Liberti, Leo and D'Ambrosio, Claudia},
title = {{The Isomap Algorithm in Distance Geometry}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {5:1--5:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.5},
URN = {urn:nbn:de:0030-drops-76079},
doi = {10.4230/LIPIcs.SEA.2017.5},
annote = {Keywords: distance geometry problem, protein conformation, heuristics}
}
Document
Distributed Domain Propagation
Abstract
Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite its simplicity, portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after the domain of a variable has been reduced. In this paper we introduce distributed domain propagation, a technique that shares bound tightenings across solvers to trigger further domain propagations. We investigate its impact in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions, they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.
Cite as
Robert Lion Gottwald, Stephen J. Maher, and Yuji Shinano. Distributed Domain Propagation. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 6:1-6:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{gottwald_et_al:LIPIcs.SEA.2017.6,
author = {Gottwald, Robert Lion and Maher, Stephen J. and Shinano, Yuji},
title = {{Distributed Domain Propagation}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {6:1--6:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.6},
URN = {urn:nbn:de:0030-drops-76236},
doi = {10.4230/LIPIcs.SEA.2017.6},
annote = {Keywords: mixed integer programming, parallelization, domain propagation, portfolio solvers}
}
Document
Efficient Algorithms for k-Regret Minimizing Sets
Abstract
A regret minimizing set Q is a small size representation of a much larger database P so that user queries executed on Q return answers whose scores are not much worse than those on the full dataset. In particular, a k-regret minimizing set has the property that the regret ratio between the score of the top-1 item in Q and the score of the top-k item in P is minimized, where the score of an item is the inner product of the item's attributes with a user's weight (preference) vector. The problem is challenging because we want to find a single representative set Q whose regret ratio is small with respect to all possible user weight vectors.
We show that k-regret minimization is NP-Complete for all dimensions d>=3, settling an open problem from Chester et al. [VLDB 2014]. Our main algorithmic contributions are two approximation algorithms, both with provable guarantees, one based on coresets and another based on hitting sets. We perform extensive experimental evaluation of our algorithms, using both real-world and synthetic data, and compare their performance against the solution proposed in [VLDB 14]. The results show that our algorithms are significantly faster and scalable to much larger sets than the greedy algorithm of Chester et al. for comparable quality answers.
Cite as
Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, and Subhash Suri. Efficient Algorithms for k-Regret Minimizing Sets. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.SEA.2017.7,
author = {Agarwal, Pankaj K. and Kumar, Nirman and Sintos, Stavros and Suri, Subhash},
title = {{Efficient Algorithms for k-Regret Minimizing Sets}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {7:1--7:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.7},
URN = {urn:nbn:de:0030-drops-76321},
doi = {10.4230/LIPIcs.SEA.2017.7},
annote = {Keywords: regret minimizing sets, skyline, top-k query, coreset, hitting set}
}
Document
Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs
Abstract
We present an implementation of a linear-time approximation scheme for the traveling salesman problem on planar graphs with edge weights. We observe that the theoretical algorithm involves constants that are too large for practical use. Our implementation, which is not subject to the theoretical algorithm's guarantee, can quickly find good tours in very large planar graphs.
Cite as
Amariah Becker, Eli Fox-Epstein, Philip N. Klein, and David Meierfrankenfeld. Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{becker_et_al:LIPIcs.SEA.2017.8,
author = {Becker, Amariah and Fox-Epstein, Eli and Klein, Philip N. and Meierfrankenfeld, David},
title = {{Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {8:1--8:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.8},
URN = {urn:nbn:de:0030-drops-76305},
doi = {10.4230/LIPIcs.SEA.2017.8},
annote = {Keywords: Traveling Salesman, Approximation Schemes, Planar Graph Algorithms, Algorithm Engineering}
}
Document
Approximating the Smallest 2-Vertex-Connected Spanning Subgraph via Low-High Orders
Abstract
Let G = (V, E) be a 2-vertex-connected directed graph with m edges and n vertices. We consider the problem of approximating the smallest 2-vertex connected spanning subgraph (2VCSS) of G, and provide new efficient algorithms for this problem based on a clever use of low-high orders. The best previously known algorithms were able to compute a 3/2-approximation in O(m n+n 2) time, or a 3-approximation faster in linear time. In this paper, we present a linear-time algorithm that achieves a better approximation ratio of 2, and another algorithm that matches the previous 3/2-approximation in O(m n + n 2 ) time. We conducted a thorough experimental evaluation of all the above algorithms on a variety of input graphs. The experimental results show that both our two new algorithms perform well in practice. In particular, in our experiments the new 3/2-approximation algorithm was always faster than the previous 3/2-approximation algorithm, while their two approximation ratios were close. On the other side, our new linear-time algorithm yielded consistently better approximation ratios than the previously known linear-time algorithm, at the price of a small overhead in the running time.
Cite as
Loukas Georgiadis, Giuseppe F. Italiano, and Aikaterini Karanasiou. Approximating the Smallest 2-Vertex-Connected Spanning Subgraph via Low-High Orders. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{georgiadis_et_al:LIPIcs.SEA.2017.9,
author = {Georgiadis, Loukas and Italiano, Giuseppe F. and Karanasiou, Aikaterini},
title = {{Approximating the Smallest 2-Vertex-Connected Spanning Subgraph via Low-High Orders}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {9:1--9:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.9},
URN = {urn:nbn:de:0030-drops-76299},
doi = {10.4230/LIPIcs.SEA.2017.9},
annote = {Keywords: 2-vertex connectivity, approximation algorithms, directed graphs}
}
Document
Extending Search Phases in the Micali-Vazirani Algorithm
Abstract
The Micali-Vazirani algorithm is an augmenting path algorithm that offers the best theoretical runtime of O(n^{0.5} m) for solving the maximum cardinality matching problem for non-bipartite graphs. This paper builds upon the algorithm by focusing on the bottleneck caused by its search phase structure and proposes a new implementation that improves efficiency by extending the search phases in order to find more augmenting paths. Experiments on different types of randomly generated and real world graphs demonstrate this new implementation's effectiveness and limitations.
Cite as
Michael Huang and Clifford Stein. Extending Search Phases in the Micali-Vazirani Algorithm. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{huang_et_al:LIPIcs.SEA.2017.10,
author = {Huang, Michael and Stein, Clifford},
title = {{Extending Search Phases in the Micali-Vazirani Algorithm}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {10:1--10:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.10},
URN = {urn:nbn:de:0030-drops-76141},
doi = {10.4230/LIPIcs.SEA.2017.10},
annote = {Keywords: matching, graph algorithm, experimental evaluation, non-bipartite}
}
Document
A Framework of Dynamic Data Structures for String Processing
Abstract
In this paper we present DYNAMIC, an open-source C++ library implementing dynamic compressed data structures for string manipulation. Our framework includes useful tools such as searchable partial sums, succinct/gap-encoded bitvectors, and entropy/run-length compressed strings and FM indexes. We prove close-to-optimal theoretical bounds for the resources used by our structures, and show that our theoretical predictions are empirically tightly verified in practice. To conclude, we turn our attention to applications. We compare the performance of five recently-published compression algorithms implemented using DYNAMIC with those of state-of-the-art tools performing the same task. Our experiments show that algorithms making use of dynamic compressed data structures can be up to three orders of magnitude more space-efficient (albeit slower) than classical ones performing the same tasks.
Cite as
Nicola Prezza. A Framework of Dynamic Data Structures for String Processing. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{prezza:LIPIcs.SEA.2017.11,
author = {Prezza, Nicola},
title = {{A Framework of Dynamic Data Structures for String Processing}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.11},
URN = {urn:nbn:de:0030-drops-76028},
doi = {10.4230/LIPIcs.SEA.2017.11},
annote = {Keywords: C++, dynamic, compression, data structure, bitvector, string}
}
Document
Practical Range Minimum Queries Revisited
Abstract
Finding the position of the minimal element in a subarray A[i..j] of an array A of size n is a fundamental operation in many applications. In 2011, Fischer and Heun presented the first index of size 2n+o(n) bits which answers the operation in constant time for any subarray. The index can be computed in linear time and queries can be answered without consulting the original array. The most recent and currently fastest practical index is due to Ferrada and Navarro (DCC'16). It reduces the range minimum query (RMQ) to more fundamental and well studied queries on binary vectors, namely rank and select, and a RMQ query on an array of sublinear size derived from A. A range min-max tree is employed to solve this recursive RMQ call. In this paper, we review their practical design and suggest a series of changes which result in consistently faster query times. Specifically, we provide a customized select implementation, switch to two levels of recursion, and use the sparse table solution for the recursion base case instead of a range min-max tree.
We provide an extensive empirical evaluation of our new implementation and also compare it to the state of the art. Our experimental study shows that our proposal significantly outperforms the previous solutions on established benchmarks (up to a factor of three) and furthermore accelerates real world applications such as traversing a succinct tree or listing all distinct elements in an interval of an array.
Cite as
Niklas Baumstark, Simon Gog, Tobias Heuer, and Julian Labeit. Practical Range Minimum Queries Revisited. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{baumstark_et_al:LIPIcs.SEA.2017.12,
author = {Baumstark, Niklas and Gog, Simon and Heuer, Tobias and Labeit, Julian},
title = {{Practical Range Minimum Queries Revisited}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {12:1--12:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.12},
URN = {urn:nbn:de:0030-drops-76158},
doi = {10.4230/LIPIcs.SEA.2017.12},
annote = {Keywords: Succinct Data Structures, Range Minimum Queries, Algorithm Engineering}
}
Document
Compression with the tudocomp Framework
Abstract
We present a framework facilitating the implementation and comparison of text compression algorithms. We evaluate its features by a case study on two novel compression algorithms based on the Lempel-Ziv compression schemes that perform well on highly repetitive texts.
Cite as
Patrick Dinklage, Johannes Fischer, Dominik Köppl, Marvin Löbel, and Kunihiko Sadakane. Compression with the tudocomp Framework. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{dinklage_et_al:LIPIcs.SEA.2017.13,
author = {Dinklage, Patrick and Fischer, Johannes and K\"{o}ppl, Dominik and L\"{o}bel, Marvin and Sadakane, Kunihiko},
title = {{Compression with the tudocomp Framework}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {13:1--13:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.13},
URN = {urn:nbn:de:0030-drops-76015},
doi = {10.4230/LIPIcs.SEA.2017.13},
annote = {Keywords: lossless compression, compression framework, compression library, algorithm engineering, application of string algorithms}
}
Document
Algorithm Engineering for All-Pairs Suffix-Prefix Matching
Abstract
All-pairs suffix-prefix matching is an important part of DNA sequence assembly where it is the most time-consuming part of the whole assembly. Although there are algorithms for all-pairs suffix-prefix matching which are optimal in the asymptotic time complexity, they are slower than SOF and Readjoiner which are state-of-the-art algorithms used in practice. In this paper we present an algorithm for all-pairs suffix-prefix matching that uses a simple data structure for storing input strings and advanced algorithmic techniques for matching, which together lead to fast running time in practice. Our algorithm is 14 times faster than SOF and 18 times faster than Readjoiner on average in real datasets and random datasets.
Cite as
Jihyuk Lim and Kunsoo Park. Algorithm Engineering for All-Pairs Suffix-Prefix Matching. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{lim_et_al:LIPIcs.SEA.2017.14,
author = {Lim, Jihyuk and Park, Kunsoo},
title = {{Algorithm Engineering for All-Pairs Suffix-Prefix Matching}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {14:1--14:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.14},
URN = {urn:nbn:de:0030-drops-76174},
doi = {10.4230/LIPIcs.SEA.2017.14},
annote = {Keywords: all-pairs suffix-prefix matching, algorithm engineering, DNA sequence assembly}
}
Document
The Quantile Index - Succinct Self-Index for Top-k Document Retrieval
Abstract
One of the central problems in information retrieval is that of finding the k documents in a large text collection that best match a query given by a user. A recent result of Navarro & Nekrich (SODA 2012) showed that single term and phrase queries of length m can be solved in optimal O(m+k) time using a linear word sized index. While a verbatim implementation of the index would be at least an order of magnitude larger than the original collection, various authors incrementally improved the index to a point where the space requirement is currently within a factor of 1.5 to 2.0 of the text size for standard collections.
In this paper, we propose a new time/space trade-off for different top-k indexes. This is achieved by sampling only a quantile of the postings in the original inverted file or suffix array-based index. For those queries that cannot be answered using the sampled version of the index we show how to compute the query results on the fly efficiently. As an example, we apply our method to the top-k framework by Navarro & Nekrich. Under probabilistic assumptions that hold for most standard texts, and for a standard scoring function called term frequency, our index can be represented with only sublinearly many bits plus the space needed for a compressed suffix array of the text, while maintaining poly-logarithmic query times. We evaluate our solution on real-world datasets and compare its practical space usage and performance against state-of-the-art implementations. Our experiments show that our index compresses below the size of the original text. To our knowledge it is the first suffix array-based text index that is able to break this bound in practice even for non-repetitive collections, while still maintaining reasonable query times of under half a millisecond on average for top-10 queries.
Cite as
Niklas Baumstark, Simon Gog, Tobias Heuer, and Julian Labeit. The Quantile Index - Succinct Self-Index for Top-k Document Retrieval. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{baumstark_et_al:LIPIcs.SEA.2017.15,
author = {Baumstark, Niklas and Gog, Simon and Heuer, Tobias and Labeit, Julian},
title = {{The Quantile Index - Succinct Self-Index for Top-k Document Retrieval}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {15:1--15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.15},
URN = {urn:nbn:de:0030-drops-76183},
doi = {10.4230/LIPIcs.SEA.2017.15},
annote = {Keywords: Text Indexing, Succinct Data Structures, Top-k Document Retrieval}
}
Document
Online Construction of Wavelet Trees
Abstract
The wavelet tree (WT) is a flexible and efficient data structure for representing character strings in succinct space, while allowing for fast generalised rank, select and access operations. As such, they play an important role in modern text indexing methods. However, despite their popularity, not many algorithms have been published concerning their construction. In particular, while the WT is capable of representing a sequence of length n over an alphabet of size m in n\lg m+o(n\lg m) bits, much more space is typically used for its construction. Here we propose an O(n\lg m)-time online method for the construction of the WT, requiring no prior knowledge about the input alphabet. The proposed algorithm is conceptually simpler than other state-of-the-art methods, while having comparable time performance and being more space-efficient in practice, since it performs just one pass over the input text and uses little extra space other than for the structure itself, as shown both theoretically and empirically.
Cite as
Paulo G. S. da Fonseca and Israel B. F. da Silva. Online Construction of Wavelet Trees. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{dafonseca_et_al:LIPIcs.SEA.2017.16,
author = {da Fonseca, Paulo G. S. and da Silva, Israel B. F.},
title = {{Online Construction of Wavelet Trees}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {16:1--16:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.16},
URN = {urn:nbn:de:0030-drops-76135},
doi = {10.4230/LIPIcs.SEA.2017.16},
annote = {Keywords: Wavelet tree, Online construction}
}
Document
Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet
Abstract
The suffix array augmented with the LCP array is perhaps the most important data structure in modern string processing. There has been a lot of recent research activity on constructing these arrays in external memory. In this paper, we engineer the two fastest LCP array construction algorithms (ESA 2016) and improve them in three ways. First, we speed up the algorithms by up to a factor of two through parallelism. Just 8 threads is sufficient for making the algorithms essentially I/O bound. Second, we reduce the disk space usage of the algorithms making them in-place: The input (text and suffix array) is treated as read-only and the working disk space never exceeds the size of the final output (the LCP array). Third, we add support for large alphabets. All previous implementations assume the byte alphabet.
Cite as
Juha Kärkkäinen and Dominik Kempa. Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{karkkainen_et_al:LIPIcs.SEA.2017.17,
author = {K\"{a}rkk\"{a}inen, Juha and Kempa, Dominik},
title = {{Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {17:1--17:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.17},
URN = {urn:nbn:de:0030-drops-76116},
doi = {10.4230/LIPIcs.SEA.2017.17},
annote = {Keywords: LCP array, suffix array, external memory algorithms}
}
Document
Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees
Abstract
In a personalized route planning query, a user can specify how relevant different criteria as travel time, gas consumption, scenicness, etc. are for his individual definition of an optimal route. Recently developed acceleration schemes for personalized route planning, which rely on preprocessing, achieve a significant speed-up over the Dijkstra baseline for a small number of criteria. But for more than five criteria, either the preprocessing becomes too complicated or the query answering is slow. In this paper, we first present a new LP-based preprocessing technique which allows to deal with many criteria efficiently. In addition, we show how to further reduce query times for all known personalized route planning acceleration schemes by considering approximate queries. We design a data structure which allows not only to have personalized costs but also individual approximation guarantees per query, allowing to trade solution quality against query time at the user's discretion. This data structure is the first to enable a speed-up of more than 100 for ten criteria while accepting only 0.01% increased costs.
Cite as
Stefan Funke, Sören Laue, and Sabine Storandt. Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{funke_et_al:LIPIcs.SEA.2017.18,
author = {Funke, Stefan and Laue, S\"{o}ren and Storandt, Sabine},
title = {{Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {18:1--18:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.18},
URN = {urn:nbn:de:0030-drops-76255},
doi = {10.4230/LIPIcs.SEA.2017.18},
annote = {Keywords: personalized route planning, contraction hierarchies, linear program, separation oracle, approximate queries}
}
Document
Consumption Profiles in Route Planning for Electric Vehicles: Theory and Applications
Abstract
In route planning for electric vehicles (EVs), consumption profiles are a functional representation of optimal energy consumption between two locations, subject to initial state of charge. Efficient computation of profiles is a relevant problem on its own, but also a fundamental ingredient to many route planning approaches for EVs. In this work, we show that the complexity of a profile is at most linear in the graph size. Based on this insight, we derive a polynomial-time algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. Exploiting efficient profile search, our approach also allows partial recharging at charging stations to save energy. In a sense, our results close the gap between efficient techniques for energy-optimal routes (based on simpler models) and NP-hard time-constrained problems involving charging stops for EVs. We propose a practical implementation, which we carefully integrate with Contraction Hierarchies and A* search. Even though the practical variant formally drops correctness, a comprehensive experimental study on a realistic, large-scale road network reveals that it always finds the optimal solution in our tests and computes even long-distance routes with charging stops in less than 300 ms.
Cite as
Moritz Baum, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Consumption Profiles in Route Planning for Electric Vehicles: Theory and Applications. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{baum_et_al:LIPIcs.SEA.2017.19,
author = {Baum, Moritz and Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
title = {{Consumption Profiles in Route Planning for Electric Vehicles: Theory and Applications}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {19:1--19:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.19},
URN = {urn:nbn:de:0030-drops-76088},
doi = {10.4230/LIPIcs.SEA.2017.19},
annote = {Keywords: electric vehicles, charging station, shortest paths, route planning, profile search, algorithm engineering}
}
Document
Efficient Traffic Assignment for Public Transit Networks
Abstract
We study the problem of computing traffic assignments for public transit networks: Given a public transit network and a demand (i.e. a list of passengers, each with associated origin, destination, and departure time), the objective is to compute the utilization of every vehicle. Efficient assignment algorithms are a core component of many urban traffic planning tools. In this work, we present a novel algorithm for computing public transit assignments. Our approach is based upon a microscopic Monte Carlo simulation of individual passengers. In order to model realistic passenger behavior, we base all routing decisions on travel time, number of transfers, time spent walking or waiting, and delay robustness. We show how several passengers can be processed during a single scan of the network, based on the Connection Scan Algorithm [Dibbelt et al., LNCS Springer 2013], resulting in a highly efficient algorithm. We conclude with an experimental study, showing that our assignments are comparable in terms of quality to the state-of-the-art. Using the parallelized version of our algorithm, we are able to compute a traffic assignment for more than ten million passengers in well below a minute, which outperforms previous works by more than an order of magnitude.
Cite as
Lars Briem, Sebastian Buck, Holger Ebhart, Nicolai Mallig, Ben Strasser, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf. Efficient Traffic Assignment for Public Transit Networks. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{briem_et_al:LIPIcs.SEA.2017.20,
author = {Briem, Lars and Buck, Sebastian and Ebhart, Holger and Mallig, Nicolai and Strasser, Ben and Vortisch, Peter and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
title = {{Efficient Traffic Assignment for Public Transit Networks}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {20:1--20:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.20},
URN = {urn:nbn:de:0030-drops-76109},
doi = {10.4230/LIPIcs.SEA.2017.20},
annote = {Keywords: Algorithms, Optimization, Route planning, Public transportation}
}
Document
Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure
Abstract
We present an improved coarsening process for multilevel hypergraph partitioning that incorporates global information about the community structure. Community detection is performed via modularity maximization on a bipartite graph representation. The approach is made suitable for different classes of hypergraphs by defining weights for the graph edges that express structural properties of the hypergraph. We integrate our approach into a leading multilevel hypergraph partitioner with strong local search algorithms and perform extensive experiments on a large benchmark set of hypergraphs stemming from application areas such as VLSI design, SAT solving, and scientific computing. Our results indicate that respecting community structure during coarsening not only significantly improves the solutions found by the initial partitioning algorithm, but also consistently improves overall solution quality.
Cite as
Tobias Heuer and Sebastian Schlag. Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{heuer_et_al:LIPIcs.SEA.2017.21,
author = {Heuer, Tobias and Schlag, Sebastian},
title = {{Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {21:1--21:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.21},
URN = {urn:nbn:de:0030-drops-76226},
doi = {10.4230/LIPIcs.SEA.2017.21},
annote = {Keywords: multilevel hypergraph partitioning, coarsening algorithms, community detection}
}
Document
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
Abstract
We consider the minimum spanning tree (MST) problem in an uncertainty model where uncertain edge weights can be explored at extra cost. The task is to find an MST by querying a minimum number of edges for their exact weight. This problem has received quite some attention from the algorithms theory community. In this paper, we conduct the first practical experiments for MST under uncertainty, theoretically compare three known algorithms, and compare theoretical with practical behavior of the algorithms. Among others, we observe that the average performance and the absolute number of queries are both far from the theoretical worst-case bounds. Furthermore, we investigate a known general preprocessing procedure and develop an implementation thereof that maximally reduces the data uncertainty. We also characterize a class of instances that is solved completely by our preprocessing. Our experiments are based on practical data from an application in telecommunications and uncertainty instances generated from the standard TSPLib graph library.
Cite as
Jacob Focke, Nicole Megow, and Julie Meißner. Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{focke_et_al:LIPIcs.SEA.2017.22,
author = {Focke, Jacob and Megow, Nicole and Mei{\ss}ner, Julie},
title = {{Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {22:1--22:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.22},
URN = {urn:nbn:de:0030-drops-76202},
doi = {10.4230/LIPIcs.SEA.2017.22},
annote = {Keywords: MST, explorable uncertainty, competitive ratio, experimental algorithms}
}
Document
Faster Betweenness Centrality Updates in Evolving Networks
Abstract
Finding central nodes is a fundamental problem in network analysis. Betweenness centrality is a well-known measure which quantifies the importance of a node based on the fraction of shortest paths going though it. Due to the dynamic nature of many today’s networks, algorithms that quickly update centrality scores have become a necessity. For betweenness, several dynamic algorithms have been proposed over the years, targeting different update types (incremental- and decremental-only, fully-dynamic). In this paper we introduce a new dynamic algorithm for updating betweenness centrality after an edge insertion or an edge weight decrease. Our method is a combination of two independent contributions: a faster algorithm for updating pairwise distances as well as number of shortest paths, and a faster algorithm for updating dependencies. Whereas the worst-case running time of our algorithm is the same as recomputation, our techniques considerably reduce the number of operations performed by existing dynamic betweenness algorithms. Our experimental evaluation on a variety of real-world networks reveals that our approach is significantly faster than the current state-of-the-art dynamic algorithms, approximately by one order of magnitude on average.
Cite as
Elisabetta Bergamini, Henning Meyerhenke, Mark Ortmann, and Arie Slobbe. Faster Betweenness Centrality Updates in Evolving Networks. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{bergamini_et_al:LIPIcs.SEA.2017.23,
author = {Bergamini, Elisabetta and Meyerhenke, Henning and Ortmann, Mark and Slobbe, Arie},
title = {{Faster Betweenness Centrality Updates in Evolving Networks}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {23:1--23:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.23},
URN = {urn:nbn:de:0030-drops-76093},
doi = {10.4230/LIPIcs.SEA.2017.23},
annote = {Keywords: Graph algorithms, shortest paths, distances, dynamic algorithms}
}
Document
Fast Deterministic Selection
Abstract
The selection problem, in forms such as finding the median or choosing the k top ranked items in a dataset, is a core task in computing with numerous applications in fields as diverse as statistics, databases, Machine Learning, finance, biology, and graphics. The selection algorithm Median of Medians, although a landmark theoretical achievement, is seldom used in practice because it is slower than simple approaches based on sampling. The main contribution of this paper is a fast linear-time deterministic selection algorithm MedianOfNinthers based on a refined definition of MedianOfMedians. A complementary algorithm MedianOfExtrema is also proposed. These algorithms work together to solve the selection problem in guaranteed linear time, faster than state-of-the-art baselines, and without resorting to randomization, heuristics, or fallback approaches for pathological cases. We demonstrate results on uniformly distributed random numbers, typical low-entropy artificial datasets, and real-world data. Measurements are open-sourced alongside the implementation at https://github.com/andralex/MedianOfNinthers.
Cite as
Andrei Alexandrescu. Fast Deterministic Selection. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{alexandrescu:LIPIcs.SEA.2017.24,
author = {Alexandrescu, Andrei},
title = {{Fast Deterministic Selection}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {24:1--24:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.24},
URN = {urn:nbn:de:0030-drops-76122},
doi = {10.4230/LIPIcs.SEA.2017.24},
annote = {Keywords: Selection Problem, Quickselect, Median of Medians, Algorithm Engineering, Algorithmic Libraries}
}
Document
Fast and Scalable Minimal Perfect Hashing for Massive Key Sets
Abstract
Minimal perfect hash functions provide space-efficient and collision-free hashing on static sets. Existing algorithms and implementations that build such functions have practical limitations on the number of input elements they can process, due to high construction time, RAM or external memory usage. We revisit a simple algorithm and show that it is highly competitive with the state of the art, especially in terms of construction time and memory usage. We provide a parallel C++ implementation called BBhash. It is capable of creating a minimal perfect hash function of 10^{10} elements in less than 7 minutes using 8 threads and 5 GB of memory, and the resulting function uses 3.7 bits/element. To the best of our knowledge, this is also the first implementation that has been successfully tested on an input of cardinality 10^{12}.
Source code: https://github.com/rizkg/BBHash
Cite as
Antoine Limasset, Guillaume Rizk, Rayan Chikhi, and Pierre Peterlongo. Fast and Scalable Minimal Perfect Hashing for Massive Key Sets. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{limasset_et_al:LIPIcs.SEA.2017.25,
author = {Limasset, Antoine and Rizk, Guillaume and Chikhi, Rayan and Peterlongo, Pierre},
title = {{Fast and Scalable Minimal Perfect Hashing for Massive Key Sets}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {25:1--25:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.25},
URN = {urn:nbn:de:0030-drops-76196},
doi = {10.4230/LIPIcs.SEA.2017.25},
annote = {Keywords: Minimal Perfect Hash Functions, Algorithms, Data Structures, Big Data}
}
Document
Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory
Abstract
Random graph models, originally conceived to study the structure of networks and the emergence of their properties, have become an indispensable tool for experimental algorithmics. Amongst them, hyperbolic random graphs form a well-accepted family, yielding realistic complex networks while being both mathematically and algorithmically tractable. We introduce two generators MemGen and HyperGen for the G_{alpha,C}(n) model, which distributes n random points within a hyperbolic plane and produces m=n*d/2 undirected edges for all point pairs close by; the expected average degree d and exponent 2*alpha+1 of the power-law degree distribution are controlled by alpha>1/2 and C. Both algorithms emit a stream of edges which they do not have to store. MemGen keeps O(n) items in internal memory and has a time complexity of O(n*log(log n) + m), which is optimal for networks with an average degree of d=Omega(log(log n)). For realistic values of d=o(n / log^{1/alpha}(n)), HyperGen reduces the memory footprint to O([n^{1-alpha}*d^alpha + log(n)]*log(n)).
In an experimental evaluation, we compare HyperGen with four generators among which it is consistently the fastest. For small d=10 we measure a speed-up of 4.0 compared to the fastest publicly available generator increasing to 29.6 for d=1000. On commodity hardware, HyperGen produces 3.7e8 edges per second for graphs with 1e6 < m < 1e12 and alpha=1, utilising less than 600MB of RAM. We demonstrate nearly linear scalability on an Intel Xeon Phi.
Cite as
Manuel Penschuck. Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 26:1-26:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{penschuck:LIPIcs.SEA.2017.26,
author = {Penschuck, Manuel},
title = {{Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {26:1--26:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.26},
URN = {urn:nbn:de:0030-drops-76218},
doi = {10.4230/LIPIcs.SEA.2017.26},
annote = {Keywords: Random hyperbolic graph generator, streaming algorithm}
}
Document
Incremental Low-High Orders of Directed Graphs and Applications
Abstract
A flow graph G = (V, E, s) is a directed graph with a distinguished start vertex s. The dominator tree D of G is a tree rooted at s, such that a vertex v is an ancestor of a vertex w if and only if all paths from s to w include v. The dominator tree is a central tool in program optimization and code generation, and has many applications in other diverse areas including constraint programming, circuit testing, biology, and in algorithms for graph connectivity problems. A low-high order of G is a preorder d of D that certifies the correctness of D, and has further applications in connectivity and path-determination problems.
In this paper we consider how to maintain efficiently a low-high order of a flow graph incrementally under edge insertions. We present algorithms that run in O(mn) total time for a sequence of edge insertions in a flow graph with n vertices, where m is the total number of edges after all insertions. These immediately provide the first incremental certifying algorithms for maintaining the dominator tree in O(mn) total time, and also imply incremental algorithms for other problems. Hence, we provide a substantial improvement over the O(m^2) straightforward algorithms, which recompute the solution from scratch after each edge insertion. Furthermore, we provide efficient implementations of our algorithms and conduct an extensive experimental study on real-world graphs taken from a variety of application areas. The experimental results show that our algorithms perform very well in practice.
Cite as
Loukas Georgiadis, Konstantinos Giannis, Aikaterini Karanasiou, and Luigi Laura. Incremental Low-High Orders of Directed Graphs and Applications. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{georgiadis_et_al:LIPIcs.SEA.2017.27,
author = {Georgiadis, Loukas and Giannis, Konstantinos and Karanasiou, Aikaterini and Laura, Luigi},
title = {{Incremental Low-High Orders of Directed Graphs and Applications}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {27:1--27:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.27},
URN = {urn:nbn:de:0030-drops-76319},
doi = {10.4230/LIPIcs.SEA.2017.27},
annote = {Keywords: connectivity, directed graphs, dominators, dynamic algorithms}
}
Document
Jdrasil: A Modular Library for Computing Tree Decompositions
Abstract
While the theoretical aspects concerning the computation of tree width - one of the most important graph parameters - are well understood, it is not clear how it can be computed practically. We present the open source Java library Jdrasil that implements several different state of the art algorithms for this task. By experimentally comparing these algorithms, we show that the default choices made in Jdrasil lead to an competitive implementation (it took the third place in the first PACE challenge) while also being easy to use and easy to extend.
Cite as
Max Bannach, Sebastian Berndt, and Thorsten Ehlers. Jdrasil: A Modular Library for Computing Tree Decompositions. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{bannach_et_al:LIPIcs.SEA.2017.28,
author = {Bannach, Max and Berndt, Sebastian and Ehlers, Thorsten},
title = {{Jdrasil: A Modular Library for Computing Tree Decompositions}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {28:1--28:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.28},
URN = {urn:nbn:de:0030-drops-76051},
doi = {10.4230/LIPIcs.SEA.2017.28},
annote = {Keywords: tree width, algorithmic library, experimental evaluation}
}
Document
On the Separation of Topology-Free Rank Inequalities for the Max Stable Set Problem
Abstract
In the context of finding the largest stable set of a graph, rank inequalities prescribe that a stable set can contain, from any induced subgraph of the original graph, at most as many vertices as the stability number of the former. Although these inequalities subsume many of the valid inequalities known for the problem, their exact separation has only been investigated in few special cases obtained by restricting the induced subgraph to a specific topology.
In this work, we propose a different approach in which, rather than imposing topological restrictions on the induced subgraph, we assume the right-hand side of the inequality to be fixed to a given (but arbitrary) constant. We then study the arising separation problem, which corresponds to the problem of finding a maximum weight subgraph with a bounded stability number. After proving its hardness and giving some insights on its polyhedral structure, we propose an exact branch-and-cut method for its solution. Computational results show that the separation of topology-free rank inequalities with a fixed right-hand side yields a substantial improvement over the bound provided by the fractional clique polytope (which is obtained with rank inequalities where the induced subgraph is restricted to a clique), often better than that obtained with Lovász’s Theta function via semidefinite programming.
Cite as
Stefano Coniglio and Stefano Gualandi. On the Separation of Topology-Free Rank Inequalities for the Max Stable Set Problem. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{coniglio_et_al:LIPIcs.SEA.2017.29,
author = {Coniglio, Stefano and Gualandi, Stefano},
title = {{On the Separation of Topology-Free Rank Inequalities for the Max Stable Set Problem}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {29:1--29:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.29},
URN = {urn:nbn:de:0030-drops-76266},
doi = {10.4230/LIPIcs.SEA.2017.29},
annote = {Keywords: Maximum stable set problem, rank inequalities, cutting planes, integer programming, combinatorial optimization}
}
Document
Graph Partitioning with Acyclicity Constraints
Abstract
Graphs are widely used to model execution dependencies in applications. In particular, the NP-complete problem of partitioning a graph under constraints receives enormous attention by researchers because of its applicability in multiprocessor scheduling. We identified the additional constraint of acyclic dependencies between blocks when mapping streaming applications to a heterogeneous embedded multiprocessor. Existing algorithms and heuristics do not address this requirement and deliver results that are not applicable for our use-case. In this work, we show that this more constrained version of the graph partitioning problem is NP-complete and present heuristics that achieve a close approximation of the optimal solution found by an exhaustive search for small problem instances and much better scalability for larger instances. In addition, we can show a positive impact on the schedule of a real imaging application that improves communication volume and execution time.
Cite as
Orlando Moreira, Merten Popp, and Christian Schulz. Graph Partitioning with Acyclicity Constraints. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{moreira_et_al:LIPIcs.SEA.2017.30,
author = {Moreira, Orlando and Popp, Merten and Schulz, Christian},
title = {{Graph Partitioning with Acyclicity Constraints}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {30:1--30:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.30},
URN = {urn:nbn:de:0030-drops-76042},
doi = {10.4230/LIPIcs.SEA.2017.30},
annote = {Keywords: Graph Partitioning, Computer Vision and Imaging Applications}
}
Document
Bilevel Programming Approaches to the Computation of Optimistic and Pessimistic Single-Leader-Multi-Follower Equilibria
Abstract
We study the problem of computing an equilibrium in leader-follower games with a single leader and multiple followers where, after the leader’s commitment to a mixed strategy, the followers play simultaneously in a noncooperative way, reaching a Nash equilibrium. We tackle the problem from a bilevel programming perspective. Since, given the leader’s strategy, the followers’ subgame may admit multiple Nash equilibria, we consider the cases where the followers play either the best (optimistic) or the worst (pessimistic) Nash equilibrium in terms of the leader’s utility. For the optimistic case, we propose three formulations which cast the problem into a single level mixed-integer nonconvex program. For the pessimistic case, which, as we show, may admit a supremum but not a maximum, we develop an ad hoc branch-and-bound algorithm. Computational results are reported and illustrated.
Cite as
Nicola Basilico, Stefano Coniglio, Nicola Gatti, and Alberto Marchesi. Bilevel Programming Approaches to the Computation of Optimistic and Pessimistic Single-Leader-Multi-Follower Equilibria. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{basilico_et_al:LIPIcs.SEA.2017.31,
author = {Basilico, Nicola and Coniglio, Stefano and Gatti, Nicola and Marchesi, Alberto},
title = {{Bilevel Programming Approaches to the Computation of Optimistic and Pessimistic Single-Leader-Multi-Follower Equilibria}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {31:1--31:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.31},
URN = {urn:nbn:de:0030-drops-76249},
doi = {10.4230/LIPIcs.SEA.2017.31},
annote = {Keywords: Stackelberg games; Nash equilibria; Game theory; Bilevel and nonlinear programming; Branch-and-bound}
}
Document
The Impact of Landscape Sparsification on Modelling and Analysis of the Invasion Process
Abstract
Climate change is a major threat to species, unless their populations are able to invade and colonise new landscapes of more suitable environment. In this paper, we propose a new model of the invasion process using a tool of landscape network sparsification to efficiently estimate a duration of the process. More specifically, we aim to simplify the structure of large landscapes using the concept of sparsification in order to substantially decrease the time required to compute a good estimate of the invasion time in these landscapes. For this purpose, two different simulation methods have been compared: full and R-local simulations, which are based on the concept of dense and sparse networks, respectively. These two methods are applied to real heterogeneous landscapes in the United Kingdom to compute the total estimated time to invade landscapes. We examine how the duration of the invasion process is affected by different factors, such as dispersal coefficient, landscape quality and landscape size. Extensive evaluations have been carried out, showing that the R-local method approximates the duration of the invasion process to high accuracy using a substantially reduced computation time.
Cite as
Daniyah A. Aloqalaa, Jenny A. Hodgson, and Prudence W. H. Wong. The Impact of Landscape Sparsification on Modelling and Analysis of the Invasion Process. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{aloqalaa_et_al:LIPIcs.SEA.2017.32,
author = {Aloqalaa, Daniyah A. and Hodgson, Jenny A. and Wong, Prudence W. H.},
title = {{The Impact of Landscape Sparsification on Modelling and Analysis of the Invasion Process}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {32:1--32:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.32},
URN = {urn:nbn:de:0030-drops-76160},
doi = {10.4230/LIPIcs.SEA.2017.32},
annote = {Keywords: Landscape sparsification, invasion process, network sparsification, dense and sparse networks}
}
Document
Ad-Hoc Affectance-Selective Families for Layer Dissemination
Abstract
Information dissemination protocols for ad-hoc wireless networks frequently use a minimal subset of the available communication links, defining a rooted "“broadcast"” tree. In this work, we focus on the core challenge of disseminating from one layer to the next one of such tree. We call this problem Layer Dissemination. We study Layer Dissemination under a generalized model of interference, called affectance. The affectance model subsumes previous models, such as Radio Network and Signal to Inteference-plus-Noise Ratio. We present randomized and deterministic protocols for Layer Dissemination. These protocols are based on a combinatorial object that we call Affectance-selective Families. Our approach combines an engineering solution with theoretical guarantees. That is, we provide a method to characterize the network with a global measure of affectance based on measurements of interference in the specific deployment area. Then, our protocols distributedly produce an ad-hoc transmissions schedule for dissemination. In the randomized protocol only the network characterization is needed, whereas the deterministic protocol requires full knowledge of affectance. Our theoretical analysis provides guarantees on schedule length. We also present simulations of a real network-deployment area contrasting the perform- ance of our randomized protocol, which takes into account affectance, against previous work for interference models that ignore some physical constraints. The striking improvement in performance shown by our simulations show the importance of utilizing a more physically-accurate model of interference that takes into account other effects beyond distance to transmitters.
Cite as
Harshita Kudaravalli and Miguel A. Mosteiro. Ad-Hoc Affectance-Selective Families for Layer Dissemination. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{kudaravalli_et_al:LIPIcs.SEA.2017.33,
author = {Kudaravalli, Harshita and Mosteiro, Miguel A.},
title = {{Ad-Hoc Affectance-Selective Families for Layer Dissemination}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {33:1--33:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.33},
URN = {urn:nbn:de:0030-drops-76064},
doi = {10.4230/LIPIcs.SEA.2017.33},
annote = {Keywords: Wireless Networks, Broadcast Protocols, Affectance, SINR}
}