Improved Mathematical Programming Techniques for Approximation Algorithms

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

A striking number of problems in discrete optimization are, unfortunately, computationally intractable. These problems stem from issues faced by our complex society: coordinating vehicles in a transportation network, compiling code to create efficient executable programs, determining placements of fire or ambulance stations to improve response time. More precisely, many such problems are NP-hard meaning we do not have, nor do we expect, any efficient algorithms to solve these problems optimally. To cope with this difficulty, we focus on devising efficient algorithms that find near-optimum solutions.***The subject of this proposal is designing improved approximation algorithms for NP-hard optimization problems, primarily by devising and analyzing new mathematical programming approaches. The goal is to provide new polynomial-time algorithms to compute solutions whose costs are within some proven explicit bound of the optimum solution. The fact that these algorithms will be based on mathematical programs will also help articulate the connection between theoretical computing science and practical heuristics, as linear and integer programming techniques are often used to devise algorithms that perform well experimentally yet lack proven guarantees on their worst-case performance.***My proposed research includes modelling discrete optimization problems as mathematical programs and then relaxing some constraints of these programs to get models that can be solved efficiently. Typically, this is a linear or semidefinite programming relaxation of an integer program. Once this relaxation is solved, the solutions are carefully rounded in a way that obtains a feasible solution to the original model while preserving the objective function value as much as possible. This is already known to be one of the most effective ways to design approximation algorithms; eight chapters of the recent book "The Design of Approximation Algorithms" by Shmoys and Williamson are devoted to this method.***In particular, applications of mathematical programming techniques to vehicle routing and resource allocation problems will be investigated. In vehicle routing problems, a strong linear programming approach has recently proven useful in addressing problems with multiple vehicles and I propose to further explore these techniques to address fundamental routing problems. Additionally, I will investigate the so-called unsplittable flow problem in trees which represents the frontier of our understanding in how to approximate resource allocation and packing problems. In particular, I expect that understanding the effectiveness of a relatively new linear programming model should either lead to improved approximations or tighter lower bounds.********