Improved Mathematical Programming Techniques for Approximation Algorithms

改进近似算法的数学编程技术

• 批准号: RGPIN-2015-06496
• 负责人: Friggstad, Zachary
• 金额: $ 1.68万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=651200
• 关键词: Improved; Mathematical; Programming; Techniques; Approximation

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.********

不幸的是，在离散优化中有大量的问题在计算上是棘手的。这些问题源于我们复杂社会所面临的问题：在运输网络中协调车辆，编译代码以创建有效的可执行程序，确定放置或救护车站的位置以改善响应时间。更确切地说，许多这样的问题都是NP顽强的，这意味着我们没有，也没有期望任何有效算法可以最佳地解决这些问题。为了应对这一难度，我们专注于设计有效的算法，这些算法找到了接近最佳的解决方案。目标是提供新的多项式时间算法来计算其成本在某些最佳解决方案的明确限制之内的解决方案。 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有效解决。通常，这是整数程序的线性或半决赛编程放松。一旦解决了这种放松，解决方案就会以一种为原始模型获得可行的解决方案的方式仔细绕组，同时尽可能地保留目标函数值。这已经是设计近似算法的最有效方法之一。 Shmoys和Williamson的最新著作《近似算法的设计》的八章专门用于此方法。在车辆路线问题中，最近已证明一种强大的线性编程方法可用于解决多个车辆的问题，我建议进一步探索这些技术，以解决基本的路由问题。此外，我将调查树木中所谓的无法确定的流动问题，这代表了我们在如何近似资源分配和包装问题的理解的前沿。特别是，我希望了解相对较新的线性编程模型的有效性应导致改善近似值或更紧密的下限。**********