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.