DIMACS Workshop on Faster Exact Solutions for NP-Hard Problems


Program

Wednesday, February 23rd, 2000

8:45
REGISTRATION
9:10-9:40
Finding the closest lattice vector when it's unusually close --- Philip Klein, Brown University
9:45-10:15
An Exact Algorithm for 3-Coloring --- David Eppstein, University of California, Irvine
10:20-10:35
BREAK
10:40-11:10
Maximum Independent Set Algorithms: Improved Analysis --- Mike Robson, Universite de Bordeaux
11:15-11:45
Robust Algorithms for the Stable Set Problem --- Vadim Lozin, Rutgers University
11:50-12:20
Applying structions to the independent set problem --- Richard Beigel, DIMACS and University of Illinois
12:25-2:25
LUNCH BREAK
2:30-3:00
Algorithms for k-SAT based on Covering Codes --- Edward Hirsch, Steklov Institute of Mathematics at St. Petersburg
3:05-3:35
Faster Exact Solutions for Max2SAT --- Jens Gramm, University of Tuebingen
3:40-4:10
Using poly-time SAT decidable and recognisable hierarchies of conjunctive normal forms for improved SAT decision and general lower bounds on resolution with oracles --- Oliver Kullman, University of Toronto
4:15-4:35
BREAK
4:40-5:10
Improved Exponential Time Algorithms for Vertex Cover --- Jianer Chen, Texas A&M University
5:15-5:45
On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover --- Rolf Niedermeier, University of Tuebingen

Thursday, February 24th, 2000

9:00
REGISTRATION
9:30-10:30
Satisfiability Testing: Theory and Practice (Invited Talk) --- Bart Selman, Cornell University
10:35-10:55
BREAK
11:00-11:30
Exponential Algorithms for SAT and MAJSAT --- Michael Littman, AT&T Labs Research and Duke University
11:35-12:05
Complexity of k-SAT --- Ramamohan Paturi, University of California, San Diego