论文标题
在具有位置不确定性的图表中近似优化问题
Approximating optimization problems in graphs with locational uncertainty
论文作者
论文摘要
许多组合优化问题可以提出，以搜索满足某些特性并最大程度减少总重量的子图。我们在这里假设顶点对应于度量空间中的点，并且可以在给定的不确定性集中占据任何位置。然后，要最小化的成本函数是在不确定性集中顶点最差位置的距离之和。我们提出了两种类型的多项式时间近似算法。第一个依赖于解决问题的确定性对应物，其中不确定的距离被最大成对距离替换。我们详细研究了所得近似值，这取决于可行的亚图的结构以及度量空间是否为托勒密。第二种算法是针对$ S-T $路径的特殊情况的完全多项式时间近似方案。
Many combinatorial optimization problems can be formulated as the search for a subgraph that satisfies certain properties and minimizes the total weight. We assume here that the vertices correspond to points in a metric space and can take any position in given uncertainty sets. Then, the cost function to be minimized is the sum of the distances for the worst positions of the vertices in their uncertainty sets. We propose two types of polynomial-time approximation algorithms. The first one relies on solving a deterministic counterpart of the problem where the uncertain distances are replaced with maximum pairwise distances. We study in details the resulting approximation ratio, which depends on the structure of the feasible subgraphs and whether the metric space is Ptolemaic or not. The second algorithm is a fully-polynomial time approximation scheme for the special case of $s-t$ paths.
