Humboldt-Universität zu Berlin, Friday, July 11th 2003
Schedule:
All lectures had been held inErwin Schrödinger-Zentrum, HU Berlin Rudower Chaussee 26, 12489 Berlinin room 0.110.
(for information of arrival look at Address of ESZ or the city map.)
Friday, July 11th 2003 |
||
| 13:30 |  Den Anfang machte Prof. Prömel. |
|
| 14:00 | Uriel Feige (Weizmann Institut (Israel)) |  Algorithms for Semirandom Instances of NP-hard Problems |
| 15:00 |  Prof. Uriel Feige |
|
| 15:30 | Stefan Hougardy (HU) |  Stefan Hougardy |
| 16:00 | Tobias Lenz (TU) |  Tobias Lenz |
| 16:30 |  In den Kaffeepausen … … wurde eifrig diskutiert. |
|
| 17:00 | Diana Poensgen (ZIB) |  Teamarbeit war gefragt beim Einrichten der Technik. Diana Poensgen |
| 17:30 | Florian Pfender (FU) |  Florian Pfender Die Zuhörer zeigten sich zufrieden. |
| 18:30 |  Auf der Terasse konnten auch … … die letzten Klarheiten beseitigt werden. |
|
Abstracts
Uriel Feige
Algorithms for Semirandom Instances of NP-hard Problems
Some NP-hard problems can be solved efficiently on average on some
natural input distributions. For example, there are efficient algorithms
that easily find Hamiltonian cycles in random graphs. We consider
semirandom models of input instances, that blend together a random
component and a limited adversarial component. For example, we consider
graphs that are generated in two steps, the first being random, and in
the second step an adversary may add arbitrary edges (but not remove any
edge). We then develop algorithms that are robust enough to handle also
the semirandom models. In some cases, this results in algorithms that
are not only provably good in this theoretical model, but also have good
performance in practice.
We shall illustrate how the above approach is applied to problems such
as Hamiltonicity, satisfiability, and graph partitioning problems.
Stefan Hougardy
Linear Time Matching Algorithms
The weighted matching problem is to find a matching in a weighted graph
that has maximum weight. The fastest known algorithm for this problem has
running time O(nm+n2logn). Many real world problems require
graphs of such large size that this running time is too costly. We
present a linear time approximation algorithm for the weighted matching
problem with a performance ratio of 2/3-ε. This improves the
previously best performance ratio of 1/2.
This is joint work with Dorotha Drake.
Tobias Lenz
Efficient Contour Tree Construction and Computation of Betti Numbers in Scalar Fields
Contour trees are used when high-dimensional data are preprocessed for efficient extraction of iso-contours, mainly for the purpose of visualization. So far, efficient algorithms for contour trees are based on processing the data in sorted order. We present a new algorithm that avoids sorting of the whole data set. It also generates additional topological information about the data which can be used to compute the Betti numbers for all possible level sets in two and three dimensions.
Diana Poensgen
Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem
In the Online Dial-a-Ride Problem Oldarp, a server of unit speed
and given capacity C must transport objects between points of a
metric space. Each transportation request is defined by its release
time, its source, and its destination. An online algorithm learns
about the existence of a request at its release time, and it must
serve each request by transporting an object from the given source to
the destination, never carrying more than C objects at once. We
investigate the Oldarp with the maximum flow time as objective
function. The flow time of a request is the difference between the
time when the object reaches its destination and its release time.
It is easy to see that competitive analysis fails to distinguish
online algorithms for this problem, unless the adversary is
restricted. We extend the fair adversary defined for the real line by
Blom et al. to the uniform metric space and show that a simple
first-come-first-serve strategy is 2-competitive and best possible,
if source and destination of each request coincide. For the case that
they differ, we provide a worst-case construction that shows that no
deterministic online algorithm can be competitive for the Oldarp with
the maximum flow time as objective function,
not even against the fair adversary.
This is joint work with Sven O. Krumke, Luigi Laura, Maarten Lipmann,
Alberto Marchetti-Spaccamela, Willem de Paepe, and Leen Stougie.
Florian Pfender
On Graph Irregularity Strength
An assignment of positive integer weights to the edges of a
simple graph G is called irregular if the weighted degrees of
the vertices are all different. The irregularity strength, s(G), is
the maximal weight, minimized over all irregular assignments, and
is set to ∞ if no such assignment is possible.
In this talk, we are using a combination of
deterministic and probabilistic techniques to achieve new upper bounds
for s(G) depending on the minimum and maximum degree of G.
This is joint work with A. Frieze, R. Gould and M. Karonski.
Contact:
Amin Coja-OghlanPostadresse: Johann von Neumann-Haus Humboldt-Universität zu Berlin Institut für Informatik Rudower Chaussee 25 12489 Berlin
Tel. : (+49 30) 2093 3803 Fax : (+49 30) 2093 3191 e-mail : coja@informatik.hu-berlin.de
Deutsch