Geodesic
On the Extreme Rays of the Metric Cone
Canadian journal of mathematics, Tome 32 (1980) no. 1, pp. 126-144

Voir la notice de l'article provenant de la source Cambridge University Press

A classical result in the theory of convex polyhedra is that every bounded polyhedral convex set can be expressed either as the intersection of half-spaces or as a convex combination of extreme points. It is becoming increasingly apparent that a full understanding of a class of convex polyhedra requires the knowledge of both of these characterizations. Perhaps the earliest and neatest example of this is the class of doubly stochastic matrices. This polyhedron can be defined by the system of equations Birkhoff [2] and Von Neuman have shown that the extreme points of this bounded polyhedron are just the n × n permutation matrices. The importance of this result for mathematical programming is that it tells us that the maximum of any linear form over P will occur for a permutation matrix X. 
Avis, David. On the Extreme Rays of the Metric Cone. Canadian journal of mathematics, Tome 32 (1980) no. 1, pp. 126-144. doi: 10.4153/CJM-1980-010-0
@article{10_4153_CJM_1980_010_0,
     author = {Avis, David},
     title = {On the {Extreme} {Rays} of the {Metric} {Cone}},
     journal = {Canadian journal of mathematics},
     pages = {126--144},
     year = {1980},
     volume = {32},
     number = {1},
     doi = {10.4153/CJM-1980-010-0},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1980-010-0/}
}
TY  - JOUR
AU  - Avis, David
TI  - On the Extreme Rays of the Metric Cone
JO  - Canadian journal of mathematics
PY  - 1980
SP  - 126
EP  - 144
VL  - 32
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1980-010-0/
DO  - 10.4153/CJM-1980-010-0
ID  - 10_4153_CJM_1980_010_0
ER  - 
%0 Journal Article
%A Avis, David
%T On the Extreme Rays of the Metric Cone
%J Canadian journal of mathematics
%D 1980
%P 126-144
%V 32
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1980-010-0/
%R 10.4153/CJM-1980-010-0
%F 10_4153_CJM_1980_010_0

[1] 1. Avis, D., On the Hamming cone, Technical Report 77-5 (1977), Department of Operations Research, Stanford University. Google Scholar

[2] 2. Birkhoff, G., Très observationes sobre et linear algebra, Rev. Univ. Nac. Tucuman A5 (1946), 147–158. Google Scholar

[3] 3. Chvätal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Mathematic. 4 (1973), 305–337. Google Scholar

[4] 4. Edmonds, J., Maximum matching and a polyhedron with integral vertices, J. Res. Nat. Bur. Standards B69 (1965), 125–130. Google Scholar

[5] 5. Erdos, P. and Spencer, J., Probabilistic methods in combinatorics (Academic Press, New York, 1974). Google Scholar

[6] 6. Harary, F., Graph theory (Addison-Wesley, Reading, Mass., 1969). Google Scholar

[7] 7. Stoer, J. and Witzgall, C., Convexity and optimization infinite dimensions (Springer-Verlag, Berlin, 1970). Google Scholar

[8] 8. Veinott, A. F. Jr., Extreme points of Leonlief substitution systems, Linear Algebra and Application. 1 (1968), 181–194. Google Scholar

[9] 9. Yao, A. and Rivest, R., On the polyhedral decision problem, manuscript, Computer Science Department, Stanford University (1977). Google Scholar

[10] 10. Graham, R., Yao, A. and Yao, F., Information bounds are weak in the shortest distance problem, to appear in J. ACM. Google Scholar

Cité par Sources :