CS Dept. V: Appointments and Events

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

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION

Piotr Berman

Department of Computer Science
University of Bonn
53117 Bonn

We consider bounded occurrence (degree) instances of a minimum constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for graphs. MIN-LIN2 is an optimization problem for a given system of linear equations mod 2 to construct a solution that satisfies the minimum number of them. E3-OCC-MIN-E3-LIN2 is the bounded occurrence (degree) problem restricted as follows: each equation has exactly 3 variables and each variable occurs in exactly 3 equations. Clearly, MIN-LIN2 is equivalent to another well known problem, the Nearest Codeword problem, and E3-OCC-MIN-E3-LIN2 to its bounded occurrence version. MIN-BISECTION is a problem of finding a minimum bisection of a graph, while 3-MIN-BISECTION is the MIN-BISECTION problem restricted to 3-regular graphs only. We show that, somewhat surprisingly, these two restricted problems are exactly as hard to approximate as their general versions. In particular, an approximation ratio lower bound for E3-OCC-MIN-E3-LIN2 (bounded 3-occurrence 3-ary Nearest Codeword problem) is equal to MIN-LIN2 (Nearest Codeword problem) lower bound n^{Omega(1)/(log log n)}. Moreover, an existence of a constant factor approximation ratio (or a PTAS) for 3-MIN-BISECTION entails existence of a constant approximation ratio (or a PTAS) for the general MIN-BISECTION.
Joint work with Marek Karpinski.

Sampling k-Uniform Hypergraphs and Design of PTASs for Dense Instances of Min-CSP

W. Fernandez de la Vega

Laboratoire de Recherche en Informatique
Université Paris-Sud
Orsay

We introduce a new sampler technique for k-uniform hypergraphs and apply it to design the first polynomial time approximation schemes (PTASs) for dense instances of Min-Ek-Lin2 (the problem of minimising the number of satisfied equations within a system of linear equations mod 2 with exactly k variables per equation) and dense instances of Min-Ek-SAT.
Joint work with Christina Bazgan and Marek Karpinski.

A Polynomial-Time Approximation Algorithms for the Permanent of a Matrix with Non-Negative Entries

Mark Jerrum^*, Alistair Sinclair⁺ and Eric Vigoda^*

^*Department of Computer Science
University of Edinburgh
Edinburgh EH9 3JZ

⁺Computer Science Division
University of California, Berkley
Berkley, CA 94720

We present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries.

Approximability of Dense Nearest Codeword Problem

Marek Karpinski

Department of Computer Science
University of Bonn
53117 Bonn

We design a polynomial time approximation scheme (PTAS) for the dense instances of Nearest Codeword Problem (NCP). The problem can be formulated as a linear feasibility problem of constructing an assignment x for a given system of linear equations mod 2, which minimizes the number of unsatisfied equations. The Dense NCP was known to be NP-hard in an exact setting. The general problem is known to have exceedingly high lower approximation bound of n^{Omega(1)/(log log n)} (Dinur, Kindler, Raz, Safra, 2000), and an existence of a PTAS on dense instances comes as a surprise. The technique of solution depends on a method of approximating Smooth Polynomial Integer Programs (Arora, Karger and Karpinski, 1995), and a new density sampler technique for graphs and k-uniform hypergraphs developed recently by Bazgan, Fernandez de la Vega and Karpinski, 2000. Despite an importance of the general NCP problem, and its many motivations, not much was known about ''good'' approximation ratio algorithms, better than of order n, and this for arbitrary fields. Only recently the first polynomial time algorithm with sublinear approximation ratio O(n/logn) was designed for the general problem by Berman and Karpinski, 2001. A challenging problem remains to design a better approximation algorithm which works on general instances of NCP.

Coalescing Particles on a Tree

Claire Kenyon

Laboratoire de Recherche en Informatique
Université Paris-Sud
Orsay

The following problem is related to the average-case analysis of distributed updates on trees. Consider a perfect binary tree of height h. At time 0, we begin with a particle at each tree node. At each positive integer time, one of the remaining particles is chosen at random and moved up to its parent node, coalescing with any particle that might already be there. How long does it take until all particles coalesce (at the root)?
Joint work with Alistair Sinclair.

The RPR² rounding technique for semidefinite programs

Michael Langberg

Department of Computer Science and Applied Mathematics
Weizmann Institute of Science
Rehovot 76100

Several combinatorial optimization problems can be approximated using algorithms based on semidefinite programming. In many of these algorithms a semidefinite relaxation of the underlying problem is solved yielding an optimal vector configuration v₁ ... v_n. This vector configuration is then rounded into a {0,1} solution. We present a procedure called RPR² (Random Projection followed by Randomized Rounding) for rounding the solution of such semidefinite programs. We show that the random hyperplane rounding technique introduced by Goemans and Williamson, and its variant that involves outward rotation are both special cases of RPR². We illustrate the use of RPR² by presenting two applications. For Max-Bisection we improve the approximation ratio. For Max-Cut, we improve the tradeoff curve (presented by Zwick) that relates the approximation ratio to the size of the maximum cut in a graph.
Joint work with Uriel Feige.

Routing random calls on graphs

Malwina Luczak

Mathematical Institute
University of Oxford
Oxford OX1 3LB

We are given a complete graph and a sequence of calls uniformly distributed over the edges. For each call {v,u} in turn, the call is routed on the direct link if possible; and otherwise d nodes are selected uniformly at random from V-{v,u} and the call is routed via one of these nodes if possible. The first fit dynamic alternative routing algorithm FDAR chooses the first possible alternative route. The balanced dynamic alternative routing algorithm BDAR chooses an alternative route which minimises the maximum of the current loads on its two links. We compare the asymptotic blocking probability achieved by these algorithms. We further consider some extensions to non-complete graphs and asymmetric distributions of calls.

Quantum Algorithms for Some Instances of the Hidden Subgroup Problem

Miklos Santha

Laboratoire de Recherche en Informatique
Université Paris-Sud
Orsay

In the first part of the talk we give a survey on the status of the hidden subgroup problem, and in particular we sketch an efficient quantum algorithm for the Abelian case. In the second part we show that certain special cases of the non-Abelian case can also be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden normal subgroups of solvable groups and permutation groups, finding hidden subgroups of groups with small commutator subgroup and of groups admitting an elementary Abelian normal 2-subgroup of small index or with cyclic factor group.
Joint work with G. Ivanyos and F. Magniez.

The Complexity of Coefficients of Some Combinatorial Polynomials

Dominic Welsh

Mathematical Institute
Universtiy of Oxford
Oxford OX1 3LB

The two variable Tutte polynomial T(x,y) contains as specialisations one variable knot polynomials, the chromatic and flow polynomials of a graph, the partition function of the Ising and Potts models of statistical physics, the codeweight polynomial of linear codes over any finite field and the Ehrhart polynomial of a unimodular zonotope. In 1990, with F. Jaeger and D.L. Vertigan, we showed that unless #P=P (which is most unlikely) there is no polynomial time evaluation algorithm except at 8 special points and along two special curves of the (x,y) plane. In this talk I shall concentrate on the complexity of the individual coefficients of some of these polynomials and in particular describe some new hardness results obtained in joint work with James Oxley . I shall also describe the current state of knowledge on attempts to find polynomial time randomised algorithms for these quantities.