[ University of Bonn | Department of Computer Science | Chair V | deutsche Version ]
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.
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:
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.
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.
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,
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
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
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
|
Institution (with local RAND2 webpages) |
Contact | |
|---|---|---|
| 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, followed by at-sign, followed by cs (dot) lth (dot) 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 |
||