标题： 关于列车路由的可近似性和最小最大不相交路径问题 显示英文标题

标题： On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem

摘要： 在列车径路规划中，间隔是指为了安全和鲁棒性必须在连续列车之间保持的最小距离。 我们引入了一个列车径路模型，该模型要求在列车之间保持固定的间隔，并研究了在单源单汇网络中最小化总完成时间的问题，即最后一列火车的到达时间。 对于这个问题，我们首先证明存在一个最优解，其中列车以车队的形式移动，即任何两列列车的最优路径要么相同，要么是边不相交的。 通过这一洞察，我们能够将我们的列车径路问题的近似性降低到最小最大不相交路径问题的近似性，该问题要求找到一组不相交的路径，使得集合中任何路径的最大长度尽可能小。 尽管最小最大不相交路径问题从多级瓶颈分配问题继承了一个强大的不可近似性结果，但我们表明，一种自然的贪心组合方法在系列-并行图中可以得到关于不相交路径数量的对数近似。 我们还对该方法进行了另一种分析，该分析给出了一个依赖于系列-并行图分解树在任何根叶路径上交替出现串联和并联组合频率的保证。 显示英文摘要

摘要： In train routing, the headway is the minimum distance that must be maintained between successive trains for safety and robustness. We introduce a model for train routing that requires a fixed headway to be maintained between trains, and study the problem of minimizing the makespan, i.e., the arrival time of the last train, in a single-source single-sink network. For this problem, we first show that there exists an optimal solution where trains move in convoys, that is, the optimal paths for any two trains are either the same or are arc-disjoint. Via this insight, we are able to reduce the approximability of our train routing problem to that of the min-max disjoint paths problem, which asks for a collection of disjoint paths where the maximum length of any path in the collection is as small as possible. While min-max disjoint paths inherits a strong inapproximability result on directed acyclic graphs from the multi-level bottleneck assignment problem, we show that a natural greedy composition approach yields a logarithmic approximation in the number of disjoint paths for series-parallel graphs. We also present an alternative analysis of this approach that yields a guarantee depending on how often the decomposition tree of the series-parallel graph alternates between series and parallel compositions on any root-leaf path.