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