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.

Actions:

Download:	Postscript - Preprinted Version Download (215kB) | Preview
Editorial actions:	View Item (Login required)