 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.
|
|
|
