Duality in Combinatorial Optimization -- Sometimes it Works, Sometimes it Won't

Hochstättler, Winfried (1997) Duality in Combinatorial Optimization -- Sometimes it Works, Sometimes it Won't.
Technical Report , 57 p.


In this thesis we comment on six papers, three from matroid theory and three from cooperative game theory. Their common theme is duality in combinatorial optimization, although it occurs in different settings. The first three articles (available as 92-109, 94-154 and 95-195 ) study polarity (or projective duality) in oriented matroids, a combinatorial model for linear programming and hyperplane arrangements. While older work on adjoints contains mainly negative results on the existence of adjoints, we provide several sufficient conditions, in particular in the rank four case. In cooperative game theory (see 93-137, 94-166 and 94-178) we study several solution concepts which are defined by polyhedral constraints. These concepts are applied to games defined by combinatorial optimization problems, such as the TSP, the MCMST and non-bipartite matching.

Download: [img] Postscript
Download (436kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-294
Depositing User: Winfried Hochstättler
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/294