Generating All Vertices of a Polyhedron is Hard

Khachiyan, Leonid; Boros, Endre; Borys, Konrad; Elbassioni, Khaled; Gurvich, Vladimir

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

Generating All Vertices of a Polyhedron is Hard

MPS-Authors

/persons/resource/persons44374

Elbassioni, Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., & Gurvich, V. (2006). Generating All Vertices of a Polyhedron is Hard. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06 (pp. 758-765). New York, USA: ACM / SIAM.

引用: https://hdl.handle.net/11858/00-001M-0000-000F-22F4-5

要旨

We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless P=NP. As a corollary, we solve in the negative two well-known generating problems from linear programming: (i) Given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. Yet, for generating maximal feasible subsystems the complexity remains open. (ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. Yet, in the case of bounded polyhedra the complexity remains open