文章基本信息

标题：Robust Algorithms for TSP and Steiner Tree
本地全文：下载
作者：Arun Ganesh ; Bruce M. Maggs ; Debmalya Panigrahi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：54:1-54:18
DOI：10.4230/LIPIcs.ICALP.2020.54
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Robust optimization; Steiner tree; traveling salesman problem