×

zbMATH — the first resource for mathematics

Which nonnegative matrices are slack matrices? (English) Zbl 1283.15103
Summary: We characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack matrix. The underlying decision problem is equivalent to the polyhedral verification problem whose complexity is unknown.

MSC:
15B48 Positive matrices and their generalizations; cones of matrices
52B11 \(n\)-dimensional polytopes
65F30 Other matrix algorithms (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Björner, A., Topological methods, (Handbook of Combinatorics, (1995), Elsevier), 1819-1872 · Zbl 0851.52016
[2] Bredon, G. E., Topology and geometry, Grad. Texts in Math., vol. 139, (1993), Springer · Zbl 0791.55001
[3] Dyer, M. E., The complexity of vertex enumeration methods, Math. Oper. Res., 8, 3, 381-402, (1983) · Zbl 0531.90064
[4] Freund, R.; Orlin, J., On the complexity of four polyhedral set containment problems, Math. Program., 33, 133-145, (1985) · Zbl 0581.90060
[5] Gouveia, J.; Parrilo, P. A.; Thomas, R. R., Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 248-264, (2013) · Zbl 1291.90172
[6] Joswig, M., Software, (Goodman, Jacob E.; ORourke, Joseph, Handbook of Discrete and Computational Geometry, (2004), CRC Press), 1415-1433, Chapter 64
[7] Joswig, M.; Ziegler, G. M., Convex hulls, oracles, and homology, J. Symbolic Comput., 38, 4, 1247-1259, (2004) · Zbl 1121.52030
[8] Kaibel, V.; Pfetsch, M. E., Some algorithmic problems in polytope theory, (Algebra, Geometry, and Software Systems, (2003), Springer Berlin), 23-47 · Zbl 1027.65032
[9] Matheiss, T. H.; Rubin, D., A survey and comparison of methods for finding all vertices of convex polyhedral sets, Math. Oper. Res., 5, 2, 167-185, (1980) · Zbl 0442.90050
[10] Richter-Gebert, J., Realization spaces of polytopes, Lecture Notes in Math., vol. 1643, (1996), Springer · Zbl 0866.52009
[11] Seidel, R., Convex hull computations, (Goodman, Jacob E.; ORourke, Joseph, Handbook of Discrete and Computational Geometry, (2004), CRC Press), 495-512, Chapter 22
[12] Seymour, P. D., A note on hyperplane generation, J. Combin. Theory Ser. B, 61, 1, 88-91, (1994) · Zbl 0803.05015
[13] Steinitz, E.; Rademacher, H., Vorlesungen über die theorie der polyeder, (1934), Springer, (reprint 1976) · Zbl 0325.52001
[14] Yannakakis, M., Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci., 43, 3, 441-466, (1991) · Zbl 0748.90074
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.