Accession Number:

ADA434261

Title:

Fundamentals of Combinatorial Optimization and Algorithm Design

Descriptive Note:

Final rept., 1 Jan-31 Mar 2005

Corporate Author:

LUCENT TECHNOLOGIES INC MURRAY HILL NJ

Report Date:

2005-05-24

Pagination or Media Count:

8.0

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 APPROXRANDOM Chekuri, CORC 4th Optimization Day, INOC, Aussois workshop Shepherd, and a workshop in Bertinoro, Italy Chekuri Shepherd.

Subject Categories:

  • Operations Research
  • Numerical Mathematics
  • Theoretical Mathematics
  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE