Atlas home || Conferences | Abstracts | about Atlas
Host: DIMACS Center, Rutgers University
Sponsor: National Security Agency and Microsoft Research
Homepage: http://dimacs.rutgers.edu/Workshops/ProbAnal
Organizers: Martin Dyer (University of Leeds), Alan Frieze (Carnegie Mellon University)
Description:
The analysis of algorithms for NP-hard problems under distributional assumptions on the input, is an important approach to
dealing with hardness issues. As Karp remarked in his Turing award lecture, "I felt, however, that in the case of NP-complete
problems we weren't going to get the worst-case guarantees we wanted, and that the probabilistic approach was the best way
and perhaps the only way to understand why heuristic combinatorial algorithms work so well in practice." Random models are
also important as benchmarks for empirical testing of algorithms.
Here tools from probability theory (especially concentration inequalities), and the theory of random combinatorial structures, especially random graphs, play an important role. Problems such as finding Hamilton cycles in graphs or properly coloring them have been shown to be tractable under such assumptions. Simple heuristics have been defined which are likely to be asymptotically close to optimal with high probability. The paper of Karp on the TSP in the plane was of this type and was fundamental in stimulating interest in the subject. There are also, hybrid approaches, such as the analysis of semi-random models which combine aspects of worst case and average case analysis.
Sometimes there are results which show that the average case can be hard too. Many enumerative type algorithms have been shown to take exponential time with high probability. Of particular importance here is the result of Chvatal and Szemeredi showing that a certain random model of satisfiability, resolution can take exponential time with high probability. Levin introduced the notion of completeness on average to describe probabilistic models problems which are unlikey to have fast average case solution.
There are a variety of research goals: to extend average case analysis to new problems, to explore the effect of distributional assumptions on the behavior of algorithms, to identify distributions that are especially hard for particular problems.
The workshop aims to bring together researchers interested in all of these approaches.
Date received: October 07, 1999
© 2008 Atlas Conferences Inc.