Consider a complete graph G=(V,E) in which each node is present with probability pi. The authors are interested in solving combinatorial optimization problems on subsets of nodes which are present with a certain probability. They introduce the idea of a priori optimization as a strategy competitive to the strategy of reoptimization, under which the combinatorial optimization problem is solved optimally for every instance. The authors consider four problems: the traveling salesman problem (TSP), the minimum spanning tree, vehicle routing, and traveling salesman facility location. They discuss the applicability of a priori optimization strategies in several areas and show that if the nodes are randomly distributed in the plane the a priori and reoptimization strategies are very close in terms of performance. The authors characterize the complexity of a priori optimization and address the question of approximating the optimal a priori solutions with polynomial time heuristics with provable worst-case guarantees. Finally, they use the TSP as an example to find practical solutions based on ideas of local optimality.
