polyhedral verification problem

Which Nonnegative Matrices Are Slack Matrices?

  • João Gouveia
  • Volker Kaibel
  • R. Grappe
  • K. Pashkovich
  • Richard Z. Robinson
  • Rekha R. Thomas
    • Categories Linear Programming, Polyhedra Tags , , ,

    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 verifi cation problem whose complexity is unknown. CitationApril 2013ArticleDownload View PDF