Premium
An algorithmic proof of the polyhedral decomposition theorem
Author(s) -
Akgül Mustafa
Publication year - 1988
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(198810)35:5<463::aid-nav3220350510>3.0.co;2-5
Subject(s) - simplex , mathematics , polyhedron , extreme point , combinatorics , regular polygon , bounded function , projection (relational algebra) , dimension (graph theory) , polynomial , simplex algorithm , convex polytope , discrete mathematics , extension (predicate logic) , ellipsoid method , linear programming , convex analysis , convex optimization , algorithm , computer science , mathematical analysis , geometry , programming language
It is well‐known that any point in a convex polyhedron P can be written as the sum of a convex combination of extreme points of P and a non‐negative linear combination of extreme rays of P . Grötschel, Lovász, and Schrijver gave a polynomial algorithm based on the ellipsoidal method to find such a representation for any x in P when P is bounded. Here we show that their algorithm can be modified and implemented in polynomial time using the projection method or a simplex‐type algorithm : in n (2 n + 1) simplex pivots, where n is the dimension of x . Extension to the unbounded case is immediate.