Paper Info
Title
A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes
Abstract
We consider the problem of developing an efficient algorithm for enumerating the extreme points of a convex polytope specified by linear constraints. Murty and Chung (Math Program 70:27–45, 1995) introduced the concept of a segment of a polytope, and used it to develop some steps for carrying out the enumeration efficiently until the convex hull of the set of known extreme points becomes a segment. That effort stops with a segment, other steps outlined in Murty and Chung (Math Program 70:27–45, 1995) for carrying out the enumeration after reaching a segment, or for checking whether the segment is equal to the original polytope, do not constitute an efficient algorithm. Here we describe the central problem in carrying out the enumeration efficiently after reaching a segment. We then discuss two procedures for enumerating extreme points, the mukkadvayam checking procedure, and the nearest point procedure. We divide polytopes into two classes: Class 1 polytopes have at least one extreme point satisfying the property that there is a hyperplane H through that extreme point such that every facet of the polytope incident at that extreme point has relative interior point intersections with both sides of H; Class 2 polytopes have the property that every hyperplane through any extreme point has at least one facet incident at that extreme point completely contained on one of its sides. We then prove that the procedures developed solve the problem efficiently when the polytope belongs to Class 2.
Year
DOI
Venue
2009
10.1007/s11590-008-0103-8
Optimization Letters
Keywords
DocType
Volume
convex polytopes and their dual polytopes · fcfs facetal constraint functions · enumeration of extreme points · adjacency · segments · mukkas · mukkadvayams · central problem and strategy for its solution · nearest points · linear and convex quadratic programs,satisfiability,convex polytope,interior point,convex hull,extreme point
Journal
3
Issue
ISSN
Citations 
2
1862-4480
3
PageRank 
References 
Authors
0.46
6
1
Name
Order
Citations
PageRank
Katta G. Murty160295.15