Lectures and Colloquia during the semester

Konrad-Zuse-Zentrum für InformationstechnikBerlin

Takustraße 7, 14195 Berlin

Room 2005 (lecture hall), ground floor

*Abstract:*
The *minimum test set problem* is a problem that arises from
practical problems in which tests have to be executed in order to
investigate the effect of application of measures or drugs on a
number of diseases. In fact the motivation for this research came
from a request from the Agricultural University of Wageningen in The
Netherlands concerning studies of potato diseases. Each potato race
is vulnerable for a number of diseases. In order to investigate the
effect of special treatments on the diseases a selection of potato
races had to be made such that any pair of diseases could be
distinguished from one another.

Presented more formally, in the minimum test set problem a set of items and a set of tests are given. Each test is a subset of the items, and is said to differentiate the items in the test from the items not in the test. The objective is to find a smallest subset of tests such that every pair of items is differentiated.

Algorithms for minimum test set problems are studied. For the general problem we define branch and bound algorithms, which we tested empirically, and appeared to be working remarkably well. We also analyse a greedy approximation algorithm for this problem from a worst-case point of view.

Finally, we pay attention is paid to the special case in which each test contains exactly two items. This problem can be formulated as the optimization problem of packing paths of length two in a graph. The relation to this packing problem is exploited to show that this special minimum test set problem is NP-hard, contradicting a claim in [Garey & Johnson 1979], and in deriving performance guarantees for a series of local improvement heuristics. The latter are some of the first results on performance guarantees of local search heuristics in the literature.

The results presented are joint work with C.A.H. Hurkens, J.K. Lenstra, K. De Bontridder, Technische Universiteit Eindhoven, J.B. Orlin, Massachusetts Institute of Technology (MIT).

**Colloquium - 16:00**

*Abstract:*
In optical telecommunication networks, data is sent via glass fibers
as optical signals of a certain wavelength without converting them
into electronical form at intermediate nodes. A connection is
implemented by one or several *lightpaths*, where each lightpath
is a combination of a path and a wavelength.

In the problem of Online Call Admission in Optical Networks, we are
given a graph together with a set of wavelengths. *Connection
requests*, also referred to as *calls*, arrive in an online
fashion, i.e., an online algorithm learns the next call only after
having processed the previous one. A call specifies a pair *(s,t)* of
nodes to be connected and its *demand*, that is, the number *b*
of lightpaths needed. The task of an online algorithm is to decide
which calls to accept and which to reject. If a call is accepted, a
valid routing has to be provided, i.e., *b* paths connecting nodes *s*
and *t*, each together with a wavelength, have to be implemented. The
crucial restriction is that on every edge, each wavelength can be used
by at most one lightpath (*wavelength conflict constraint*).
Consequently, previously accepted calls restrict the availability of
wavelengths for the implementation of further lightpaths. When a call
with demand *b* is accepted, it contributes *b* to the overall profit.
The objective is to maximize the profit.

After giving a short introduction to the area of online optimization and
competitive analysis, we review an online algorithm for the special
case of the problem where all demands equal *1*, proposed by
Awerbuch, Azar, Fiat, Leonardi and Rosén. We then present a
competitive online algorithm for the general case in which calls may
request up to *chi* wavelengths, where *chi* is the number of
eligible wavelengths on any edge. This is the first competitive algorithm
for the general case.

[top]