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.
翻译:许多组合优化问题可以形成为寻找满足某些特性并最大限度地减少总重量的子集的问题。 我们在此假设, 脊椎与计量空间的点相对应, 并且可以在给定的不确定性组中占据任何位置。 然后, 要最小化的成本函数是其不确定性组中脊椎最差位置的距离总和。 我们建议了两种多球- 时间近似算法。 第一项取决于解决不确定距离被最大对称距离取代的问题的决定性对应方。 我们研究由此产生的近似比率, 这取决于可行的子集的结构以及衡量空间是否为Ptolemaic 。 第二种算法是美元- t$ 路径特例的全极极时近似方法 。