33. Berliner Algorithmen-Tag

Friday, July 15, 2005

Program

14:15-15:30	Rolf Klein (University of Bonn) On the dilation of planar sets
	--- break ---
16:00-16:30	Tobias Achterberg (Konrad Zuse Center for Scientific Computing) Constraint Integer Programming
16:30-17:00	Daniel Marx (Humboldt University of Berlin) The Closest Substring problem with small distances
	--- break ---
17:15-17:45	Nicole Megow (Technical University of Berlin) A combined model for online scheduling with stochastic information
17:45-18:15	Tobias Lenz (Free University of Berlin) A New Approach to Curve Reconstruction
	______________________________________
18:30-open end:	BAT'05-Party  Location: Inner courtyard of the Computer Science Building next to the lecture hall

Photo-Gallery

The photos of the event can be found here.

Location

Free University of Berlin (FU)  Institut für Informatik
Takustr. 9, 14195 Berlin	lecture hall 003

Abstracts

Rolf Klein, University of Bonn

On the dilation of planar sets

Traffic networks can be modeled by plane graphs. If p and q are two points on a plane graph, N, we can divide the length of a shortest path in N that connects p with q by the Euclidean distance |pq|. The maximum of all these ratios is called the dilation of N.

There are two different settings. In a city, houses are everywhere along the streets. Here, p and q are allowed to be arbitrary points of N, giving rise to the "geometric" dilation of N. In a railway system, access is only possible at stations. Consequently, p and q must be vertices of N, in this case. The corresponding dilation measure is called stretch factor, spanning ratio, or "graph-theoretic" dilation.

In this talk we will mention some results on efficiently computing the dilation and then consider the embedding proble: Given a set of points, what is the lowest possible dilation of any plane graph containing the set? This question leads to many open problems that will be mentioned at the end.

 

Tobias Achterberg, Konrad Zuse Center for Scientific Computing

Constraint Integer Programming

For solving Integer Programs and Constraint Programs, a very similar technique is used: the problem is successively divided into smaller subproblems (branching) that are solved recursively.

On the other hand, Integer Programming and Constraint Programming have different strengths: Integer Programming uses LP relaxations and cutting planes to provide strong dual bounds, while Constraint Programming can handle arbitrary (non-linear) constraints and uses propagation to tighten the variable's domains.

In this talk, we discuss the different strengths, and how both techniques can be integrated to benefit from both, strong dual bounds and extensive modelling possibilities.

The software package SCIP is introduced, which is a framework for Constraint Integer Programming oriented towards the needs of Mathematical Programming experts who want to have total control of the solution process and access detailed information down to the guts of the solver. For solving pure MIPs, SCIP is approximately 25% slower than the state-of-the-art commercial solver CPLEX 9.03.

 

Daniel Marx, Humboldt University of Berlin

The Closest Substring problem with small distances

The Closest Substring problem is a pattern matching problem where we have to find a string that approximately appears in each string in a given set of strings. The problem is NP-hard (not very surprisingly), hence most probably it can be solved only in exponential time. By analyzing the problem from the parameterized complexity point of view, we can investigate whether it is possible to restrict the exponential growth of the running time to some parameters of the input. This is motivated by the observation that in applications, some of the parameters are typically small, thus an algorithm can be efficient even if it is exponential in the small parameters, provided that it is polynomial in the others. It turns out that if we allow only a small number of errors in the approximate string matches, then the problem has surprising connections with the extremal combinatorics of hypergraphs. These connections can be leveraged to design new algorithms for the problem.

 

Nicole Megow, Technical University of Berlin

A combined model for online scheduling with stochastic information

We introduce a model for scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling as a special case. The particular setting we analyze is nonpreemptive parallel machine scheduling, with the objective to minimize the total weighted completion times of jobs. We propose simple, combinatorial online scheduling policies for that model, and derive performance guarantees that match the currently best known performance guarantees for stochastic and online parallel machine scheduling. For processing times that follow NBUE distributions, we improve upon previously best known performance bounds from stochastic scheduling, even though we consider a more general setting.

 

Tobias Lenz, Free University of Berlin

A New Approach to Curve Reconstruction

Given an arbitrary curve C and a finite sample S of it. Curve reconstruction deals with the problem of connecting the points in S in an order consistent with the adjacency in C. Obviously this problem is not solvable for any set S. Several sampling conditions are known under which algorithms can guarantee a correct reconstruction if the curve has a special type, e.g. the well-known epsilon-sampling condition for smooth curves.

In this talk a very simple general framework is introduced which works well as a heuristic but which also provides provable correct results for epsilon-samples.