Institut für Theoretische Informatik, Algorithmik

URAW 2004 - List of Abstracts

  • Christian Ammann (University of Berne, Switzerland)
    Implementation of 3D Computer Games Using Subdivision Surfaces
    Subdivision has proved to be a very elegant and efficient approach to generate many kinds of smooth surfaces of arbitrary topology. It seems to be especially useful for the implementation of nontrivial 3D computer games as it is able to cope naturally with continuous level-of-detail.
    In this talk we present data structures and algorithms for subdivision that are suitable for 3D real-time computer games.
  • Henning Fernau (University of Tuebingen)
    A Top-Down Approach to Search-Trees
    We show how to systematically improve on search-tree based parameterized algorithms and their analysis, focussing on Hitting Set. We concentrate on algorithms that are easy to implement, in contrast to the highly sophisticated algorithms developed previously. Yet, our algorithm analysis shows better worst-case behavior of our algorithms.
  • Daniel Fleischer (University of Konstanz)
    Electrical Networks
    This talk will be mainly about electrical networks, i.e. a graph G together with an edge function c modelling its conductances. Two centrality indices based on flows in electrical networks will be proposed and an efficient algorithm for their computation will be presented.
  • Jiong Guo (Universität Tübingen)
    Fixed-Parameter tractability results for Multicut and Multicommodity Demand Flow in Trees
    We study two NP-hard (and MaxSNP-hard) problems on trees—Multicut and Multicommodity Demand Flow—each of them dealing with demand flows between pairs of nodes, either disabling or fulfilling these demands, respectively. Both problems have been intensively studied for trees as well as for general graphs mainly from the viewpoint of polynomial-time approximation algorithms. By way of contrast, we provide exact algorithms for both problems that work well whenever some natural problem parameters are small, a reasonable assumption in several applications. Thus, we prove fixed-parameter tractability with respect to the considered parameters.
  • Michael Hoffmann (ETH Zurich)
    Chordless Paths through Three Vertices
    Consider the following problem, called CP3V, for short: Given an undirected graph G=(V,E), a positive integer k, and three distinct vertices s, t, and v in V, is there a chordless path from s via v to t of length at most k in G? A chordless path is a path for which no two vertices are connected by an edge that is not in the path. Alternatively, one could say that the subgraph induced by the vertex set of the path in G is the path itself. I will discuss the parametric complexity of CP3V and prove it to be W(1)-complete for general graphs. The problem appears in the context of service deployment in communication networks, and it has some connection to the theory of perfect graphs.
    (joint work with Robert Haas from IBM Rueschlikon)
  • Rolf Klein (Universität Bonn)
    On the dilation of curves and point sets
    Given a geometric graph in the plane, we can define its dilation in the following way. Given two points in the network we consider the ratio of the length of a shortest connecting path in the network over the Euclidean distance of the points. The maximum of these values is called the dilation of the network. More precisely, we talk about the geometric dilation if all points (vertices and interior edge points alike) are considered, whereas the graph-theoretic dilation results from restricting the points to vertices of the net.
    Of particular interest is the case where the network is a curve or a polygonal chain. We review some structural upper bounds to the dilation, and present efficient algorithms for computing the dilation of a given chain, cycle, or tree. Next, we address the problem of embedding a given point set into networks of low dilation.
  • Katharina Nina Lehmann (WSI, Universität Tübingen)
    What a bookstore can tell us
    We have just begun to analyze the dynamic properties of a very interesting network: Every one of us knows Amazon, the big internet-bookseller. It makes recommendation to every item, based on the idea of „People who bought this item also bought“.
    Following these links yields structure-rich networks which we analyse in many ways. We will represent you some of our latest results and discuss the next steps to find out how and why these structures emerge.
  • Jürgen Lerner (University of Konstanz)
    Structural Similarity
    Standard methods in network role analysis partition the vertex set of a graph in such a way that vertices in the same class can be considered to assume equivalent roles. Several classes of equivalence relations such as regular equivalence and equitable partitions have been proposed for role assignment, but they all suffer from the strictness of classifying vertices into being either equivalent or not. To allow for varying degrees of similarity, we introduce the concept of structural similarity by relaxation of equitable partitions, and show that it enjoys more desirable properties with respect to existence, structure, and computability.
  • Matus Mihalak (ETH Zurich)
    OVSF-code assignment
    An OVSF-code assignment is a mean how to share a bandwith within a group of users allowing different data rate in a design of a new generation telecommunication systems, e.g., UMTS. The OVSF-codes are represented as nodes of a complete binary tree of height h. Codes on a level l provides a fraction 2^{-l} of the total bandwith. Users request codes on a certain level, expressing their bandwith demands and we want to assign them an arbitrary code from the tree of that level. The constrain is, however, that on every leaf-root path, there can be at most one code assigned to a user. As users request and release their codes, the tree can get fragmented so a new request can not be served without reassigning the current assigned codes. The natural goal is to minimize the number of code reassignments in order to serve a new request. In this talk we look on some aspects of this problem, namely we point out this problem to be NP-complete, which totally contradicts certain claims of previous work on this problem, then we analyse a simple greedy algorithm and look also on an online version of the problem.
  • Matthias Müller-Hannemann (TU Darmstadt)
    Moving Policies in Cyclic Assembly-Line Scheduling
    We consider an assembly line that processes a (potentially infinite) number of identical workpieces in a cyclic fashion. In contrast to common variants of assembly–line scheduling, the forward steps may be smaller than the distance of two stations. Therefore, each station may process parts of several workpieces at the same time, and parts of a workpiece may be processed by several stations at the same time. The throughput rate is determined by the number of (cyclic) forward steps, the offsets of the individual forward steps, and the distribution of jobs over the stationary stages between the forward steps. Even for a given number of forward steps and for given offsets of the forward steps, the optimal assignment of the jobs to the stationary stages is at least weakly NP-hard.
    We will base our algorithmic considerations on some quite conservative assumptions, which are greatly fulfilled in various application scenarios: the number of jobs may be huge, but the number of stations and the number of forward steps in an optimal solution are small, the granularity of forward steps is quite coarse, and the processing times of the individual items do not differ by several orders of magnitude from each other. We will present an algorithm that is polynomial and provably deviates from optimality to a negligible extent (under these assumptions). This result may be viewed as an application of fixed-parameter tractability to a variety of real-world settings.
    This is joint work with Karsten Weihe.
  • Yoshio Okamoto (Institute of Theoretical Computer Science, ETH Zurich)
    The traveling salesman problem with few inner points
    We study the traveling salesman problem in the 2-dimensional Euclidean plane. The problem is NP-hard in general, but trivial if the points are in convex position. In this paper, we investigate the influence of the number of inner points (i.e., points in the interior of the convex hull) on the computational complexity of the problem. We give a simple algorithm for this problem which runs in time O(k!kn) and space O(n), when n is the total number of input points and k is the number of inner points. If k is taken as a parameter, this algorithm is fixed-parameter-tractable (FPT), and also implies that the problem can be solved in polynomial time if k=O(log n/log log n). We also consider some variants of the traveling salesman problem in this setting, and give FPT algorithms for them. This is a joint work with Michael Hoffmann (ETH Zurich).
  • Jan Remy (ETH Zürich)
    Online Construction of Minimum Spanning Trees in Random Weighted Graph
    In this talk an online variant of the minimum spanning tree problem in random weighted graphs will be presented. We assume that the input graph is complete and the edge weights have uniform distribution over [0,1]. An algorithm receives the edges one by one in random order and has to decide immediately whether to include the current edge into the spanning tree or to reject it. As a performance measure we consider the expected competitive ratio E[r], where r=ALG/OPT. As our main result, we propose an online algorithm and show that its expected competitive ratio is O(1).
  • Philippe Robert (University of Bern)
    Using the GPU for Geometric Computations
    Recent advances in programmable graphics hardware make it possible to use GPUs as highly parallel streaming processors for a wide range of applications. Considering ray-triangle intersection testing as example, we describe possible pitfalls and advantages of porting and performing algorithms on programmable graphics hardware using Nvidia Cg.
  • Markus Schmidt (Institut für Informatik, Albert-Ludwigs-Universität Freiburg)
    Performance of Greedy Algorithms in Packet Buffering
    We study a basic buffer management problem that arises in network switches. Consider m input ports, each of which is equipped with a buffer (queue) of limited capacity. Data packets arrive online and can be stored in the buffers if space permits; otherwise packet loss occurs. In each time step the switch can transmit one packet from one of the buffers to the output port. The goal is to maximize the number of transmitted packets. Simple arguments show that any reasonable algorithm, which serves any non-empty buffer, is 2-competitive. Azar and Richter recently presented a randomized online algorithm and gave lower bounds for deterministic and randomized strategies. In practice greedy algorithms are very important because they are fast, use little extra memory and reduce packet loss by always serving a longest queue. In this paper we first settle the competitive performance of the entire family of greedy strategies. We prove that greedy algorithms are not better than 2-competitive no matter how ties are broken. Our lower bound proof uses a new recursive construction for building adversarial buffer configurations that may be of independent interest. We also give improved lower bounds for deterministic and randomized online algorithms.
    In the second part of the paper we present the first deterministic online algorithm that is better than 2-competitive. We develop a modified greedy algorithm, called „Semi-Greedy“, and prove that it achieves a competitive ratio of 17/9=1.89. The new algorithm is simple, fast and uses little extra memory. Only when the risk of packet loss is low, it does not serve the longest queue. Additionally we study scenarios when an online algorithm is granted additional resources. We consider resource augmentation with respect to memory and speed, i.e. an online algorithm may be given larger buffers or higher transmission rates. We analyze greedy and other online strategies.
  • Dominique Schmitt (University of Haute-Alsace)
    k-set polytopes and order-k Delaunay diagrams
    Given a set S of n points (called sites) in a d-dimensional Euclidean space and an integer k, 1 ⇐ k ⇐ n-1, the k-set polytope of S is the convex hull of the centroids of the subsets of k elements in S. The order-k Delaunay diagram of S is the dual of the order-k Voronoi diagram of S whose vertices are centroids of subsets of k elements in S. Studying these two objects leads to consider the separability of a subset of k sites by a separating surface: A hyperplane for the k-set polytope and a sphere for the order-k Delaunay diagram. We introduce a generalization of this notion by considering couples of site sets (P,Q) with Q on the separating surface and with P and S  (P u Q) on both sides of the surface. Moreover, we deal with degenerate cases, i.e. the separating surface may contain any number of sites.
    The notion of k-set polytope extended to such couples allows to completely characterize all the faces of the k-set polytope of S and those of the order-k Delaunay diagram of S.
    Furthermore, the connexion between order-k Delaunay diagrams and (d+1)-dimensional k-set polytopes as well as the orthogonal duality between order-k Delaunay and Voronoi diagrams become easy to prove.
  • Étienne Schramm (Universität Karlsruhe)
    The European Pie
    We study the area-labeling problem where areas (e.g. countries) have to be labelled with polygonally-shaped labels. For example, given a map of Europe, we want to show statistics about the member countries of the European Union with a square for each country.
    We can model this problem in several ways. For example, one way is to minimize the area overlap between a label and the countries it does not label. For each model, we investigate the complexity of an exact solution, an x-discretisation and an x-y-discretisation.
    It is known to be NP-hard to minimize label overlap, but when the labels are not too big with respect to the size of the countries, simple and efficient models can often avoid label overlap, even if they don't guarantee an overlap-free solution.
  • Ingo Schurr (ETH Zürich)
    Memoryless Algorithms on Unique Sink Orientations of Cubes
    Unique sink orientations of cubes (USO's) are a common framework for several problems (like LP, LCP, smallest enclosing balls). In the last years several attempts were made to estimate the complexity of finding the sink in a USO. In this talk we will introduce the basic concepts and construct worst case examples for some algorithms.
  • Jean-Claude Spehner (University of Haute-Alsace)
    Araucarias
    The study of the shuffle product of words leds to the construction of an automaton whose structure is deeply connected to a family of trees
    which we call araucarias. We give here a direct definition of these araucarias, characterize their maximal paths and finally give a construction based on the properties of the terminal sections of the maximal paths. Then we define a family of remarkable symmetric polynomials which play a crucial role in the computation of the size of the araucarias.
  • Johannes Uhlmann (Universität Tübingen)
    Tree decompositions of graphs: saving memory in dynamic programming
    We propose an effective heuristic to save memory in dynamic programming on tree decompositions when solving graph optimization problems. The introduced „anchor technique“ is closely related to a tree-like set covering problem.
  • Birgitta Weber (ETH Zürich)
    Parallel Prefetching and Caching is Hard
    We study integrated prefetching and caching in parallel disk systems. This topic has gained a lot of interest in the last years which manifests itself in numerous recent approximation algorithms. This paper provides the first negative result in this area by showing that optimizing the stall time is APX-hard. This also implies that computing the optimal processing time is NP-hard, which settles an open problem posed by Kimbrel and Karlin.
  • Guochuan Zhang (University of Freiburg)
    Maximizing the Number of Packed Rectangles
    Given a set of rectangles we are asked to pack as many of them as possible into a bigger rectangle. The rectangles packed may not overlap and may not be rotated. This problem is NP-hard in the strong sense even for packing squares into a square. We establish the relationship between the asymptotic worst-case ratio and the (absolute) worst-case ratio for the problem. It is proved that there exists an asymptotic FPTAS, and thus a PTAS, for packing squares into a rectangle. We give an approximation algorithm with asymptotic ratio of at most two for packing rectangles, and further show a simple (2+eps)-approximation algorithm.