[
University of Bonn

Department of Computer Science

Chair V
]
Approximation Hardness of Bounded Degree MINCSP and MINBISECTION
Piotr Berman
Department of Computer Science
University of Bonn
53117 Bonn
We consider bounded occurrence (degree) instances of a minimum constraint
satisfaction problem MINLIN2 and a MINBISECTION problem for graphs.
MINLIN2 is an optimization problem for a given system of linear equations
mod 2 to construct a solution that satisfies the minimum number of them.
E3OCCMINE3LIN2 is the bounded occurrence (degree) problem restricted as
follows: each equation has exactly 3 variables and each variable occurs in
exactly 3 equations. Clearly, MINLIN2 is equivalent to another well known
problem, the Nearest Codeword problem, and E3OCCMINE3LIN2 to its bounded
occurrence version. MINBISECTION is a problem of finding a minimum
bisection of a graph, while 3MINBISECTION is the MINBISECTION problem
restricted to 3regular 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
E3OCCMINE3LIN2 (bounded 3occurrence 3ary Nearest Codeword problem) is
equal to MINLIN2 (Nearest Codeword problem) lower bound
n^{Omega(1)/(log log n)}. Moreover, an existence of a constant factor
approximation ratio (or a PTAS) for 3MINBISECTION entails existence of a
constant approximation ratio (or a PTAS) for the general MINBISECTION.
Joint work with Marek Karpinski.
Sampling kUniform Hypergraphs and Design of PTASs for Dense Instances of MinCSP
W. Fernandez de la Vega
Laboratoire de Recherche en Informatique
Université ParisSud
Orsay
We introduce a new sampler technique for kuniform hypergraphs and apply
it to design the first polynomial time approximation schemes (PTASs)
for dense instances of MinEkLin2 (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
MinEkSAT.
Joint work with Christina Bazgan and Marek Karpinski.
A PolynomialTime Approximation Algorithms for the Permanent of a Matrix with NonNegative 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 fullypolynomial randomized approximation scheme
for computing the permanent of an arbitrary matrix with nonnegative
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 NPhard
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 kuniform 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é ParisSud
Orsay
The following problem is related to the averagecase
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^{2} 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_{1} ... v_{n}. This vector configuration is
then rounded into a {0,1} solution. We present a procedure called
RPR^{2} (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^{2}. We illustrate the use of RPR^{2} by presenting two applications.
For MaxBisection we improve the approximation ratio. For MaxCut, 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 noncomplete graphs and
asymmetric distributions of calls.
Quantum Algorithms for Some Instances of the Hidden Subgroup Problem
Miklos Santha
Laboratoire de Recherche en Informatique
Université ParisSud
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 nonAbelian 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 2subgroup 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.
Last updated: Mai 28th, 2001
© InfoV > webmaster