Resolving Anomalies in Approximation Algorithms

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

Many problems in combinatorial optimization are NP-hard, and unlikely to have efficient algorithms to find the optimal solution. These include multitudes of problems that arise in practice in industry, including locating facilities to service customer demands, scheduling service personnel to make onsite repairs, dispatching vehicles, constructing low-cost networks with specific connectivity properties, routing wires on chips, and many, many others. The typical approaches for solving these problems are to design some heuristic that in practice provides solutions that are good enough, or, if enough time and resources are available and an optimal solution is sufficiently valuable, to designan exhaustive search algorithm to find the optimal solution.In order to mathematically ground the study of heuristics, computer scientists have considered approximation algorithms. These are efficient, polynomial-time algorithms that produce solutions that are provably close in value to the optimal solution. In particular, an _-approximation algorithm produces a solution whose value is within a factor of _ of the value of an optimal solution. The parameter _ is sometimes called the performance guarantee of the algorithm. To prove that the algorithm produces a near-optimal solution, a bound on the optimal value must be used. This bound is often a quantity that can be computed efficiently on its own, and in many interesting cases is based on a linear programming relaxation of the problem. When a polynomial-time computable bound, such as a linear programming bound, is used to prove a strong performance guarantee, this also has implications for practitioners who solve problems to optimality using exhaustive search, since a strong bound is useful in quickly pruning the search space.The goal of the proposal is to study some anomalies in the current state of knowledge of approximation algorithms, since as in other areas of science, consideration of anomalies leads most quickly to new advances. Several known approximation algorithms use as their bound quantities that are not polynomial-time computable; or, even if polynomial-time computable, are difficult to show apriori are bounds on the problem being considered. Included in the study are problems of locating facilities that can serve a bounded amount of customer demand (the capacitated facility location problem), designing low-cost networks (the Steiner tree problem), and the routing of vehicles to minimize the average time at which a vehicle arrives at a customer (the minimumlatency problem). The goal of the research is to show that these algorithms can be restated in terms of polynomial-time computable bounds, and, as often as possible, bounds involving linear programming relaxations.Intellectual merit: Significant methodological innovations will likely be needed to resolvethese issues. Additionally, the PI expects to find simpler, better, more general, and more practical approximation algorithms as a result of this research. Furthermore, if polynomial-time computable bounds can be found for some of these problems, it will lead to better exhaustive search algorithms for finding the optimal solution for these problems. The PI is one of the leaders in the field of approximation algorithms and has an extensive track record of finding new methods and improved algorithms.Broader impact: The PI will train of graduate researchers in the broader area of combinatorial optimization and in conducting original research in the area of algorithms. Since one of the goals of the proposal is the simplification of current results, the broad dissemination of the results of the research through conference and journal publication should increase understanding in the area. Potentially the results of the research will be part of a graduate class that the PI has taught on several occasions on the subject of approximation algorithms; notes from previous versions of the class are publically available and have been widely used. Finally, since many of the problems to be considered have practical importance, the improved bounds developed will affect the heuristics and exact optimization techniques used in practice.