The UPS Problem consists of the following: given a vertex set V, vertex probabilities (p{sub}v){sub}v∈V, and distances l：V{sup}2→R{sup}+ that satisfy the triangle inequality, find a Hamilton cycle such that the expected length of the shortcut that skips each vertex v with probability 1-p{sub}v (independently of the others) is minimum. This problem appears in the following context. Drivers of delivery companies visit customers daily to deliver packages. For the company, the shorter the distance traversed, the better. For a driver, routes that change dramatically from one day to the other are inconvenient; it is better if one only has to shortcut a fixed route. The UPS problem, whose objective captures these two points of view, is at least as hard to approximate as the Metric TSP. Given that one of the vertices has probability one, we show that the performance ratio of a TSP tour for the UPS problem is 1/p{sub}(min), where p{sub}(min) := min{sub}v∈Vp{sub}v. We also show that this is tight. Consequently, Christofides' algorithm for the TSP has a performance ratio of 3/(2p{sub}(min)) for the UPS problem and the approximation threshold for the UPS problem is at most 1/p{sub}(min) times the one for the TSP.
展开▼
机译：UPS问题包括以下内容：给定顶点集V，顶点概率（p {sub} v）{sub}v∈v，距离三角形不等式的距离l：v {sup} 2→r {sup} + ，找到汉密尔顿循环，使得使用概率1-p {sub} v（独立于其他）跳过每个顶点v的快捷方式的预期长度最小。此问题显示在以下上下文中。送货公司的司机每天访问客户送餐。对于公司来说，距离越短，越越好。对于驾驶员，从一天到另一天急剧变化的路线是不方便的;如果只有一个固定的路线只有捷径才能更好。 UPS问题，其客观捕获这两个观点，至少难以近似为度量TSP。考虑到其中一个顶点具有概率，我们表明，UPS问题的TSP巡回赛的性能比为1 / p {sub}（min），其中p {sub}（min）：= min {sub} v ∈vp{sub} v。我们还表明这是紧张的。因此，Christofides为TSP的算法具有UPS问题的3 /（2P {sub}（min））的性能比，UPS问题的近似阈值最多为1 / p {sub}（min）次数一个用于TSP。
展开▼
