Geometric Duality and Combinatorial Optimization

Jünger, Michael and Pulleyblank, William R. (1993) Geometric Duality and Combinatorial Optimization.
Published in: Überblicke Mathematik (Jahrbuch) 1993. Vieweg 1993, pp. 1-24.


Many combinatorial optimization problems have natural geometric versions, that is, versions in which the objects are points or lines in Euclidean space and the cost function is given by a planar metric. For example, a Euclidean Traveling Salesman Problem is specified by giving n points in the plane, and then requiring the construction of a tour with minimum Euclidean (L2) length passing through these points. A problem encountered in VLSI design is that of constructing minimum weight Steiner trees on a set of n points in the plane, for which the edge lengths are given by the Manhattan, or L1, metric. For many such problems there are natural ''dual'' problems. These are geometric problems, usually involving optimally packing some shape in the plane, with the property that any feasible solution to the dual problem provides a bound on the optimum solution to the original problem. Moreover, in some cases, the ''best'' such bound is tight; its value equals that of the optimum solution. We describe several such optimization problems and their geometric duals. We also discuss the solvability of these problems.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr92-111
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 19 Jan 2012 11:31