Accession Number:

ADA429923

Title:

Fundamentals of Combinatorial Optimization and Algorithms Design: December Report

Descriptive Note:

Interim rept. 1 Jul-31 Dec 2004

Corporate Author:

LUCENT TECHNOLOGIES INC MURRAY HILL NJ

Personal Author(s):

Report Date:

2005-02-10

Pagination or Media Count:

6.0

Abstract:

The primary activities supported by the grant during the reporting period include a new result showing the hardness of the single-source robust network design and an invitation to include this in the special issue devoted to selected papers in FOCS 2005. A summer intern was hosted, Andrew McGregor from UPenn, who worked with Shepherd on recognizing Hilbert Bases and other theoretical topics in Math Programming. A visit was also supported for Gianpaolo Oriolo Rome, which resulted in some new joint work on robust network design. In addition, there was a week visit from Seffi Naor Technicion. Travel supported during this period includes trips by Shepherd to UPenn to work with Sanjeev Khanna and C. Chekuri on the mutlicommodity flow problem. This work has resulted in the FOCS 2005 paper, which in addition was invited into a special issue of selected papers. Conferences attended were the 2004 APPROXRANDOM Chekuri and CORC 4th Optimization Day Shepherd.

Subject Categories:

  • Numerical Mathematics
  • Computer Systems Management and Standards

Distribution Statement:

APPROVED FOR PUBLIC RELEASE