van Ee Martijn, Sitters René
1Vrije Universiteit Amsterdam, De Boelelaan 1105, 1081 HV Amsterdam, Netherlands.
2Centrum voor Wiskunde en Informatica (CWI), Science Park 123, 1098 XG Amsterdam, Netherlands.
Algorithmica. 2018;80(10):2818-2833. doi: 10.1007/s00453-017-0351-z. Epub 2017 Jul 28.
The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem, the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we study the uniform model, where a vertex is in the active set with probability independently of the other vertices, and give the first constant-factor approximation for a priori TRP.
先验优化领域是随机组合优化中一个有趣的子领域，非常适合路由问题。在这种情况下，活动集（即必须访问的顶点）上存在概率分布。对于固定的巡回路线，通过限制活动集上的解来获得活动集上的解。在经过充分研究的先验旅行商问题中，目标是找到一条使期望长度最小的巡回路线。在先验旅行修理工问题（TRP）中，目标是找到一条使期望延迟总和最小的巡回路线。在本文中，我们研究均匀模型，其中一个顶点以概率独立于其他顶点处于活动集中，并给出了先验TRP的首个常数因子近似解。
