DIMACS Workshop on Computing Approximate Solutions to NP-hard Problems

(Click here for more info.)

February 20 - 22,  2000
Princeton, NJ (Nassau Inn)


(All events are at the Nassau Inn except the dinner, which is at Prospect House..)
For some of the abstracts see here. 

Sunday, Feb 20
9:30-10am Breakfast and coffee
10-10:45 Approximation Algorithms for Metric Facility Location and k-Median Problems
using the Primal-Dual Schema and Lagrangian Relaxation. Kamal Jain
10:45-11:15 Approximation Algorithms for Min-Sum Clustering, Moses Charikar
11:15-12:15 Open problems in approximation, Vijay Vazirani
12:15-2pm Lunch (served at the workshop)
2-2:30 Approximating minimum metric cost k-outconnected subgraphs. Joseph Cheriyan 
2:30-3:00 Directed Network Design with Orientation Constraints, Seffi Naor
3:00-3:30 Data Placement on Parallel Disks. Samir Khuller
3:30-4:00 Coffee and snack break
4:00-4:30 A Constant Factor Approximation Algorithm for a Class of Classification Problems. Anupam Gupta 
4:30-5:00 On two segmentation problems. Benjamin Sudakov 
6-8pm Dinner and reception at Prospect House.
Monday, Feb 21
9:30-10am Breakfast and coffee
10-10:45 On some PCPs with one free bit. Johan Hastad 
10:45-11:15 Clique is hard to approximate within n^{1-o(1)}: the explicit value of o(1). Lars Engelebrtsen
11:15-12:15 Open problems in hardness of approximation, Madhu Sudan
12:15-2pm Lunch (served at the workshop)
2-2:45 Average-Case Analysis of the Sum-of-Squares Bin Packing Algorithm. David Johnson
2:45-3:15 Approximation Hardness of Sorting by Reversals. Marek Karpinski
3:15-3:45 Hardness of approximating label cover. Irit Dinur
3:45-4:15 Coffee and snack break
4:15-4:45pm Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. Cliff Stein
4:45-5:15 Computing Approximate Solutions in Resource-Constrained Project Scheduling. Cindy Phillips
5:15-5:45 A unified approach to approximating resource allocation and scheduling. Reuven Bar-Yehuda
Participants are free to make their own dinner plans
Tuesday, Feb 22
9:30-10am Breakfast and coffee
10-10:45 Approximation Algorithms for Unsplittable Flow and the
Half-Disjoint Paths problem. Yossi Azar 
10:45-11:15 Fairness in Routing and Load Balancing. Jon Kleinberg
11:15-11:30 Coffee break
11:30-12 Improved Approximation Algorithms for MAX SAT. David Williamson 
12-12:30 Improved approximations for MAX-CUT in bounded degree graphs via semidefinite programming. Uri Feige
12:30-2 Lunch (served at the workshop)
2-2:30 Polynomial time approximation schemes for geometric k-clustering in high dimensional spaces.Yuval Rabani 
2:30-3:00 On the Hardness of 4-coloring a 3-colorable Graph.Sanjeev Khanna
3:00-3:30  Coffee and snack break
3:30-4:00 Nested Graph Dissection and Approximation Algorithms. Sudipto Guha
4-4:30 Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas. Guy Even
4:30-5:15 Polyhedra, Approximability, and the TSP. Santosh Vempala
Workshop ends; there is another workshop the following day.