This proposal seeks continued funding for the PI's work in his principal research area of Approximation Algorithms. Previous NSF-funded work by the PI's research group has successfully formulated and solved several interesting problems for approximation including the Buy-at-Bulk Network Design, $k$-Minimum Spanning Tree, Group Steiner Tree, and the Degree-bounded Minimum Spanning Tree problems. Our contributions to this area include mathematical programming relaxations of hard problems and novel ways to round such relaxations using deterministic and randomized rounding techniques, as well as new problem formulations.
The focus of this proposal is to address the solution of computationally hard problems in the vein of approximation algorithms by moving closer to more real-world constraints. Specifically, we propose work in directions involving incorporating integration, heterogeneity, competition, uncertainty, and hybrid input models into classical problems. The proposal reports on preliminary successes and ongoing investigation in each of these directions, and formulates specific new problems and approaches. The intellectual merit of the proposal is to push the frontiers of approximation algorithms in terms of expanding its scope and applicability, as well as the potential for discovery of new underlying techniques.
The proposal is complemented with an educational and outreach plan that continues the PI's involvement in broader educational goals such as participation in surveys, tutorials and teaching workshops, as well as new course and lecture note development. The broader impact of the proposal include graduate student training and placement in this research area as well as an extensive education plan aimed at increased dissemination of the PI's research to a broader audience including four-year college lecturers.
