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. 124.
Abstract
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.
Item Type:  Collection Item 

Citations:  No citation data. 
Uncontrolled Keywords:  duality geometric combinatorial programming geometric duality 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  zpr92111 

Depositing User:  Prof. Dr. Michael Jünger 
Date Deposited:  27 Jun 2003 00:00 
Last Modified:  19 Jan 2012 11:31 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/111 