Hochstättler, Winfried and Nesetril, Jaroslav
(1999)
Linear Programming Duality and Morphisms.
Published in:
Commentationes mathematicae Universitatis Carolinae : CMUC Vol. 40 (3).
pp. 577592.
Abstract
In this paper we investigate the class NP cap coNP (or the class of problems permitting a good characterisation) from the point of view of morphisms of oriented matroids. We prove several morphismduality theorems for oriented matroids. These generalize LPduality (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: 
Postscript
 Preprinted Version
Download (215kB)
 Preview

Export as: 
[error in script] 
Editorial actions: 
View Item (Login required) 
Item Type: 
Article

Citations: 
[error in script]
12 (Google
Scholar) 
[error in script]

Uncontrolled Keywords: 
[error in script] 
Subjects: 
05XX Combinatorics > 05Bxx Designs and configurations > 05B35 Matroids, geometric lattices
05XX Combinatorics > 05Cxx Graph theory > 05C99 None of the above, but in this section
18XX Category theory; abstract homological algebra > 18Bxx Special categories > 18B99 None of the above, but in this section
52XX Convex and discrete geometry > 52Cxx Discrete geometry > 52C40 Oriented matroids
90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C05 Linear programming
90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization
90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C46 Optimality conditions, duality

Uncontrolled Keywords: 
duality, homomorphism, oriented matroids, strong map 
Subjects: 
05XX Combinatorics > 05Bxx Designs and configurations > 05B35 Matroids, geometric lattices 05XX Combinatorics > 05Cxx Graph theory > 05C99 None of the above, but in this section 18XX Category theory; abstract homological algebra > 18Bxx Special categories > 18B99 None of the above, but in this section 52XX Convex and discrete geometry > 52Cxx Discrete geometry > 52C40 Oriented matroids 90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C05 Linear programming 90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization 90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C46 Optimality conditions, duality 
Divisions: 
Mathematical Institute 
Depositing User: 
Winfried Hochstättler

Date Deposited: 
03 Jun 2009 00:00 
Last Modified: 
19 Dec 2011 09:45 