[ University of Bonn | Dept. of Computer Science | Chair V | deutsche Version ]

# RAND Seminar

## (Chair V)

### Abstracts

• The RAND Seminar takes place in SeminarRoom N327.
• Seminar talks are hold either in German or in English.
• Contact: Peter Wegner
• Guests are welcome.

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

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

• Albers (1997)
• Aspnes et al. (1993)
• Berman, Charikar, Karpinski (1997)
with the functional programming language Haskell. We also show that functional programming languages are an appropriate means to implement online algorithms in a simple way. Furthermore we introduce an improved new variant of Aspnes' algorithm.

(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:

• the ratio of the sums of the numbers in the two sets minimum possible, problem called "Ratio Subsets Sum",
• the difference of the sums of the numbers in the two sets minimum possible, problem called "Difference Subsets Sum".
We give a fully polynomial time approximation scheme for "Ratio Subsets Sum". Also we give an algorithm that finds two subsets with the difference of the sums at most K/n^{log n} where K is the greatest number of the instance and we show that "Difference Subsets Sum" is not 2^{n^c}-approximable for any constant c.

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