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

Contacting the Center

Document last modified on November 12, 1998.