CAREER: Approximability of Combinatorial Optimization Problems

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

Combinatorial optimization is concerned with finding optimal arrangements from within some finite space of arrangements. The theory of NP-completeness has shown that numerous combinatorial optimization problems that arise frequently in computer science and other fields are not likely to have polynomial time algorithms. One approach to overcome this fundamental intractability has been to shift focus from computing exact solutions to approximate solutions. This CAREER project involves research and teaching efforts aimed at developing our understanding of the approximability behavior of combinatorial optimization problems.The research component of this project has two broad directions. One direction is to obtain tight bounds on the approximability of some basic problems in the areas of graph optimization, network design and routing, and scheduling theory. Some representative examples include the graph k-coloring problem and the preemptive weighted flow time problem. The second direction is to build on our understanding of central problems and develop unifying frameworks that highlight inherent connections among seemingly unrelated techniques and results. The goal here is to identify minimal characteristics that determine the approximability of optimization problems. The educational component of this project will introduce an advanced undergraduate/graduate course on Approximability of Combinatorial Optimization Problems. Such problems routinely arise in almost all areas of computer science, including databases, networking and systems. Practitioners and researchers in these areas would benefit from learning the various powerful theoretical techniques and results for optimization problems. The PI will also introduce a freshman course on Mathematical Thinking and Reasoning to help undergraduate students develop their ability to write concise formal proofs