Linear programming duality and morphisms

Winfried Hochstättler; Jaroslav Nešetřil

Commentationes Mathematicae Universitatis Carolinae (1999)

  • Volume: 40, Issue: 3, page 577-592
  • ISSN: 0010-2628

Abstract

top
In this paper we investigate a 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.

How to cite

top

Hochstättler, Winfried, and Nešetřil, Jaroslav. "Linear programming duality and morphisms." Commentationes Mathematicae Universitatis Carolinae 40.3 (1999): 577-592. <http://eudml.org/doc/248395>.

@article{Hochstättler1999,
abstract = {In this paper we investigate a 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.},
author = {Hochstättler, Winfried, Nešetřil, Jaroslav},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {oriented matroids; strong maps; homomorphisms; duality; oriented matroid; strong map; homomorphism; duality},
language = {eng},
number = {3},
pages = {577-592},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Linear programming duality and morphisms},
url = {http://eudml.org/doc/248395},
volume = {40},
year = {1999},
}

TY - JOUR
AU - Hochstättler, Winfried
AU - Nešetřil, Jaroslav
TI - Linear programming duality and morphisms
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1999
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 40
IS - 3
SP - 577
EP - 592
AB - In this paper we investigate a 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.
LA - eng
KW - oriented matroids; strong maps; homomorphisms; duality; oriented matroid; strong map; homomorphism; duality
UR - http://eudml.org/doc/248395
ER -

References

top
  1. Bachem A., Kern W., Linear Programming Duality: An Introduction to Oriented Matroids, Springer, Berlin etc., 1992. Zbl0757.90050MR1230380
  2. Bacik R., Mahajan S., Interactive proof systems and polynomial algorithms, preprint. 
  3. Björner A., Las Vergnas M., Sturmfels B., White N., Ziegler G.M., Oriented Matroids, Encyclopedia of Mathematics and its Applications 46, Cambridge University Press, 1993. MR1226888
  4. Bland R.G., Dietrich B.L., An abstract duality, Discrete Math. 70 (1988), 203-208. (1988) Zbl0686.05014MR0949779
  5. Bland R.G., Las Vergnas M., Orientability of matroids, J. Combin. Theory Ser. B 24 (1978), 94-123. (1978) Zbl0374.05016MR0485461
  6. Edmonds J., Paths, trees and flowers, Canadian J. Math. 17 (1965), 449-467. (1965) Zbl0132.20903MR0177907
  7. Farkas G., Theorie der einfachen Ungleichungen, J. Reine Angew. Math. 124 (1902), 1-27. (1902) 
  8. Feder T., Vardi M.Y., Monotone Monadic SNP and Constraint Satisfaction, Proc. 25th ACM STOC 1993, pp.612-622. Zbl0914.68075
  9. Folkman J., Lawrence J., Oriented matroids, J. Combin. Theory Ser. B 25 (1978), 199-236. (1978) Zbl0325.05019MR0511992
  10. Grötschel M., Lovász L., Schrijver A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), 169-197. (1981) MR0625550
  11. Hell P., Zhu X., Homomorphisms to oriented paths, Discrete Math. 132 (1994), 107-114. (1994) Zbl0819.05030MR1297376
  12. Hell P., Nešetřil J., Zhu X., Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc. 348 (1996), 1281-1297. (1996) MR1333391
  13. Hell P., Nešetřil J., Zhu X., Complexity of tree homomorphisms, submitted. 
  14. Hochstättler W., A note on the Weak Zone Theorem, Congressus Numerantium 98 (1993), 95-103. (1993) MR1267343
  15. Hoffman A.J., Schwartz D.E., On partitions of partially ordered sets, J. Combin. Theory Ser. B 23 (1977), 3-13. (1977) MR0472547
  16. Hoffman A.J., On lattice polyhedra, Proceedings 5th Hungarian Coll. on Combinatorics, North Holland, 1978, pp.593-598. Zbl0443.05003MR0519293
  17. Komarek P., Some new good characterizations of directed graphs, Časopis Pěst. Mat. 51 (1984), 348-354. (1984) MR0774277
  18. Komarek P., Good characterizations, Thesis, Charles University, Prague, 1983. Zbl0609.05040
  19. Lovász L., Schrijver A., oral communication, . 
  20. Minty G.J., On the axiomatic foundations of the theories of directed linear graphs, electrical networks and network-programming, J. Math. and Mechanics 15 (1966), 485-520. (1966) Zbl0141.21601MR0188102
  21. Nešetřil J., Pultr A., On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math. 22 (1978), 287-300. (1978) MR0522724
  22. Nešetřil J., Theory of Graphs, SNTL, Praha, 1979. 
  23. Schrijver A., Theory of Linear and Integer Programming, Wiley-Interscience, Chichester, 1986. Zbl0970.90052MR0874114
  24. White N. (editor), Theory of Matroids, Encyclopedia of Mathematics and its Applications 26, Cambridge University Press, 1986. MR0849389

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.