Online Network Optimization

这项工作将调查自然的在线版本的经典 网络优化问题：最小生成树问题， 最短路径问题，最小费用最大流问题，加权 匹配问题和旅行推销员问题。 在这些 在线算法必须开始构造一个分部 解决方案之前，所有的底层网络变得已知。 因此，我们认为， 在线算法通常不可能知道 一个特定的局部解将扩展到一个最优的全局解， 溶液 这些问题的特点是不切实际， 或者甚至不可能，在进一步 关于网络的信息变得已知。 在线算法 因此，目标是迭代地构造接近于 最优的，而不需要从一个部分解决方案到 下一个.

This work will investigate natural online versions of the classical network optimization problems: the minimal spanning tree problem, the shortest path problem, the min-cost max-flow problem, the weighted matching problem, and the traveling salesman problem. In these problems an online algorithm must begin constructing a partial solution before all of the underlying network becomes known. Hence, it is generally not possible for the online algorithm to know whether a particular partial solution will extend to an optimal global solution. The hallmark of these problems is that it is impractical, or even impossible, to restructure the partial solution when further information about the network becomes known. The online algorithm's goal is thus to iteratively construct a solution that is close to optimal without significant restructuring from one partial solution to the next.