Fundamentals of Combinatorial Optimization and Algorithm Design: Report for April 1 2006-March 31 2007

摘要

The main research output this year included work on degree- constrained network flows which was accepted by STOC 2007. Shepherd will give a plenary talk on this topic at CANADAM. Lucent has also applied for a patent based on this work. Work was also done on protected buy-at-bulk network design problems by Antonakopoulos, Chekuri Shepherd, and Zhang resulting in a manuscript, April 2007. Work was done by Andrews and Zhang on scheduling in wireless networks resulting in a manuscript. Work was done on flow-cut gaps in series-parallel graphs by Chekuri and Shepherd.