🚀 go-pugleaf

----------------------------------------------------------------------------
------------Graduiertenkolleg "ALGORITHMISCHE DISKRETE MATHEMATIK" ---------
----------------------------------------------------------------------------


Das Graduiertenkolleg laedt ein zu folgenden Veranstaltungen:

KOLLEGSVORLESUNG
Montag, den 4. Mai 1998                       TU Berlin
                                              MA 363
                                              14 Uhr c.t.

                      Jeremy Spinrad
               Vanderbilt University, Nashville
         Solving Problems on Restricted Classes of Graphs

There are many algorithms which are designed to solve problems on special
classes of graphs. This talk takes the position that the standard notion
of solving a problem on a restricted class is not appropriate, and proposes 
new standards for showing a problem is easy/hard on a class.

Clearly, an algorithm which solves a problem on a class must produce the 
correct solution if the input is in the class. Using the standard definition, 
we do not care what the algorithm produces if the input is not in the class. 
I propose stricter criteria for solving a problem for a class; if the input 
is not in the class, the algorithm should still produce ``correct'' results, 
which may be either the correct solution to the problem or the answer "the 
input is not in the class". We will see examples of problems which are 
solvable in polynomial time if we do not care what happens when the input is 
outside the class, but are not solvable in polynomial time in the new sense 
unless P = NP. We will also discuss issues that arise if the graph class has 
a nice "model", and the distinctions between solving a problem given the 
model and solving the problem given an adjacency list matrix.

The talk will also discuss a new graph class which was partially responsible
for raising these issues, and leads to interesting open problems. A graph
is k-extendible if there is an ordering such that for every set S of k+1 
vertices which differs from a clique by lacking a single edge (x,y), x and y 
are not the first and last vertices of S in the ordering. The 2-extendible
graphs are exactly equal to the comparability graphs. For any fixed k, the
clique problem on k-extendible graphs is solvable in polynomial time if the 
ordering is given; the first algorithm for solving the clique problem on 
visibility graphs given a model used the fact that the order of vertices on 
the outside of the polygon is 3-extendible, if we start with the leftmost 
vertex. Open problems, including recognition, solving the clique problem 
without the order given, and other problems on the class, will be presented 
in the talk.  


KAFFEE/TEE im Anschluss an die Vorlesung im Raum MA 606.


KOLLOQUIUM des Graduiertenkollegs
Montag, den 4. Mai 1998                      TU Berlin
                                             MA 363
                                             16 Uhr s.t.

                       Martin Skutella
               Technische Universitaet Berlin
           MaxCut Algorithms for Parallel Machine Scheduling

We consider the problem of scheduling a set of jobs on unrelated parallel 
machines or processors so as to minimize the weighted sum of the comple-
tion times of jobs. Whereas the best previously known approximation algo-
rithms for this problem are based on LP relaxations, we give a 3/2-appro-
ximation algorithm that relies on a convex quadratic programming relaxation. 
For two unrelated parallel machines, this result can be further improved 
by using a more sophisticated semidefinite programming relaxation. For the 
special case of identical parallel machines we establish approximation 
preserving reductions to MaxCut problems. In particular, we discuss the 
connections to the MaxCut results of Goemans and Williamson that are also 
based on semidefinite relaxations. This is the first time that convex and
semidefinite programming techniques are used in the area of scheduling.

---------------------------------------------------------------------------
Veranstaltungsort: Technische Universitaet Berlin, Fachbereich Mathematik
                       Strasse des 17. Juni 136, 10623 Berlin.
                             Raum MA 363
---------------------------------------------------------------------------

Hinweise auf weitere Veranstaltungen:

Montag, den 11. Mai 1998, FU Berlin

KOLLEGSVORLESUNG 
Martin Aigner, Freie Universitaet Berlin
Pascal Determinanten

KOLLOQUIUM 
Christian Knauer, Freie Universitaet Berlin
The computation of the Hausdorff distance between sets of line segments

---------------------------------------------------------------------------
Informationen      Bettina Felsner  e-mail: bfelsner@inf.fu-berlin.de
                                    Tel.: (030) 838 75 104
Graduiertenkolleg  http://www.inf.fu-berlin.de/inst/theo/gk.html
---------------------------------------------------------------------------