LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Oberseminar Theoretische Informatik SS 02

Brauer, Esparza, Mayr, Steger

Mittwochs um 14:00 Uhr s.t., Raum S2229

der nächste Vortrag findet am Mittwoch 10. Juli 2002 statt

*Mi,8.5.2002
Alex Hall
NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow
We consider the version of broadcast scheduling where a server can transmit one message of a given set at each time-step, answering previously made requests for that message. The goal is to minimize the average response time if the amount of requests is known in advance for each time-step and message. We prove that this problem is NP-hard, thus answering an open question stated by Kalyanasundaram, Pruhs and Velauthapillai (Proceedings of ESA 2000, LNCS 1879, 2000, pp.\ 290--301). Furthermore, we present an approximation algorithm that is allowed to send several messages at once. Using 6 channels for transmissions, the algorithm achieves an average response time that is at least as good as the optimal solution using one channel. The best previous approximation algorithm achieved ratio 1.5 with 6 channels and reached ratio 1 only in the case where there are as many channels as messages.
From the NP-hardness of broadcast scheduling we derive a new inapproximability result of $(2 - \varepsilon, 1)$ for the (congestion,cost) bicriteria version of the single source unsplittable min-cost flow problem, for arbitrary $\varepsilon > 0$. The result holds even in the often considered case where the maximum demand is less than or equal to the minimum edge capacity ($d_{\max} \le u_{\min}$), a case for which an algorithm with ratio $(3, 1)$ was presented by Skutella.
Our results were published in SODA 2002.
*Mi,29.5.2002
Nicolas Fournier
Insights into local search for SAT
Lokale Suchalgorithmen und verwandte Heuristiken, wie zum Beispiel Evolutionäre Algorithmen, Tabu-Suche, Simmulated Annealing, u.Ä., haben Dank ihrer Robustheit und Effizienz in den letzten Jahren zunehmend an Beliebtheit gewonnen. Jedoch um zu wissen ob und wie gut ein solcher Algorithmus funktioniert, bleibt zur Zeit meist nichts anderes übrig als ihn zu implementieren und laufen zu lassen, denn das theoretische Verständnis dieser Algorithmen ist noch rudimentär.
Der Vortrag diese Woche geht einen Schritt in Richtung eines besseren Verständnisses lokaler Suchalgorithmen. Präsentiert wird zuerst eine Analyse der lokalen Struktur des Suchraums kombinatorischer Probleme, am Beispiel des SATISFIABILITY Problems. Auf dieser Struktur aufbauend kann ein Markov Prozess definiert werden, der es erlaubt lokale Suchalgorithmen zu modellieren. Der Vergleich mit experimentellen Ergebnissen zeigt, dass der Markov Prozess die erwartete Laufzeit einer Reihe an randomisierten lokalen Suchalgorithmen auf zufälligen SAT-Instanzen gut beschreibt. Dies unterstützt die These, dass die lokale Struktur allein ausreicht um die durchschnittliche Laufzeit der Algorithmen zu beschreiben, und dass keine weitere globale Strukturen in Betracht gezogen werden müssen.
*Do,20.6.2002
S. Arun-Kumar (IIT Delhi)
Reflecting BDDs in Coq
We describe an implementation and a proof of correctness of binary decision diagrams (BDDs), completely formalized in Coq. This allows us to run BDD-based algorithms inside Coq and paves the way for a smooth integration of symbolic model checking in the Coq proof assistant by using reflection. It also gives us, by Coq's extraction mechanism, certified BDD algorithms implemented in Caml. We have also implemented and proved correct, a garbage collector for our implementation of BDDs inside Coq. Our experiments show that this approach works in practice, and is able to solve both relatively hard propositional problems and actual industrial hardware verification tasks.
*Mi,3.7.2002
Klaus Holzapfel
The complexity of finding dense subgraphs
We study the complexity of finding a subgraph of certain size and certain density, where density is measured by the average degree. Let \gamma >= 0 be any fixed rational (which may depend on an argument). Then \gamma-Cluster is the problem of deciding, given an undirected graph G and natural number k, whether there is a subgraph of G on k vertices which has average degree at least $\gamma(k)$. For \gamma =k-1, this problem becomes the well-known clique problem, and is thus NP-complete. We ask for the possible values of \gamma such that \gamma-Cluster remains NP-complete or becomes solvable in polynomial time. We show \gamma-Cluster is N-complete if \gamma= 2+\Theta(1/k^{1-\epsilon}) for some 0< \epsilon <2 and has a polynomial-time algorithm for \gamma=2+O(1/k).
*Mi,10.7.2002
Michal Mnuk
On Complexity of Computation with Modules over Polynomial Rings
Based on algorithms for Gröbner bases and syzygies we present an EXPSPACE upper bound for computing a finite free resolution of a module over the ring of polynomials. Furthermore, we show that tensor product, Hom-functor, Tor and Ext modules can be computed within the same bound. This sheds more light on the complexity of a large number of algorithms in commutative algebra and algebraic geometry built on these notions.

Martin Raab