Abstracts

Andreas Bjorklund, Lund University

Title: Faster 3-coloring for diameter two

Abstract

The complexity of 3-coloring an n-vertex graph of diameter two is unknown. That is, its decision version is not known to be NP-complete, yet the fastest known algorithms are far from polynomial. Mertzios and Spirakis [http://arxiv.org/abs/1202.4665] recently gave an algorithm that runs in $2^{O(\sqrt{n\log n})}$ time.

Given the similarity to the runtime of the fastest known graph isomorphism algorithm, they speculated that the two problems might be related. While that still may be, we break this apparent runtime similarity:

First, we present an algorithm for 3-coloring an n-vertex graph of diameter two that runs in $2^{O(\sqrt{n})}$ time.

Second, for many instances that meet the upper time bound for the algorithm above, we describe another algorithm that runs in $2^{O(n^{1/3+\epsilon}\log^2 n)}$ time. For any fixed $\epsilon>0$ it works for all graphs such that no pair of vertices have more than $n^{\epsilon}$ neighbors in common.

------------------------------------------------------------------

Marcus Brazil, University of Melbourne (visiting DIKU)

Title: Maximising the Lifetime of Robust Wireless Sensor Networks through Strategic Relay Placement.

Abstract

In network design, a bottleneck can be any node or link at which a performance objective attains its least desirable value. For example, in wireless sensor networks a key objective is to optimise the lifetime of individual nodes. Nodes communicating over large distances utilise the most energy and therefore die first due to battery depletion. Consequently these nodes are considered to be bottlenecks of the network, and can be identified as nodes incident to the longest links in the transmission network. Equivalently we may consider the longest links to be the bottlenecks, and this is the approach taken here.

This talk considers the problem of devising an efficient algorithm for adding a fixed number of relays to a sparse Wireless Sensor Network so that the longest "bottleneck" link in the associated transmission network is minimised. The network should also be robust, in the sense that the unexpected death of a single node will not disconnect the remainder of the network. This can be modelled as an optimisation problem known as the bottleneck 2-connected Steiner network problem. We show that this problem can be exactly and efficiently solved using the properties of combinatorial structures such as 2-relative neighbourhood graphs and farthest colour Voronoi diagrams. More generally, this talk demonstrates the important role graph theory and geometry can play in industrial optimisaiton problems such as the efficient design of wireless sensor networks.

-------------------------------------------------------------------

Bengt Nilsson, Malmoe University

Title: Combinatorial Methods for Optimizing Web Services

Abstract

We look at the problem of optimization of an web services such as e-commerce sites. We consider in particular a combinatorial solution to this optimization based on the well known Set Cover problem.

We exhibit test results on real data sets showing 5-10% increase in conversion rate using the Set Cover optimization method in comparison to the standard best seller "top list".--------------------------------------------------------------------

Carsten Witt, Technical University of Denmark, Kgs. Lyngby

Title: How to analyze evolutionary algorithms?

Abstract:

Evolutionary algorithms and other randomized search heuristics are successfully applied to solve optimization problems, but their theoretical foundation is still in its infancy. Even extremely simplified variants of evolutionary algorithms can be very hard to analyze since the algorithm designer did not have an analysis in mind.

In this talk, we focus on a simplified evolutionary algorithm called (1+1) EA and, as a benchmark problem, we study how fast it optimizes linear functions. At first glance, the problem looks innocent, and it is tempting to believe that the underlying stochastic process can be formulated using a classical coupon collector analysis. This is not the case. Despite technically involved analyses carried out over the last decade, there was until recently a gap of 39% between best known upper and lower bounds on the expected optimization time of the algorithm.

In the talk, we present drift analysis as a tool to close the gap and determine the expected optimization time exactly for the whole class of linear functions. This result has very strong implications. For the first time, it proves the optimality of the so-called mutation probability 1/n (n being the problem dimension), which is most often recommended by practitioners. Moreover, it identifies the artificially looking (1+1) EA as an optimal algorithm within the large class of mutation-based algorithms, where different population sizes and mutation probabilties may be used. Finally, we learn from the analysis that the stochastic search induced by the algorithm is surprisingly robust since its ability to explore a large neighborhood does not disrupt the search.

----------------------------------------------------------------------------------------------

Magnus Find, Univ. of Southern Denmark, Odense

Title: Trade-off between Multiplicative and Gate Complexity

Abstract

We study the relationship between the number of AND and XOR gates in XOR-AND circuits. We give a new construction that shows that arbitrary Boolean functions can be computed using $(1+o(1))2^n/n$ XOR/AND gates.

We establish that if the multiplicative complexity of a function is $M$, the gate complexity not larger than?$6M^2/\log M$, and this bound is asymptotically tight. We use this to show that almost every function can be implemented by XOR-AND circuits with optimal multiplicative complexity and almost optimal gate complexity simultaneously. For symmetric functions every function can be implemented with a circuit that is at most a constant factor larger than the optimum with respect to both the multiplicative and gate complexity. The computational complexity of determining the multiplicative complexity of a Boolean function is unknown.

We prove that the restricted problem of determining if the function computed by a circuit is affine is complete for co-NP.

----------------------------------------------------------------------------------------------------

Hjalte Wedel Vildhøj, Technical University of Denmark, Kgs. Lyngby

Title: Time-Space Trade-Offs for Longest Common Extensions

Abstract

We revisit the longest common extension (LCE) problem, that is, preprocess a string T into a compact data structure that supports fast LCE queries. An LCE query takes a pair (i,j) of indices in T and returns the length of the longest common prefix of the suffixes of T starting at positions i and j.

We study the time-space trade-offs for the problem, that is, the space used for the data structure vs. the worst- case time for answering an LCE query.

Let n be the length of T. Given a parameter τ, 1 ≤ τ ≤ n, we show how to achieve either O(n/√τ) space and O(τ) query time, or O(n/τ) space and O(τlog(|LCE(i,j)|/τ)) query time, where |LCE(i, j)| denotes the length of the LCE returned by the query. These bounds provide the first smooth trade-offs for the LCE problem and almost match the previously known bounds at the

extremes when Ï„ = 1 or Ï„ = n. We apply the result to obtain improved bounds for several applications where the LCE problem is the computational bottleneck, including approximate string matching, computing tandem repeats, and computing palindromes. Finally, we also present an efficient technique to reduce LCE queries on two strings to one string

----------------------------------------------------------------------------

Rasmus Fonseca, Univ. of Copenhagen

Title: Determining Protein Structures with beta-Sheet Enumeration and Branch-and-Bound

Abstract

Proteins are long chains of amino acids that always fold to the same native structure. Predicting this native structure from the amino acid sequence alone is one of the grand challenges of computational biology which is still essentially unsolved. The problem can be stated as an optimization problem where the Gibbs free energy of the protein is minimized.

Simplified versions of the protein structure prediction problem have been shown to be NP-complete, so metaheuristics are widely applied. We have worked on designing representations of protein structures where optimal solutions are not only achievable but also practically useful. This is done by enumerating long-range contacts between amino acids and then using a branch-and-bound implementation.

Long range contacts are represented by $\beta$-pairings consisting of $\beta$-strand segments that form pairs in a ladder-like structure. Although the correct $\beta$-pairing can not be reliably predicted, a small set of predictions can be made that is guaranteed to contain the correct one. The branch-and-bound method first fixes the structure of $\beta$-sheets using one of the predicted pairings and then proceeds to place the remaining loop segments.

--------------------------------------------------------------------------------

Christian Wulff-Nilsen, Univ. of Southern Denmark, Odense

Titel: Multiple Single-Source Single-Sink Max Flows in Planar Digraphs

Abstract

Let $G = (V,E)$ be a planar $n$-vertex digraph. Consider the problem of computing max $st$-flow values in $G$ from a fixed source $s$ to all sinks $t\in V\setminus\{s\}$. We show how to solve this problem in near-linear $O(n\log^3n)$ time. Previously, nothing better was known than running a single-source single-sink max flow algorithm $n-1$ times, giving a total time bound of $O(n^2\log n)$ with the algorithm of Borradaile and Klein. An important implication is that all-pairs max $st$-flow values in $G$ can be computed in near-quadratic time. This is close to optimal as the output size is $\Theta(n^2)$.

We also give a quadratic lower bound on the number of distinct max flow values. This distinguishes the problem from the undirected case where the number of distinct max flow values is $O(n)$. Joint work with Jakub Lacki, Yahav Nussbaum, and Piotr Sankowski.

----------------------------------------------------------------------------

Rolf Fagerberg, Univ. of Southern Denmark, Odense

Title: De-amortizing Binary Search Trees

Abstract

We give a general method for de-amortizing essentially any Binary Search Tree (BST) algorithm. In particular, used on Splay Trees, the method produces a BST that has the same asymptotic cost as Splay Trees on any access sequence while performing each search in $O(\log n)$ worst case time.

Used on Multi-Splay Trees, it produces a BST that is $O(\log \log n)$ competitive, satisfies the scanning theorem, the static optimality theorem, the static finger theorem, the working set theorem, and performs each search in $O(\log n)$ worst case time. Finally, if a dynamically optimal BST algorithm exists, the method implies the existence of a dynamically optimal BST algorithm answering every search in $O(\log n)$ worst case time.

Joint work with Prosenjit Bose, S\'ebastien Collette, and Stefan Langerman