Linear Programming Duality and Morphisms
Hochstättler, Winfried and Nesetril, Jaroslav
(1999)
Linear Programming Duality and Morphisms.
Published in:
Commentationes mathematicae Universitatis Carolinae : CMUC Vol. 40 (3).
pp. 577-592.
Abstract
In this paper we investigate the class NP cap co-NP (or the class of problems permitting a good characterisation) from the point of view of morphisms of oriented matroids. We prove several morphism-duality theorems for oriented matroids. These generalize LP-duality (in form of Farkas' Lemma) and Minty's Painting Lemma. Moreover, we characterize all morphism duality theorems, thus proving the essential unicity of Farkas' Lemma. This research helped to isolate perhaps the most natural definition of strong maps for oriented matroids.
Download: |
Download (215kB) | Preview |
---|---|
Editorial actions: | ![]() |
ZAIK Number: | zpr95-209 |
---|---|
Depositing User: | Winfried Hochstättler |
Date Deposited: | 03 Jun 2009 00:00 |
Last Modified: | 19 Dec 2011 09:45 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/209 |