Approximation Algorithms for Network Optimization

点击翻译按钮获取中文摘要

Networks underlie much of the progress in global connectivity and communications, and have enabled many of the advances in modern life. Network optimization studies networks in the abstract by formulating problems on the construction and usage of such networks. Many of the computational problems posed in this area are intractable motivating the design of heuristic approximation algorithms that run fast and deliver solutions that are provably near-optimal. The key thrust of the proposal is to design new and improved approximation algorithms for basic network problems incorporating side constraints and directionality of links building on some recent successes.Fundamental problems in network optimization remain unresolved in their approximation guarantee achievable in polynomial time, particularly problems with side constraints (such as bi-criterianetwork design problems) as well as those in directed graphs (such as the directed Steiner tree problem). This proposal addresses these shortcomings. A secondary thrust of this proposal is to formulate new network optimization problems drawing upon frameworks from Operations Research such as chance-constrained programming. The intellectual merit of the proposal include pushing the frontiers of approximation algorithms, and introducing new theoretical models for network optimization. The proposal will enable the continuation of the investigator's strong involvement in broader educational goals such as participation in invited talks, tutorials and teaching workshops, as well as new course and lecture note development. The broader impacts of the proposal include training and placement of very strong graduate students in the interdisciplinary areas ofalgorithms, combinatorics and optimization.