Farkas' Lemma and Morphism Duality

Hochstättler, Winfried and Nesetril, Jaroslav (1996) Farkas' Lemma and Morphism Duality.
Technical Report , 12 p.


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.

Download: [img] Postscript
Download (169kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-251
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/251