# 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.

Download: |
Postscript
- Preprinted Version
Download (215kB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

ZAIK Number: | zpr95-209 |
---|---|

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 |