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

# ESPRIT Working Group "Randomized Algorithms" RAND2 (No. 21726)

## Contents

• Keywords
• Objectives and Approach
• Workshops and Seminars
• Results
• Contact Point
• Partner List
• Acknowledgements

• ## Keywords

Randomized algorithms, approximation algorithms,
quantum computation, neural networks,
combinatorial enumeration, randomized complexity theory,
random generation of combinatorial structures, pseudorandom computation,
randomized boolean and arithmetic circuits,
computational learning theory.

## Objectives and Approach

In recent years randomized algorithms, approximation algorithms and randomized complexity theory have become major subjects of study in the design of computer algorithms and in the theory of computation. For some computational problems, it appears now that randomized or pseudo-randomized algorithms are more efficient than the deterministic ones (in terms of hardware size, running time, circuits depths, transparent descriptions, etc.). The very striking examples recently are the new randomized approximation algorithms for enumerating the number of perfect matchings in certain classes of graphs or for some enumeration problems in the boolean algebra and the finite fields, new approximation schemes for instances of NP-hard problems, estimating the volume of convex bodies, and the quantum algorithms for factoring integers. Another breakthrough on estimating VC dimension and sample sizes of sigmoidal neural networds, the networks most frequently used in various applications, was achieved recently by the RAND researchers (using a combination of certain techniques from combinatorics, differential topology, algebraic geometry and model theory). Solutions to these problems have applications ranging from the algorithms and network design and coding theory to statistic mechanic and quantum field theory.

In this new and fast growing area, we are confronted with the number of very fundamental questions for which the classical theory of computation knows only hardly the answers. It remains for example an important open question how much randomness is necessary to accomplish certain levels of efficiency in algorithms, and also how efficient the deterministic simulation of some classes of algorithms is possible. The proposal plans on continuing the research started in RAND and will address the above mentioned problems, and concentrate on:

1. Design of efficient (both sequential and parallel) randomized algorithms for some selected combinatorial, algebraic and geometric problems;
2. Foundations of randomized complexity of computational problems;
3. Randomized approximation problems;
4. Computation with limited randomness resources (de-randomization methods);
5. Error-Resilient ATM Based Transmission;
6. Computational learning theory, theory of Neural Networks, and applications;
7. Quantum Computation.

The topic "Quantum Computation" extends the research program initiated in RAND - Working Group. We plan research on foundations of quantum computation, in particular on the power of quantum circuits, and the quantum approximation algorithms.

The selection of the partners for this Working Group was based on the grounds of the relevance of their research towards the above topics. The extension of the RAND2 by the Weizmann Institute, Rehovot, was motivated by the relevance of the research conducted there towards topics (1) - (4).

## Workshops and Seminars

### 2000 Program

RAND Seminar

December 15th, 2000, 15.30, Seminar Room N327
Mathias Hauptmann, University of Bonn, Germany

Some Open Questions on Steiner Tree Problems

Abstract    In the Steiner Tree Problem, we are given an edge weighted graph G and a subset S of the vertices of G. We ask for a shortest connected subgraph of G containing S. If edge weights are nonnegative, this will always be a tree. The Steiner Tree Problem is well-known to be MAX SNP-hard, therefore one is interested in polynomial time approximation algorithms. In this talk we give a survey on the Steiner Tree Problem, discuss several open problems concerning the design of approximation algorithms, provable lower bounds for approximability, generalizations and applications.

RAND Seminar

November 27th, 2000, 10.15, Seminar Room N327
Piotr Berman, Pennsylvania State University, USA

Improvements on MIS Problem with a Wrong Objective

Abstract    We consider a problem of maximizing the weight of an independent set in graphs where no $k$ neightbors of a single node may form an independent set. A natural algorithm is to inspect improvements of the candidate set A. An improvement of A is defined by an independent set I of size below k, and performs N <- neighbors of I, C <- C-N, C <- $C\cup I$. As long as there is a good improvement we perform one. Chandra and Halldorsson defined an improvement to be good if the sum of node weights of C increases. They have shown that this approximation algorithm does not guarantee better results than the optimum divided by 2/3k. We will show that the approximation improves if the good improvement is defined as the one that increases the sum of squares of node weights. In particular, the maximum optimum/achieved ratio drops to 1/2k.

RAND Seminar

June 5th, 2000, 11.15, Seminar Room N327
Lars Engebretsen, Royal Institute of Technology, Stockholm

Hardness of Approximating the Maximum Clique Problem

Abstract    It is known that the size of the maximum clique in a graph with $n$ vertices cannot be approximated in polynomial time within $n^{1-\epsilon}$, for any constant $\epsilon > 0$, unless NP = ZPP. In this talk, we extend the reductions used to prove this result and combine the extended reductions with a recent PCP characterization of NP (Samorodnitsky and Trevisan 2000) to show that the size of the maximum clique in a graph with $n$ vertices cannot be approximated within $n^{1-O(1\slash \sqrt{\log \log n})}$ unless NP is contained in ZPTIME$(2^{O(\log n(\log \log n)^{3\slash 2})})$. As a comparion, the best known upper bound is $n \slash \log^2 n = n^{1 - 2 \log \log n \slash \log n}$ (Boppana and Halldorsson 1992)

RAND Seminar

May 12th, 2000, 11.15, SeminarRoom A121
Martin Zachariasen, University of Copenhagen

Unifying Steiner Tree Problems - With Computational Success

Abstract    In this talk we describe a common framework for solving both geometric and non-geometric Steiner tree problems to optimality. The set of problems includes the Euclidean and rectilinear Steiner tree problem in the plane, their obstacle-avoiding variants and the ordinary (non-geometric) Steiner tree problem in graphs. We also indicate how extensions to node weighted and prize collecting Steiner tree problems can be made. All these problems can be reduced to the Steiner tree problem in hypergraphs. We give an integer program formulation for solving this problem. The formulation is solved by branch-and-cut using a tight LP-relaxation. Separation methods and implementation details are given. Finally, we report recent computational results, including the solution of large geometric instances.

RAND Seminar

May 15th, 2000, 10.00, SeminarRoom N327
Peter Wegner, University of Bonn

A survey on the Network Steiner Tree Problem

Abstract    The Steiner Tree Problem in Networks is MAXSNP-hard, and therefore no polynomial time approximation scheme exists (assuming P not being equal to NP). A simple heuristic based on spanning trees archieves an approximation ratio of 2. In the last years several more sophisticated algorithms were given, stepwise improving the approximation ratio. In this talk we give a survey on the various algorithms and discuss the central ideas they are based on.

RAND Seminar

May 19th, 2000, 14.15, SeminarRoom N327
Mathias Hauptmann, University of Bonn

The Algorithm of Robins and Zelikovsky for the Network Steiner Tree Problem

Abstract    In this talk we complete the survey on approximation algorithms for the Network Steiner Tree Problem by presenting the algorithm of Gabriel Robins and Alexander Zelikovsky. This is the best known polynomial time approximation algorithm archieving an approximation ratio of ln(3)/2.

### 1999 Program

RAND Seminar

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.

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

Esprit Working Group RAND2
Workshop on Randomized Algorithms,
Oxford,
Sept. 19-22, 1999.

Esprit Working Group RAND2
Workshop on Randomized Algorithms
Thursday 20th May - Saturday 22nd May, 1999
Gif-sur-Yvette, Université de Paris-Sud

### 1998 Program

RAND Seminar
University of Bonn

Séminaire Complexité
Université de Paris-Sud

Esprit Working Group RAND2
Workshop under the auspices of the
International Center for Mathematical Sciences
(ICMS)
Friday 27th - Sunday 29th March, 1998
Edinburgh

### 1997 Program

RAND Seminar
University of Bonn

Séminaire Complexité
Université de Paris-Sud

Esprit Working Group RAND2
Workshop on Randomized Approximation Algorithms
Saturday 20th - Monday 22nd September, 1997
University of Leeds

## Contact Point

Contact Person:
Marek Karpinski

Dept. of Computer Science
Friedrich-Ebert-Allee 144
53113 Bonn
Germany

Phone and Fax:
+49 (0)228 734224 (office)
+49 (0)228 734327 (secretary)
+49 (0)228 734440 (fax)

Email:
marek@cs.uni-bonn.de

## Partner List

Institution
(with local RAND2 webpages)
Contact Email
University of Bonn Marek Karpinski marek@cs.uni-bonn.de
University of Edinburgh Mark Jerrum mrj@dcs.ed.ac.uk
University of Leeds Martin Dyer dyer@scs.leeds.ac.uk
Lund University Andrzej Lingas Andrzej.Lingas@dna.lth.se
Oxford University Dominic Welsh dwelsh@maths.ox.ac.uk
Université de Paris-Sud Miklos Santha Miklos.Santha@lri.fr
Weizmann Institute, Rehovot Moni Naor naor@wisdom.weizmann.ac.il
Mail alias for all members of RAND2:
rand2@cs.uni-bonn.de