DIMACS Mixer Series - November 17, 1998

AT&T Labs Research, Florham Park, NJ

1.

Herve Bronnimann, Inria Sophia-Antipolis and NEC Research Inst.

"Recent Trends in robust geometric computing"

A geometric algorithm makes a combinatorial structure out of
combinatorial and numerical (hence continuous) data. This conversion
from continuous to discrete quantities poses problems when the
continuous data is the result of computations which do not yield
consistent values due to roundoff and approximation floating-point
errors. This leads the algorithm to enter inconsistent states and
sometimes to crash.

The talk will survey the problem and various approaches developed
recently to tackle it.


2.

Alex Samorodnitsky, Rutgers University

"A Deterministic Strongly Polynomial Algorithm for Matrix Scaling
and Approximate Permanents"

We present a deterministic strongly polynomial algorithm that 
computes the permanent of a nonnegative n times n matrix to 
within a multiplicative factor of e^n. To this end we develop 
the first strongly polynomial-time algorithm for matrix scaling 
- an important nonlinear optimization problem with many applications.
Our work suggests a simple new (slow) polynomial-time decision 
algorithm for bipartite perfect matching, conceptually different
from known approaches.

This is a joint work with Nati Linial and Avi Wigderson.


3.

David S. Johnson, AT&T Labs - Research

"A Self Organizing Bin Packing Heuristic"

Suppose there is a random process that generates items of various integer
sizes which we must pack into fixed size bins, and we wish to minimize
the total wasted space in the non-empty bins of the packing.  If N is
the number of items generated, it is known that the total waste in
the optimal packing must grow either as O(N), O(sqrt(N)), or O(1),
depending on the probability distribution.  Standard bin packing
algorithms such as Best Fit do not typically perform optimally (on those
distributions for which the optimal growth rate is known).  This is even
true for offline algorithms such as Best Fit Decreasing.

We show that although in general it is NP-hard to determine the optimal
growth rate given a distribution, this problem can be solved in
pseudo-polynomial time (polynomial in the bin size) using linear
programming.  We then describe a remarkably simple online algorithm that
we conjecture, based on extensive empirical tests, performs "optimally"
for ALL distributions.  The audience will be encouraged to propose
counterexamples.

This is joint work with Janos Csirik, Claire Kenyon, Peter Shor, and
Richard Weber.


4.

Sanjeev Arora, Princeton University

"The Approximability of NP-hard Problems: A Survey"

Since many optimization problems are NP-hard, researchers have tried to 
design approximation algorithms, which provably compute solutions whose 
cost is within a small factor of the cost of the optimum solution. During the 
past decade, very good approximation algorithms have been designed for 
many problems. For some other problems, we now know that no good 
approximation algorithms exist if P is different from NP. (In other words, 
if a good approximation algorithm exists for these problems, then P is 
equal to NP and hence an exact algorithm exists.) 

The talk will survey these two areas of active research.

Other Workshops

DIMACS Homepage