Finding the incident edges to a degenerate vertex of a polyhedron is a non-trivial problem. So pivoting methods generally involve a perturbation argument to overcome the degeneracy problem. But the perturbation entails a bursting of each degenerate vertex into a cluster of nondegenerate vertices. The aim of this paper is to give some bounds on the number of these perturbed vertices.
Publié le : 1993-07-04
Classification:
Convex polytopes,
degeneracy,
linear programming,
simplex method,
[MATH]Mathematics [math]
@article{hal-00110668,
author = {Armand, Paul},
title = {Bounds on the number of vertices of perturbed polyhedra},
journal = {HAL},
volume = {1993},
number = {0},
year = {1993},
language = {en},
url = {http://dml.mathdoc.fr/item/hal-00110668}
}
Armand, Paul. Bounds on the number of vertices of perturbed polyhedra. HAL, Tome 1993 (1993) no. 0, . http://gdmltest.u-ga.fr/item/hal-00110668/