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.