Approximation algorithms for optimization problems

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

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.