 DIMACS Workshop on Computing Approximate Solutions to NP-hard Problems(Click here for more info.) February 20 - 22, 2000
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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. |