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


ESPRIT Working Group

"Randomized Algorithms"

RAND2 (No. 21726)


  • Keywords
  • Objectives and Approach
  • Workshops and Seminars
  • Results
  • Contact Point
  • Partner List
  • Links
  • 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 New!

    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.

    Esprit Working Group RAND2
    Workshop on Randomized Algorithms,
    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
    Friday 27th - Sunday 29th March, 1998

    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


    Annual Progress Report 1996 / 1997

    Contact Point

    Contact Person:
    Marek Karpinski

    Postal Address:
    Dept. of Computer Science
    Friedrich-Ebert-Allee 144
    53113 Bonn

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


    Partner List

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



    URL of this page: http://theory.cs.uni-bonn.de/info5/projects/RAND2.html
    Last updated: March 20th, 1998
    Maintained by: webmaster@cs.uni-bonn.de