Improved Mathematical Programming Techniques for Approximation Algorithms

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

• 批准号: RGPIN-2015-06496
• 负责人: Friggstad, Zachary
• 金额: $ 1.68万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=679281
• 关键词: 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难的，这意味着我们没有任何有效的算法来最优地解决这些问题，也不希望有任何有效的算法来优化解决这些问题。为了克服这一困难，我们致力于设计有效的算法来找到近最优解。*本建议的主题是设计用于NP-Hard优化问题的改进的近似算法，主要是通过设计和分析新的数学规划方法。其目标是提供新的多项式时间算法来计算其成本在最优解的某个已证明的显式界限内的解。这些算法将以数学程序为基础，这一事实也将有助于阐明理论计算科学和实用启发式之间的联系，因为线性和整数规划技术经常被用来设计在实验中表现良好但对最坏情况的性能缺乏证明的保证的算法。*我提议的研究包括将离散优化问题建模为数学程序，然后放松这些程序的一些限制，以得到可以有效求解的模型。通常，这是整数规划的线性或半定规划松弛。一旦这种松弛被解决，解就被仔细地四舍五入，以获得原始模型的可行解，同时尽可能地保持目标函数值。这已经被认为是设计近似算法的最有效的方法之一；Shmoys和Williamson最近出版的《近似算法的设计》一书中有八章专门介绍了这种方法。*特别是数学规划技术在车辆路径和资源分配问题中的应用。在车辆路径问题中，一种强大的线性规划方法最近被证明在解决多车辆问题时是有用的，我建议进一步探索这些技术来解决基本的路径问题。此外，我还将研究树中的所谓不可分流问题，它代表了我们在如何近似资源分配和布局问题方面的理解的前沿。特别是，我预计，理解一个相对较新的线性规划模型的有效性，应该会导致改进的近似或更严格的下界。