CAREER: Approximation Algorithms - New Directions and Techniques

NP完备性理论表明，一些自然发生的问题不太可能有多项式时间算法。克服优化问题这一基本难解性的一种方法是将重点从精确解转移到获得近似解。因此，近似算法的研究已经成为一个丰富而令人兴奋的领域，最近的进展已经导致了一些基本优化问题的良好近似算法。尽管有了这些发展，仍然存在一些有趣而困难的开放性问题。这个职业发展计划的一个主要焦点是研究基本问题的近似性，并试图缩小我们理解中的这些差距。本职业发展计划的广泛研究目标如下：开发新的工具来设计有向图问题的近似算法。开发度量近似和嵌入的新技术，作为近似的构建模块。研究了一种获得和利用增强sdp的系统方法，以及在图划分最小化问题和排序问题中使用增强sdp。设计处理有优先级限制的调度问题的技术。将近似算法的机制扩展到新的设置，如信息理论和代数问题。该研究项目将涉及各个层次的学生，从通过计算实验了解LP和SDPrelaxations质量的本科项目到适合博士生的数学研究。该项目的教育部分包括开发课程，旨在传播理论计算机科学社区之外的新算法思想；在最新的研究中开发的技术将被提炼成新的研究生和本科课程。为这些新课程编写的教材将免费提供，以便在其他地方教授类似的课程。

The theory of NP Completeness has shown that several naturallyoccurring problems are unlikely to have polynomial timealgorithms. One approach to overcome this fundamental intractabilityfor optimization problems has been to shift the focus from exactsolutions to obtaining approximate solutions. The study ofapproximation algorithms has thus emerged as a rich and exciting fieldand recent advances have led to good approximation algorithms forseveral fundamental optimization problems. Despite these developments,several interesting and difficult open problems remain. A primaryfocus of this career development plan is studying the approximabilityof fundamental problems and attempting to close such gaps in ourunderstanding.The broad research goals of this career development plan are thefollowing:1. Developing new tools to devise approximation algorithms for problems on directed graphs.2. Developing new techniques for metric approximations and embeddings as building blocks for approximation.3. Investigating a systematic way to obtain and exploitstrengthened SDPs as well as the use of strengthened SDPs for graph partitioning minimization problems and ordering problems.4. Devise techniques to deal with scheduling problems withprecedence constraints.5. Extend the machinery of approximation algorithms to newsettings such as information theoretic and algebraic problems.The research program will involve students at all levels, fromundergraduate projects on understanding the quality of LP and SDPrelaxations through computational experiments, to the mathematicalresearch suitable for Ph.D. students. The educational component ofthis project includes the development of courses geared towardsdisseminating new algorithmic ideas outside the theoretical computerscience community; the techniques developed in the latest researchwill be distilled into new graduate and undergraduate courses. Coursematerials developed for such new courses will be made freely availableto enable similar courses to be taught elsewhere.