Fundamentals of Combinatorial Optimization and Algorithm Design
Abstract
The main activities supported under this grant are research and support for C. Chekuri, B. Shepherd and P. Winkler. Funds also supported one summer intern, Andrew McGregory from U-Penn, who worked with Shepherd on recognizing Hilbert Bases and other theoretical topics in Math Programming. Visits from scientists include a 2-week visit from Gianpaolo Oriolo (Rome), which resulted in new joint work on robust network design, a week visit from Seffi Naor (Technician) and a visit from Anreas Sebo who spoke on a new result of Bessy and Thomasse that solves an old conjecture of Gallai. Research highlights this year include: proof that in planar graphs with all capacities at least 2, the integrality gap for edge-disjoint paths is polylogarithmic (the paper was invited for the selected papers issue devoted to FOCS 2005); a first result showing the hardness of the robust network design and introduction of the single-source hose model for robust networks; and an unlikely question: is it hard to determine whether the rows of 0,1 matrix form a Hilbert Basis? Conferences attended were the 2004 APPROX/RANDOM (Chekuri), CORC 4th Optimization Day, INOC, Aussois workshop (Shepherd), and a workshop in Bertinoro, Italy (Chekuri & Shepherd).
Document Details
- Document Type
- Technical Report
- Publication Date
- May 24, 2005
- Accession Number
- ADA434261
Entities
People
- Bruce Shepherd
- Chandra Chekuri
- Peter Winkler