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.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Application #
9209283
Program Officer
Dana May Latch
Project Start
Project End
Budget Start
1992-06-15
Budget End
1996-05-31
Support Year
Fiscal Year
1992
Total Cost
$72,656
Indirect Cost
Name
University of Pittsburgh
Department
Type
DUNS #
City
Pittsburgh
State
PA
Country
United States
Zip Code
15213