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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (215kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] 12 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 05-XX Combinatorics > 05Bxx Designs and configurations > 05B35 Matroids, geometric lattices

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C99 None of the above, but in this section

  • 18-XX Category theory; abstract homological algebra > 18Bxx Special categories > 18B99 None of the above, but in this section

  • 52-XX Convex and discrete geometry > 52Cxx Discrete geometry > 52C40 Oriented matroids

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C05 Linear programming

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C46 Optimality conditions, duality

  • Uncontrolled Keywords: duality, homomorphism, oriented matroids, strong map
    Subjects: 05-XX Combinatorics > 05Bxx Designs and configurations > 05B35 Matroids, geometric lattices
    05-XX Combinatorics > 05Cxx Graph theory > 05C99 None of the above, but in this section
    18-XX Category theory; abstract homological algebra > 18Bxx Special categories > 18B99 None of the above, but in this section
    52-XX Convex and discrete geometry > 52Cxx Discrete geometry > 52C40 Oriented matroids
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C05 Linear programming
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization
    90-XX 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
    Deposit Information:
    ZAIK Number: [error in script]
    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