×

zbMATH — the first resource for mathematics

The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable. (English) Zbl 0912.68206
Summary: We discuss the computational complexity of the following enumeration problem: given a rational convex polyhedron \(P\) defined by a system of linear inequalities, out put each vertex of \(P\). It is still an open question whether there exists an algorithm for listing all vertices in running time polynomial in the input size and the output size. Informally speaking, a linear running time in the output size leads to the notion of \({\mathcal P}\)-enumerability introduced by L. G. Valiant [The complexity of enumeration and reliability problems, SIAM J. Comput. 8, No. 3, 410-421 (1979)]. The concept of strong \({\mathcal P}\)-enumerability additionally requires an output independent space complexity of the respective algorithm. We give such an algorithm for polytopes all of whose vertices are among the vertices of a polytope combinatorially equivalent to the hypercube. As a very important special case, this class of polytopes contains all 0/1-polytopes, Our implementation based on the commercial LP solver \(\text{CPLEX}^1\) is superior to general vertex enumeration algorithms. We give an example how simplifications of our algorithm lead to efficient enumeration of combinatorial objects.

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja, R.K; Magnanti, T.L; Orlin, J.B, Network flows — theory, algorithms and applications, (1993), Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2] Avis, D; Fukuda, K, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete comput. geom., 8, 295-313, (1992) · Zbl 0752.68082
[3] Bremner, D; Fukuda, K; Marzetta, A, Primal-dual methods for vertex and facet enumeration, () · Zbl 0910.68217
[4] Fukuda, K, Note on new complexity classes \(ENP\), \(EP\) and \(CEP\), (June 1996), Paper electronically available at URL
[5] Fukuda, K; Liebling, T.M; Margot, F, Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron, Computational geometry, 8, 1-12, (1997) · Zbl 1133.68462
[6] Fukuda, K; Matsui, T, Finding all the perfect matchings in bipartite graphs, Appl. math. lett., 7, 15-18, (1994) · Zbl 0792.68129
[7] Lübbecke, M.E, Algorithmen zur enumeration aller ecken und facetten konvexer polyeder, ()
[8] Provan, J.S, Efficient enumeration of the vertices of polyhedra associated with network LP’s, Math. programming, 63, 47-64, (1994) · Zbl 0792.90045
[9] Schrijver, A, Theory of linear and integer programming, (1986), Wiley Chichester · Zbl 0665.90063
[10] Valiant, L.G, The complexity of enumeration and reliability problems, SIAM J. comput., 8, 3, 410-421, (1979) · Zbl 0419.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.