Approximation algorithms for optimization problems

组合优化涉及为离散和有限性质的问题寻找最优解。这样的问题出现在计算机科学、数学、金融、生物学、医学和运筹学等多个领域。这些问题中的许多都太复杂了，如果不使用计算机就无法解决，因此需要有效的算法来解决它们。*有强有力的理论证据表明，对于许多组合优化问题，没有多项式时间算法可以计算出它们的精确解。这样的问题被称为NP-Hard。处理这些问题的一个基本工具是近似算法；这是一种有效的算法，其解的值可以被证明是远离最优解的某个因子c。*我的研究兴趣集中在近似算法的设计上。我特别感兴趣的是两类问题的近似算法的研究：网络问题和布局问题。网络是最优化中最基本的建模工具之一，在许多领域都有应用。布局问题在运输、VLSI设计、调度以及任何其他需要在有限空间中布置物体的应用领域中都是非常重要的。*在本研究方案中，我们将追求以下短期目标：*-研究结合使用局部搜索和其他优化技术来设计设施选址和集群问题的近似算法。*-设计固定参数易处理的近似算法来解决输入受限的布局和调度问题。*-为超大型网络(如社交网络)中的集群问题设计高效的近似算法。*-为分析和改进近似算法的性能设计有效的实验技术。

Combinatorial optimization deals with finding optimum solutions for problems of a discrete and finite nature. Such problems arise in areas as diverse as Computer Science, Mathematics, Finances, Biology, Medicine, and Operations Research, among others. Many of these problems are too complex to solve without the use of computers and, therefore, efficient algorithms for solving them are needed. ******There is strong theoretical evidence suggesting that for many combinatorial optimization problems no polynomial time algorithm can compute exact solutions for them. Such problems get the technical name of NP-hard. One fundamental tool for dealing with these problems is approximation algorithms; these are efficient algorithms that yield solutions whose values can be proven to be no more than some factor c away from the optimum.******My research interests center on the design of approximation algorithms. I am particularly interested in the study of approximation algorithms for two kinds of problems: Network and packing problems. Networks are one of the most fundamental modelling tools in optimization, with application to a large number of fields. Packing problems are of great importance in transportation, VLSI design, scheduling, and any other application domains requiring the arrangement of objects in bounded spaces.******Within this research proposal we will pursue the following short term goals:******- Investigate the combined use of local search and other optimization techniques in the design of approximation algorithms for facility location and clustering problems.******- Design fixed parameter tractable approximation algorithms for packing and scheduling problems with restricted inputs. ******- Design efficient approximation algorithms for clustering problems in very large networks, like social networks. ******- Design effective experimental techniques for analyzing and improving the performance of approximation algorithms.