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 WS 1999/2000

Brauer, Esparza, Mayr, Steger

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

[Zusammenfassung des nächsten Vortrags (Mittwoch, 16. Februar 2000)]

*Mi,10.11.1999
Angelika Steger
Balanced Allocations: The Heavily Loaded Case
Balls and bins algorithms using multiple choices for each ball have caused furor in recent years. In contrast to the classical balls and bins game in which each ball is placed into a randomly selected bin, these algorithms consider several random locations for each ball and place the ball into the bin with minimal load.
Almost all previous analyses focus on the lightly loaded case, i.e., m = O(n). In this case, the multiple-choice algorithms improve greatly upon the classical one-choice algorithm. The known results for the heavily loaded case, i.e., m >> n, however, were not impressive at all. Indeed, here the best known result is that the fullest bin contains m/n + O(\sqrt{m ln n / n}) balls, which just corresponds to the maximum load produced by the classical one-choice algorithm.
In this talk, we show that the actual distribution produced by the multiple-choice algorithms is much better than this prediction. We explicitely calculate the distributions produced by different multiple-choice algorithms. For example we show that for the sequential two-choice algorithm the deviation of the fullest bin from the average is at most (ln ln n)/ln 2 + \Theta(1), independently of the number of balls.
This is joint work with Petra Berenbrink, Artur Czumaj and Berthold Vöcking.
*Mi,24.11.1999
Keijo Heljanko
Deadlock and Reachability Checking Using Net Unfoldings and Logic Programming
McMillan has presented a deadlock detection method for Petri nets based on finite complete prefixes (i.e. net unfoldings).The approach transforms the PSPACE-complete deadlock detection problem for a 1-safe Petri net into a potentially exponentially larger NP-complete problem of deadlock detection for a finite complete prefix. McMillan devised a branch-and-bound algorithm for deadlock detection in prefixes. Recently, Melzer and Römer have presented another approach,which is based on solving mixed integer programming problems. We instead use a constraint-based logic programming framework, and translate the deadlock detection problem for prefixes into the problem of finding a stable model of a logic program. As a side result a similar translation for the reachability problems is devised.
*Fr,10.12.1999
Martin Grohe (Universität Freiburg)
Approximationsalgorithmen und lokale Baumweite
Wir zeigen, daß eine Reihe von im allgemeinen schwer approximierbaren kombinatorischen Optimierungsproblemen wie Minimum Vertex Cover oder Maximum Independent Set sich in Polynomialzeit beliebig gut approximieren lassen (d.h. ein PTAS besitzen), wenn man sie auf Klassen von Graphen mit verbotenen Minoren einschränkt.
Dabei verstehen wir unter einer Klasse von Graphen mit verbotenem Minor einfach eine Klasse C von Graphen, für die es einen Graphen gibt, der Minor keines Graphen in C ist. Beispiele solcher Klassen sind die Klasse der planaren Graphen, oder allgemeiner, Klassen von Graphen, die sich eine feste Fläche einbetten lassen, und Klassen von Graphen beschränkter Baumweite.
Graphentheoretische Grundlage der Approximationsalgorithmen ist eine neue Invariante von Graphen, ihre lokale Baumweite.
*Mi,15.12.1999
Stefan Schwoon
Effiziente Algorithmen fuer das Model-Checking von Pushdown-Systemen
Verschiedene Analyse-Probleme für Pushdown-Systeme lassen sich auf Erreichbarkeits-Probleme zurückführen, d.h. auf die Berechnung von Vorgängern und Nachfolgern von (möglischerweise unendlichen) Mengen von Konfigurationen. Ausgehend von einem automatentheoretischen Ansatz zeigen wir, wie sich das Modelchecking-Problem fuer LTL loesen läßt, und stellen effiziente Algorithmen zur Lösung der dazu notwendigen Teilprobleme vor. Außerdem wird gezeigt, wie sich diese Technik auf die Verifikation von Programmen mit Prozeduren anwenden läßt.
*Mi,12.1.2000
Peter Rossmanith
Effiziente Algorithmen für gewichtetes Vertex-Cover
Vertex-Cover ist ein beliebtes Problem und es gibt viele Algorithmen, für seine Lösung. Ich möchte exakte Algorithmen für die gewichtete Variante betrachten. Dabei kann man drei Möglichkeiten unterscheiden: Die Gewichte können ganze Zahlen sein, reelle Zahlen die größer oder gleich 1 sind oder beliebige reelle Zahlen.
Im ersten Fall läßt sich das Problem auf ungewichtetes Vertex Cover reduzieren und so ein gleich schneller Algorithmus erzielen. Im zweiten Fall gibt es einen Algorithmus, der etwas langsamer ist. Beide Algorithmen sind sogenannte "fixed parameter" Algorithmen, welche schnell sind, wenn das kleinste Vertex Cover nur kleines Gewicht hat.
Ich möchte in diesem Zusammenhang einen kleinen Überblick über die Theorie der "Parametrized Complexity" geben, einem relativ neuen Zweig der Komplexitätstheorie, der von Downey und Fellows gegründet wurde. Für beliebige Gewichte stellt sich dabei heraus, daß das Problem wahrscheinlich nicht "fixed parameter tractable" ist.
*Di,18.1.2000,15:15
Markus Lohrey (Universität Stuttgart)
Zum Konfluenzproblem für Spurersetzungssysteme
Ersetzungssysteme über Spurmonoiden, oder kurz Spurersetzungssysteme, verallgemeinern sowohl Semi-Thue Systeme als auch Vektorersetzungssysteme. Viele der für diese beiden Klassen bekannten Entscheidbarkeitsresultate können jedoch nicht auf Spurersetzungssysteme verallgemeinert werden. Während z.B. für terminierende Semi-Thue Systeme Konfluenz entscheidbar ist, wurde von Narendran und Otto ein Spurmonoid angegeben, für welches bereits Konfluenz für längenreduzierende Systeme unentscheidbar ist. In dem Vortrag werden einige neue Resultate zum Konfluenzproblem für Spurersetzungssysteme vorgestellt. Es wird gezeigt, daß das oben erwähnte Unentscheidbarkeitsresultat von Narendran und Otto für alle Spurmonoide gilt, die weder frei noch frei kommutativ sind. Außerdem soll gezeigt werden, da"s Konfluenz entscheidbar ist, falls alle rechten Seiten des betrachteten Spurersetzungssystems leer sind.
*Mi,26.1.2000,14:15
Thomas Erlebach
Routing flow through a strongly connected graph
It is shown that, for every strongly connected network in which every edge has capacity at least D, linear time suffices to send flow from source vertices, each with a given supply, to sink vertices, each with a given demand, provided that the total supply equals the total demand and is bounded by D. This problem arises in a new maximum-flow algorithm of Goldberg and Rao.
This is joint work with Torben Hagerup
*Mi,2.2.2000
Barbara König
Beschreibung und Analyse von verteilten Systemen durch Hypergraph-Konstruktion
Reaktive Systeme von miteinander kommunizierenden Prozessen können oft auf natürliche Weise durch Graphen (Statik) und Graphersetzung (Dynamik) beschrieben werden.
Hypergraphen sind eine Verallgemeinerung von gerichteten Graphen, bei denen jede Kante mit beliebig vielen Knoten verbunden sein kann, und für die es einen besonders intuitiven Ersetzungsmechanismus gibt. Ein Nachteil ist die Tatsache, daß es bislang kaum Ansätze gibt, Hypergraphen induktiv über ihren Aufbau zu beschreiben. In diesem Vortrag wird ein neuer Operator zur Konstruktion von Hypergraphen eingeführt, der eine eindeutige Zerlegung von Hypergraphen in Hyperkanten ermöglicht und für den man lineare Abbildungen (analog zu linearen Abbildungen in Vektorräumen) definieren kann.
Die eingeführten Operationen kann man nutzen, um verteilte Systeme (wie beispielsweise den asynchronen polyadischen Pi-Kalkül) zu modellieren und zu analysieren.
*Fr,4.2.2000,10:15
Klaus Reinhardt (Universität Tübingen)
Die #a=#b Bilder sind erkennbar
Giammarresi, Restivo, Seibert und Thomas definieren eine Bildsprache als lokal, wenn sie beschrieben werden kann als Menge der Bilder, bei denen jedes 2x2 Unterbild zu einer festgelegten Menge von 2x2 Kacheln gehört. Die Menge der erkennbaren Sprachen ist der Abschluss der lokalen Sprachen unter Projektion.
Es wird gezeigt, dass die Sprache der Bilder aus gleich vielen a's wie b's erkennbar ist. (Bei nicht entartetem Höhen-Breiten Verhältnis)
*Mi,9.2.2000
Mark Scharbrodt
Performance in stochastic min sum scheduling
In stochastic scheduling theory a strategy is considered to be optimal if it minimizes the expected value of the objective function of the problem under consideration. We propose a second, perhaps more accurate performance measure, namely the exected relative performance towards an optimal offline algorithm. This approach is similar to the standard competetive analysis for online algorithms. We investigate the optimality of List-based scheduling strategies under this adapted performance measure and give bounds on the expected relative performance. The overall example is the problem of minimizing the total completion times on a single machine in a stochastic environment, i.e. the problem 1 | p_j \sim stoc | sum C_j. We show that the SEPT is an optimal strategy if all processing times are given by random variables that have an exponential distribution. For the case that all processing times are given by the standard exponential distribution we also provide an upper bound near 3 on the expected relative performance of SEPT. This bound is derived via the analysis of a simple random strategy which schedule the jobs in a random order. For the weighted version of the problem we show that the expected relative performance under the random strategy may be arbitrarily bad.
*Mi,16.2.2000
Maximilian Frey
Testautomatisierung für Telekommunikationsnetze
Der Telekommunikationsmarkt ist einer der am schnellsten wachsenden und sich verändenden Märkte. Gerade im Mobilfunkbereich nimmt die Komplexität der Betriebsnetze aufgrund der Einführung neuer Technologien und Services (z.B. GPRS, UMTS, Homezone (Genion)) in extermen Maße zu. Dies führt sowohl bei Herstellern als auch Netzbetreibern zu extremen Druck, die Erwartungen der Kunden in Bezug auf Qualität und time to market neuer Produkte zu erfüllen. Automatisierung gerade im Testbereich wird daher als immer wichtigerer Faktor angesehen.
Neben der Einführung strukturierter Testmethoden im Bereich des Protokoll-Testings haben sich unterschiedliche Methoden zur automatischen Testgenerierung im Bereich des Conformance Testings entwickelt. Im Telekommunikationsbereich verwenden diese Methoden i.a. FSM als Modell, da die von internationalen Standardisierungsgermie (ITU, ETSI) verwendete Sprache SDL auf EFSM beruht.
Der Vortrag gibt einen Einblick in den Bereich des automatischen Testens von Telekommunikationsnetzen sowie einen Überblick über unterschiedliche auf FSM beruhende Verfahren zur Testfallgenerierung aus Protokollspezifikationen. Für die Anwendbarkeit der Methoden bedeutende Einschränkungen werden diskutiert, sowie Lösungsvorschläge kurz skizziert.
*Do,17.2.2000,
14:15-15:45,
Raum 2502
Harold Boley (DFKI GmbH Kaiserslautern)
Beziehungen zwischen Logigprogrammierung un XML
Die Zusammenfassung des Vortrags befindet sich auf der Seite des Oberseminars KI/Kognition.


Martin Raab Last modified: Tue Feb 15 14:51:52 MET 2000
Thomas Erlebach, 1998-04-29