ARCO Workshhop Fall 2014 - Abstracts

Jesper Mikkelsen, IMADA, SDU
The Advice Complexity of a Class of Hard Online Problems

Abstract: The advice complexity of an online problem is a measure of how much knowledge of the future an online algorithm needs in order to achieve a certain competitive ratio. We determine the advice complexity of hard online problems such as independent set, vertex cover, dominating set and disjoint path allocation. These problems are hard since a single wrong answer by the online algorithm can have devastating consequences. We show that log(1+(c-1)^{(c - 1)}/c^c)n = Θ(n/c) bits of advice are necessary and sucient (up to a lower-order term) to achieve a strict competitive ratio of c for each of these problems. This is done by introducing a new string guessing problem related to that of Bockenhauer et al. (Theoretical Computer Science 2014). It turns out that this gives a powerful but easy-to-use method for providing both upper and lower bounds on the advice complexity of an entire class of online problems. Joint work with Joan Boyar, Lene M. Favrholdt and Christian Kudahl.

Jesper Larsson, Malm Univ.
Efficient Representation for Online Suffix Tree Construction

Abstract: Suffix tree construction algorithms based on suffix links are popular because they are simple to implement, can operate online in linear time, and because the suffix links are often convenient for pattern matching. We present an approach using edge-oriented suffix links, which reduces the number of branch lookup operations (known to be a bottleneck in construction time) with some additional techniques to reduce construction cost. We discuss various eects of our approach and compare it to previous techniques. An experimental evaluation shows that we are able to reduce construction time to around half that of the original algorithm, and about two thirds that of previously known branch-reduced construction. Joint work with Kasper Fuglsang and Kenneth Karlsson.

Joachim Gudmundsson, Univ. of Sydney
Fast Algorithms for Approximate Frechet Matching Queries in Geometric Trees

Abstract: Let T be a tree in R^d and let D > 0 be a real number. The aim is to preprocess T into a data structure, such that for any polygonal query path Q, we can decide if T contains a path P whose Frechet distance to Q is at most D. For any real number  ε > 0, we present an efficient data structure that solves an approximate version of this problem for the case when T is c-packed and each of the edges of T and Q has length Ω(D). Joint work with Michiel Smid.

Rasmus Fonseca, DIKU, KU
Faster Exact Algorithms for Computing Steiner Trees in Higher Dimensional Euclidean Spaces

Abstract: The Euclidean Steiner tree problem asks for a network of minimum total length interconnecting a finite set of points in d-dimensional space. For d ≥ 3, only one practical algorithmic approach exists for this problem - proposed by Smith in 1992. A number of refinements of Smith's algorithm have increased the range of solvable problems a little, but it is still infeasible to solve problem instances with more than around 17 terminals. In this paper we firstly propose some additional improvements to Smith's algorithm. Secondly, we propose a new algorithmic paradigm called branch enumeration. Our experiments show that branch enumeration has similar performance as an optimized version of Smith's algorithm; furthermore, we argue that branch enumeration has the potential to push the boundary of solvable problems further. Joint work with Marcus Brazil, Pawel Winter and Martin Zachariasen.

Bength Nilsson, Malm Univ.
Using Maximum Coverage to Optimize Recommendation Systems in E-Commerce

Abstract: We study the problem of optimizing recommendation systems for e-commerce sites. We consider in particular a combinatorial solution to this optimization based on the well-known Maximum Coverage problem that asks for the k sets (products) that cover the most elements from a ground set (consumers). This formulation provides an abstract model for what k products should be recommended to maximize the probability of consumer purchase. Unfortunately, Maximum Coverage is NP-complete but an efficient approximation algorithm exists based on the Greedy methodology.

Eli Packer, IBM Haifa, visiting Malm Univ.
Hybrid Algorithms for Scheduling Sensors for Guarding Polygonal Domains

Abstract: We dene a new version of the art gallery problem in which each guard/sensor can be functional only for a limited period of time and the task is to schedule sets of sensors within the domain to maximize the total coverage time. We present an optimal algorithm and approximating heuristics for the problem and report on experiments with many dierent input sets.

Luis Cruz-Filipe, IMADA, SDU
Sorting Networks: the End Game

Abstract: Sorting networks are a very simple model of data-independent sorting algorithms, suitable for implementation in hardware. Proving optimality of a sorting network, whether in terms of necessary gates or in terms of execution steps, remains however a daunting task, as it requires showing that no smaller arrangements of gates can sort all outputs. Due to the huge combinatorial explosion, this problem has only been settled for inputs of small size, and all current results rely on breaking symmetries in the rst comparisons made. In this talk, we discuss the properties of the last comparators in a sorting network, and show how these results help both towards improving the best-known sorting networks or proving their optimality.

Valentin Polishchuk, Linkoping University
Algorithms in the sky: How to design an optimal airspace?

Abstract: Global growth of air transportation brings up the need for efficient utilization of available airspace resources. I will describe algorithmic challenges motivated by air traffic industry needs and highlight a future project (with an open PhD position) in the area of air traffic management.

Jyrki Katajainen, DIKU, Univ. of Copenhagen
What your teachers never told you about Fibonacci heaps

Abstract: No paper nor abstract yet; I just want to stimulate discussion.