CAREER: Approximation Algorithms - New Directions and Techniques

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

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.