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.


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: [img] Postscript - Preprinted Version
Download (215kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr95-209
Depositing User: Winfried Hochstättler
Date Deposited: 03 Jun 2009 00:00
Last Modified: 19 Dec 2011 09:45