Which Nonnegative Matrices Are Slack Matrices?
Abstract: In this paper 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.
Keywords: slack matrices, polytopes, extended formulations, polyhedral verification problem
Category 1: Combinatorial Optimization (Polyhedra )
Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )
Citation: April 2013
Entry Submitted: 03/31/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|