[ University of Bonn | Dept. of Computer Science | Chair V | deutsche Version ]
December 3rd, 1999, 14.30, SeminarRoom N327
Malwina Luczak, University of Oxford
Reducing Network Congestion and Blocking Probability
Abstract We compare the performance of a variant of the standard Dynamic Alternative Routing (DAR) technique commonly used in telephone and ATM networks to a path selection algorithm that is based on the balanced allocations principle - the Balanced Dynamic Alternative Routing (BDAR) algorithm. While the standard technique checks alternative routes sequentially until available bandwidth is found, the BDAR algorithm compares and chooses the best among a small number of alternatives.
We show that, at the expense of a minor increase in routing overhead, the BDAR gives a substantial improvement in network performance in terms of both network congestion and blocking probabilities.
February 5th, 1999, 15 hst., SeminarRoom N327
Artur Czumaj, Paderborn
Applications of Non-Markovian Couplings to Generations of Random Permutations
Abstract Coupling is a classical technique to estimate convergence rates of ergodic Markov chains. Though in general it is known that every ergodic Markov chain possesses an optimal coupling proof of its mixing time, so far only very simple and restricted kinds of couplings have been used. The aim of this talk is to present the first non-trivial applications of non-Markovian couplings to estimate convergence rates of Markov chains. We analyze stochastic processes for generating permutations almost uniformly at random in distributed and parallel systems. All our protocols are simple, elegant and are based on performing disjoint transpositions executed in parallel. The challenging problem of our concern is to prove that the output configurations in our processes reach almost uniform probability distribution very rapidly, i.e. in a (low) polylogarithmic time. For the analysis of the aforementioned protocols we develop a novel technique, called delayed path coupling, that uses non-Markovian couplings for proving rapid mixing of Markov chains. We apply delayed path coupling to two stochastic processes for generating random permutations. For one process, we construct a non-Markovian coupling, and for the second one we prove the existenceof a non-Markovian coupling. Finally, we shall also briefly describe some applications of our stochastic processes for generating random permutations in distributed and parallel systems.
July 03rd, 1998, 14 hct., SeminarRoom N327
Lawrence L. Larmore and Wolfgang Bein, Las Vegas
The Trackless 2-Server Problem
Abstract The 10-competitive Irani and Rubenfeld algorithm for 2 servers is oblivious to the points of the underlying metric space and thus determines its moves merely by accessing certain distances between request points and server locations. As a side effect the algorithm does not ever store memory locations and is almost memoryless, i.e. the algorithm only requires the use of only one (real) variable for storage of relevant information. The algorithm also takes constant time per request.
Known trackless algorithms for the 2-server problem include BALANCE-SLACK, Chrobak and Larmore, which is 4-competitive and deterministic, HARMONIC, which is randomized and oblivious and is 3-competitive for 2 servers, and RANDOM-SLACK, also Chrobak and Larmore, which is also randomized and oblivious and 2-competitive for 2 servers. The word "trackless" was not used up until now, however.
Borodin and El-Yaniv recently posed as an open question to show a lower bound greater than 2 on the competitive ratio of any deterministic 2-server algorithm that uses constant time and space per request. They also mention that for such a lower bound the model of computation needed to be formalized.
We introduce the "trackless server problem", and formalize the concept of "trackless work functions". Within this framework we have determined that no deterministic trackless on-line algorithm for 2 servers can be less than 11/2 competitive.
We have created a web-based tutorial for the problem, which makes this new concept available in an innovative way. We will give an introduction to this tutorial.
June 29th, 1998, 13 hct., SeminarRoom N327
Prof. Carl Smith, Univ. Karlsruhe und Univ. of Maryland
Towards a Theory of Discovery
Abstract The models used in inductive inference have their roots in the models used by the philosophers of science who were discussing the scientific method. The goal there, and in prior work in learning theory, was to come up with an explanation of the phenomenon under consideration. However, scientists rarely work directly for the grand goal of a complete explanation. The more modest goal of finding features and facts about the observed data is pursued. A variety of types of algorithms that could be construed as discovering their final result are defined and considered. We start by considering computations that discover their intended result. Then we consider learning where conjectures are accompanied by expectation levels of correctness. Finally, a logic of discovery is introduced. This study is particularly relevant to contemporary science as automated data generation techniques produce sufficient volumes of data to overwhelm the analysis abilities of humans. The goal of our work is to illuminate precisely what can and cannot be accomplished by automatic data analysis algorithms. Such algorithms are used in data mining and text analysis for world wide web search engines.
June 26th, 1998, 15 hct., SeminarRoom N327
Stasys Jukna, Trier, Vilnius
Entropic Approach to Proving Lower Bounds for Branching Programs
Abstract We propose an information-theoretic approach to proving lower bounds on the size of branching programs (b.p.). The argument is based on Kraft-McMillan type inequalities for the average amount of uncertainty about (or entropy of) a given input during various stages of the computation. We first demonstrate the approach for read-once b.p. Then we introduce a strictly larger class of so-called "gentle" b.p. and, using the suggested approach, prove that some explicit Boolean functions, including the Clique function and a particular Pointer function (which belongs to AC$^0$), cannot be computed by gentle program of polynomial size. These lower bounds are new since explicit functions (like the characteristic functions of some linear codes), which are known to be hard for all previously considered reading-restricted classes of b.p. (such as (1,+s)-b.p. or syntactic read-k-times b.p.) can be easily computed by gentle b.p. of polynomial size.
(Joint work with S. Zák)
March 23rd, 1998, 14 hct., SeminarRoom N327
Jürgen Wirtgen, Bonn
On Approximation Intractability of the Bandwidth Problem
Abstract The bandwidth problem is the problem of enumerating the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications. There was not much known about approximation hardness of this problem till recently. In this talk we show, that there is no PTAS for the bandwidth problem unless P = NP, even for the trees. More precisely we prove that there are no polynomial time approximation algorithms for general graphs with an approximation ratio better than 1.5 and for the trees with an approximation ratio better than 4/3.
(Joint work with Gunter Blache and Marek Karpinski)
January 9th, 1998, 15 hct., SeminarRoom N327
Yousry Abdallah and Jens Luessem, Bonn
Online Algorithms and Functional Programming Language
Abstract We consider the online problem of scheduling permanent jobs on related machines. We show some of our recent results of the implemention of several "Online Load Balancing" - algorithms
(Joint work with Ralf Hinze, Bonn)
January 9th, 1998, 14 hst., SeminarRoom N327
Piotr Berman, Penn State
Sorting by reversals: 11/8 algorithm
Abstract The problem is to sort a string consisting of n distinct numbers, assuming that the only allowed operation is a reversal, i.e. in one operation a string uvw can be replaced with uv^Rw. The goal is to minimize the number of reversals needed to convert a given sequence into a monotone one. One of the application of the problem is estimating the evolutionary distance between genomes by counting the number of mutations that have rearranged the order of genes. We present a 11/8 approximation that uses two stage reduction of the problem; first to the maximization of the number of alternating cycles that cover the set of edges in a two-colored graph, and next to a special kind of maximum idependent set problem.
(Joint work with Dr. Sridhar Hannenhali)
December 19th, 1997, 14 hst., SeminarRoom N327
Cristina Bazgan, L.R.I. Paris
Good approximation algorithms for a variant of "Subset Sum"
problem
Abstract We are interested in a variant of "Subset Sum" problem that has in the input n positive integers and we search two nonempty disjoint subsets with:
(Joint work with Miklos Santh and Zsolt Tuza)
December 12th, 1997, 14 hst., SeminarRoom N327
Christoph Günzel, Bonn
Schnelle Invertierung von Cauchy Matrizen
Abstract In diesem Vortrag wird eine verbesserte Methode zur Invertierung von Cauchy Matrizen via der Berechnung des charakteristischen Polynoms [V.Y. Pan, STOC'97] vorgestellt. Das Verfahren hat unmittelbare Anwendung zur Verbesserung der Laufzeit des Invertierungsalgorithmus für Cauchymatrizen, der in dem auf dem Cauchy-Verfahren beruhenden Decodierungsalgorithmus für MDS-Codes verwendet wird. Die beiden Verfahren werden in dem Vortrag kurz verglichen.
November 14th, 1997, 15 hct., SeminarRoom N327
Katja Wolf, Köln
Finding Dense Subgraphs with Semidefinite Programming
Abstract We consider the problem of computing the heaviest k-vertex induced subgraph of a given graph with nonnegative edge weights. This problem is known to be NP-hard, but its approximation complexity is not known. For the general problem only an approximation ratio of $\tilde{\O}(n^{0.3885})$ has been proved (Kortsarz and Peleg (1993)). In the last years several authors analyzed the case $k = \Omega(n)$. In this case Asahiro et al. (1996) showed a constant factor approximation, and for dense graphs Arora et al. (1995) obtained even a polynomial-time approximation scheme. We give a new approximation algorithm for the problem based on semidefinite programming and randomized rounding which achieves the presently best (randomized) approximation factors for arbitrary graphs and k = n/c for c > 1. For example for k = n/2 our approximation factor of 0.58 improves on the previously best approximation factor of 0.44 due to Asahiro et al.
(Joint work with Anand Srivastav, Berlin)
September 17th, 1997, 11 hct., SeminarRoom N327
Jürgen Wirtgen, Bonn
Approximationsalgorithmen für das Bandwidth-Problem auf Dichten
Graphen
Abstract Das Bandwidth-Problem ist das Problem, die Knoten eines gegebenen Graphen G so anzuordnen, daß der Abstand zwischen benachbarten Knoten minimal wird. Das Problem ist NP-vollständig und es gibt nur wenige Algorithmen, die lediglich Spezialfälle des Problems exakt oder approximativ lösen. In diesem Vortrag stellen wir einen randomisierten 3-Approximationsalgorithmus für das Bandwidth-Problem auf dichten Graphen vor. Ferner zeigen wir, daß das Problem auf dichten Graphen auch NP-vollständig ist.
(Gemeinsame Arbeit mit Marek Karpinski und Alex Zelikovsky)
July 11th, 1997, 14 hct., SeminarRoom N327
Lawrence L. Larmore, Las Vegas
On-Line Matrix Searching
Abstract The on-line matrix searching problem is to find the minimum of every row of a lower triangular matrix, with the restriction that no column can be seen until the minimum of every prior row has been found. There is an O(n) time algorithm for the on-line matrix searching problem if the matrix satisfies the Monge property. This algorithm is an on-line adaptation of the famous (off-line) SMAWK algorithm. As an application, the optimal (prettiest) paragraph can be formed from a given list of n words in linear time. The algorithm first appeared in a joint paper with Baruch Schieber.
June 27th, 1997, 14 hct., SeminarRoom N327
Elias Dahlhaus, Bonn
Minimum Fill-In für Distanzerbliche Graphen
Abstract Das Fill-in einer Ordnung auf der Eckenmenge eines Graphen ist die Menge der Kanten, die man hinzufügen muß, um die größeren Nachbarn einer jeden Ecke paarweise adjazent zu machen. Fill-ins treten bei der Gauss-Elimination dünnbesetzter positiv definiter Matrizen auf. Ziel ist es, eine Ordnung zu finden, die die Anzahl der Fill-in-Kanten minimiert. Das Problem ist NP-vollständig. In diesem Vortrag werde ich beweisen, daß dieses Problem für distanzerbliche Graphen in linearer Zeit gelöst werden kann.
(Gemeisame Arbeit mit H. Broersma und T. Kloks)
June 9th, 1997, 11 hct., SeminarRoom N327
Jürgen Wirtgen, Bonn
Untere Schranken für Approximationsprobleme
Abstract In diesem Vortrag sollen einfache Methoden vorgestellt werden um die Nichtapproximierbarkeit von Optimierungsproblemen zu beweisen. Dabei wird z.B. bewiesen, daß man mit einer guten Approximation an die Optimallösung eines Optimierungsproblems ein anderes NP-vollständiges Problem lösen kann. Es werden sowohl Standardtechniken, als auch neue PCP-basierende Techniken beschrieben.
May 5th, 1997, 10 hct., SeminarRoom N327
Jürgen Wirtgen, Bonn
Approximationsalgorithmen für das Bandwidth-Problem auf Dichten
Graphen
Abstract Das Bandwidth-Problem ist das Problem, die Knoten eines gegebenen Graphen G so anzuordnen, daß der Abstand zwischen benachbarten Knoten minimal wird. Das Problem ist NP-vollständig und es gibt nur wenige Algorithmen, die lediglich Spezialfälle des Problems exakt oder approximativ lösen. In diesem Vortrag stellen wir einen randomisierten 3-Approximationsalgorithmus für das Bandwidth-Problem auf dichten Graphen vor. Ferner konstruieren wir einen randomisierten 2-Approximationsalgorithmus für das gleiche Problem auf dichten gerichteten Graphen.
(Gemeinsame Arbeit mit Marek Karpinski und Alex Zelikovsky)
April 28th, 1997, 11 hct., SeminarRoom N327
Carsten Dorgerloh, Bonn
Schnelle randomisierte und parallele Algorithmen zum Auffinden von
einfachen Kreisen in Graphen
Abstract Das Auffinden eines längsten Kreises in einem Graphen G ist ein hartes Problem, da das Auffinden eines Hamiltonkreises NP-vollständig ist. Infolgedessen ist das Auffinden eines einfachen Kreises der Länge k für ein beliebiges k NP-vollständig. Dies gilt sogar dann, wenn G planar ist und unter anderen Einschränkungen. Daher widmet man dem folgendem Problem besondere Aufmerksamkeit: Dem Auffinden von einfachen Kreisen einer gegebenen Länge. Wir zeigen, daß ein einfacher Kreis einer gegebenen Länge k in einem planaren Graphen, wenn einer existiert, von einer randomisierten EREW-PRAM berechnet werden kann. Der Erwartungswert der Laufzeit des Algorithmus beträgt O(log n) unter Verwendung von O(n) Prozessoren. Kürzlich haben wir einen randomisierten sequentiellen Algorithmus entwickelt, der dieses Problem für allgemeine Graphen in O(max{m, n log n}) erwarteter Laufzeit löst. Dieser Algorithmus kann mit einem geringen Verlust an Effizienz derandomisiert werden. Darüber hinaus läßt sich der randomisierte Algorithmus derart parallelisieren, so daß er das obige Ergebnis für planare Graphen verallgemeinert.
(Gemeinsame Arbeit mit Jürgen Wirtgen)
April 21st, 1997, 11 hct., SeminarRoom N327
Jürgen Wirtgen, Bonn
Zur Komplexität von Dichten Approximationsproblemen
Abstract In diesem Vortrag wird eine kurze Einführung in die Theorie der Approximationsalgorithmen gegeben. Es werden Techniken beschrieben um untere und obere Schranken für Approximationen zu beweisen. Auf dichte Approximations Probleme wird im besonderen eingegangen. Eine Vielzahl von Problemen die aus der Sicht der Approximierbarkeit hart sind, können im dichten Fall in polynomieller Zeit gelöst werden. Wir werden einige dieser Probleme im Detail betrachten.