CAOS Seminar Series, Spring 2005

This page contains information on the CAOS Seminar Series (Copenhagen Algorithms and Optimization Seminars), a joint venture between IT University of Copenhagen (ITU) and Department of Computer Science, University of Copenhagen (DIKU). Seminars take place on Thursdays, 13.30-15.00, at either DIKU or ITU, and are open to all. Students can get credit for following the seminars and solving problems related to the talks. Contact Martin Zachariasen (DIKU) or Rasmus Pagh (ITU) if you are interested in getting credit. Info on credit, etc., for DIKU students

Schedule

• Benny K. Nielsen: Reconstructing phylogenetic trees using sequence graphs
  Two of the main problems in computational biology today are 1) multiple sequence alignment and 2) reconstruction of phylogenetic trees (the evolutionary history of a set of species). Traditionally these problems are handled separately, however, a phylogenetic tree is most often based on an alignment and such an alignment should be based on the tree. Solving the problems simultaneously is known as the generalized alignment problem. We have re-implemented and extended an algorithm by Schwikowski which uses sequence graphs for solving this problem. Preliminary results are presented.
• Rasmus Pagh: On Dynamic Range Reporting in One Dimension
  We consider the problem of maintaining a dynamic set of integers and answering queries of the form: report a point (equivalently, all points) in a given interval. Range searching is a natural and fundamental variant of integer search, and can be solved using predecessor search. However, for a RAM with $w$-bit words, we show how to perform updates in $O(\lg w)$ time and answer queries in $O(\lg\lg w)$ time. The update time is identical to the van Emde Boas structure, but the query time is exponentially faster.
  Our solution is based on a new and interesting recursion idea which is ``more extreme'' that the van Emde Boas recursion. Whereas van Emde Boas uses a simple recursion (repeated halving) on each path in a trie, we use a nontrivial, van Emde Boas-like recursion on every such path. To achieve linear space for our data structure, we solve a problem which is of independent interest. We develop the first scheme for dynamic perfect hashing requiring sublinear space.
• Stephen Alstrup: Algorithm based startups with focus on Octoshape
  Recently many algorithm experts have succeeded with startups, solving problems like "world wide searching" and "world wide waiting". In the presentation there will be given several examples on such startups. We also raise the question: Why algorithms today are more important than ever?
  Next we move to Octoshape: In 2003 Octoshape was started by two algorithm researchers from ITU with the goal to solve "world wide streaming": The object was to make software enabling to live stream to millions of simultaneous users from a single standard machine with a single standard DSL-connection.
  Today Octoshape is ready to launch its first product solving the "world wide streaming problem". The remaining presentation will be split in two parts:
  1) Technique: How to stream with and without Octoshape.
  2) Startup: What to think about beside technique when making a new startup
• Martin Zachariasen: Construction of minimum-weight spanners
  Spanners are sparse subgraphs that preserve distances up to a given factor in the underlying graph. Recently spanners have found important practical applications in metric space searching and message distribution in networks. These applications use some variant of the so-called greedy algorithm for constructing the spanner --- an algorithm that mimics Kruskal's minimum spanning tree algorithm. Greedy spanners have nice theoretical properties, but their practical performance with respect to total weight is unknown. In this paper we give an exact algorithm for constructing minimum-weight spanners in arbitrary graphs. By using the solutions (and lower bounds) from this algorithm, we experimentally evaluate the performance of the greedy algorithm for a set of realistic problem instances.
• Sathiamoorthy Subbarayan: Integrating CSP Decomposition Techniques and BDDs for Compiling Configuration Problems
  Configuration problems can be modelled as Constraint Satisfaction Problems (CSP). The Binary Decision Diagram (BDD) based symbolic CSP compilation technique can be used to compile all solutions of a configuration problem into a BDD. Once a BDD is obtained, the functions required for interactive configuration can be efficiently implemented. The problem with such approaches is that they do not exploit the fact that configuration problems are specified in hierarchies. Due to this the BDD obtained after compilation could be unnecessarily large. Such hierarchies are close to trees in shape. Hence, the tree decomposition techniques for CSPs, could be used to enhance the compilation schemes for configuration problems. We present the tree-of-BDDs approach: a combination of the BDD-based compilation technique and a CSP decomposition technique for efficient compilation of configuration problems. Experiments show that the approach can drastically reduces the time and space requirements for interactive configurators.
• Stefan Roepke: The pickup and delivery problem: models and optimization algorithms
  This talk introduces the NP-Hard "Dial A Ride Problem" (DARP) which is a variant of the Pickup and Delivery Problem. The DARP is often used to model the transportation of handicapped and elderly using minibuses. Several mathematical models for the problem are presented and it is investigated which model that is easiest to solve to optimality in practice. Valid inequalities are introduced and it is shown how these can be added to the models dynamically using a branch and cut algorithm. Computational results are presented.
• 
  
• Inge Li Goertz: Asymmetry in k-Center Variants
  Imagine you have a delivery service. You want to place your k delivery hubs at locations that minimize the maximum distance between customers and their nearest hubs. This is the k-center problem---a type of clustering problem that is similar to the facility location and k-median problems. The motivation for the asymmetric k-center problem, in our example, is that traffic patterns or one-way streets might cause the travel time from one point to another to differ depending on the direction of travel. Variants of k-center may more accurately model real-life problems than the original formulation. We give an O(log* n)-approximation algorithm for the asymmetric weighted k-center problem. Here, the vertices have weights and we are given a total budget for opening centers. In the p-neighbor variant each vertex must have p (unweighted) centers nearby: we give an O(log* k)-bicriteria algorithm using 2k centers, for small p. Finally, we show the following three versions of the asymmetric k-center problem to be inapproximable: priority k-center, k-supplier, and outliers with forbidden centers.
• Jens Egeblad: Container Loading of Italian Furniture
  We consider a real-life problem which is to be solved for the Italien furniture industry. The talk represents work-in-progress. To explain the background of the problem we will describe the current methods utilized by the company as well as requirements to the new solution method. To show the complexity of the problem some of its sub-problems will be described in detail. Because this is work in progress no final solution method will be presented. Rather we will give an overview of existing solution methods that we have tried to adapt to the problem and briefly touch upon our current method.
• Philip Bille: The Tree Inclusion Problem: In Optimal Space and Faster
  Given two rooted, ordered, and labeled trees P and T the tree inclusion problem is to determine if P can be obtained from T by deleting nodes in T. This problem has recently been recognized as an important query primitive in XML databases. Kilpelainen and Mannila (SIAM J. of Comp. 1995) presented the first polynomial time algorithm using quadratic time and space. Since then several improved results have been obtained for special cases when P and T have a small number of leaves or small depth. However, in the worst case these algorithms still use quadratic time and space. In this paper we present a new approach to the problem which leads to a new algorithm which use optimal linear space and has subquadratic running time. Our algorithm improves all previous time and space bounds. Most importantly, the space is improved by a linear factor. This will make it possible to query larger XML databases and speed up the query time since more of the computation can be kept in main memory.
• Rolf Fagerberg: On the Adaptiveness of Quicksort
  Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic sorting algorithms available, as testified by the choice of Quicksort as the default sorting algorithm in most programming libraries. Some sorting algorithms are adaptive, i.e. they have a complexity analysis which is better for inputs which are nearly sorted, according to some specified measure of presortedness. Quicksort is not among these, as it uses Omega(n log n) comparisons even when the input is already sorted. However, in this paper we demonstrate empirically that the actual running time of Quicksort *is* adaptive with respect to the presortedness measure Inv. Differences close to a factor of two are observed between instances with low and high Inv value. We then show that for the randomized version of Quicksort, the number of element *moves* performed is provably adaptive with respect to the measure Inv. More precisely, we prove that randomized Quicksort performs expected O(n(1+log(1+Inv/n))) element swaps, where Inv denotes the number of inversions in the input sequence. This result gives a theoretical explanation for the observed behavior, and provides further insight on the behavior of the classic Quicksort algorithm. We also give some empirical results on the adaptive behavior of Heapsort and Mergesort.
• Jakob Krarup: A family of structured set covering problems
  For a 0-1 matrix C = {c_ij_}, column j is said to _cover_ row i if c_ij_=1. A _cover_ is a subset of columns covering all rows. _Unweighted SET COVER (USC)_ is the problem of finding a cover containing as few columns as pos- sible.
  An open optimisation problem was published in a Danish journal in 2003. Not much reflection is needed to realize that the solution of a highly structured instance C of USC will answer the question posed. The instance C or rather, the _family_ of instances C(k), is a series of square matrices of size 3^k, k=1,2, ... . Provided that C(1) is known, the fractal-like structure of the matrices allows for C(k) to be constructed recursively for any value of k.
  Let r(k) be the number of columns in an optimal solution to C(k). Some preliminary investigations have enabled us to determine r(k), k=1,2,3,4 and to show that r(5) must be either 12 or 13.
  12 or 13? Unfortunately LP-based bounds take us nowhere in this case since the optimum is flat as a pancake. It offers some consolation though that experiments with _CPLEX_ were not too encouraging either. For k=5, C(5) is a matrix of size 243x243. Nothing was returned after 24 hours CPU time. Eventually, upon an investment of 72 hours CPU time, CPLEX managed to come up with r(5)=12.
  The original problem asks for r(12), that is, an optimal solution to a square matrix of size 531,441. After a week the originator of the problem, using an invalid argument, announced his own answer, r(12) = 512, and cashed the award. We have so far shown that r(12) is bounded to belong to the interval [210, 377]. We also need to conclude that no brute force approach (such as further experiments with CPLEX) is likely to work whereas paper and pencil _may_ suffice in providing the final result.

  Reference: J. Krarup, J. Villadsen, "A family of structured set covering problems", in preparation.