CAREER: Approximability of Combinatorial Optimization Problems

组合优化是从有限的排列空间中寻找最优排列的问题。NP-完备性理论表明，在计算机科学和其他领域中频繁出现的大量组合优化问题不太可能有多项式时间算法。克服这一根本难题的一种方法是将重点从计算精确解转移到近似解。这个职业项目包括研究和教学工作，旨在加深我们对组合优化问题的可逼近性态的理解。这个项目的研究部分有两个大的方向。一个方向是在图优化、网络设计和路由、调度理论等领域中的一些基本问题的可逼近性上获得严格的界。一些典型的例子包括图的k-染色问题和抢占式加权流时间问题。第二个方向是以我们对中心问题的理解为基础，制定统一的框架，突出看似不相关的技术和结果之间的内在联系。这里的目标是确定决定优化问题的可近似性的最小特征。这个项目的教育部分将介绍一门关于组合优化问题的可近似性的本科生/研究生高级课程。这类问题经常出现在计算机科学的几乎所有领域，包括数据库、网络和系统。这些领域的实践者和研究人员将受益于学习各种强大的优化问题的理论技术和结果。PI还将推出一门关于数学思维和推理的大一课程，以帮助本科生培养他们撰写简洁形式证明的能力

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