DIMACS Workshop on Computing Approximate Solutions to NPhard Problems(Click here for more info.) February 20  22, 2000

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