Author: Maria Minkoff

Publisher:

Published: 2003

Total Pages: 90

ISBN-13:

(Cont.) We model this problem as an extension of the well-studied Prize-Collecting Traveling Salesman problem, and develop a constant factor approximation algorithm for it, solving an open question along the way. Next we examine several classical combinatorial optimization problems such as bin-packing, vertex cover, and shortest path in the context of a "preplanning" framework, in which one can "plan ahead" based on limited information about the problem input, or "wait and see" until the entire input becomes known, albeit incurring additional expense. We study this time-information tradeoff, and show how to approximately optimize the choice of what to purchase in advance and what to defer. The last problem studied, called maybecast is concerned with designing a routing network under a probabilistic distribution of clients using locally available information. This problem can be modeled as a stochastic version of the Steiner tree problem. However probabilistic objective function turns it into an instance of a challenging optimization problem with concave costs.