CAREER: Approximation Algorithms - New Directions and Techniques

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

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.