论文标题
TSP和Steiner树的强大算法
Robust Algorithms for TSP and Steiner Tree
论文作者
论文摘要
强大的优化是操作研究中广泛研究的领域，在该领域中，该算法将作为输入范围的一个值，并输出单个解决方案，该解决方案在整个范围内表现良好。具体而言，一种强大的算法旨在最大程度地减少遗憾，这定义为解决方案成本与事后见解后最佳解决方案之间的最大差异。对于P中的图形问题，例如最短路径和最小跨越树，已知可靠的多项式时间算法在遗憾的是获得恒定的近似值。在本文中，我们研究了强大的算法，以最大程度地减少NP-HARD图优化问题的遗憾，并为经典的旅行推销员和Steiner树问题提供遗憾的不断近似。
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solution's cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.
