On Generating All Minimal Integer Solutions for a Monotone System of Linear 
Inequalities

Boros, Endre; Elbassioni, Khaled M.; Khachiyan, Leonid; Gurvich, Vladimir; Makino, Kazuhisa

On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities

Boros, E., Elbassioni, K. M., Khachiyan, L., Gurvich, V., & Makino, K. (2001). On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities. In Automata, Languages and Programming, 28th International Colloquium, ICALP 2001 (pp. 92-103). Berlin, Germany: Springer.

Item is 公開

表示: 全項目非表示: 全項目

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-31AB-E 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-31AD-A

資料種別: 会議論文

ファイル

表示: ファイル

非表示: ファイル

:

icalp01.pdf (全文テキスト（全般）), 185KB

ファイルのパーマリンク:
-

ファイル名:
icalp01.pdf

説明:
-

OA-Status:

閲覧制限:
非公開

MIMEタイプ / チェックサム:
application/pdf

技術的なメタデータ:

著作権日付:
-

著作権情報:
-

CCライセンス:
-

作成者

表示:

非表示:

作成者:
Boros, Endre, 著者
Elbassioni, Khaled M.¹, 著者
Khachiyan, Leonid, 著者
Gurvich, Vladimir, 著者
Makino, Kazuhisa, 著者

所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

内容説明

表示:

非表示:

キーワード: -

要旨: We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that for any monotone system of linear inequalities in variables, the number of maximal infeasible integer vectors is at most times the number of minimal integer solutions to the system. This bound is accurate up to a factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating minimal integer solutions of a monotone system of linear inequalities can be done in quasi-polynomial time.

資料詳細

表示:

非表示:

言語: eng - English

日付: 修正: 2007-05-02出版: 2001

出版の状態: 出版

ページ: -

出版情報: -

目次: -

査読: -

識別子（DOI, ISBNなど）: eDoc: 518229
その他: Local-ID: C1256428004B93B8-DABCE3715C07BBADC1256FB000652C42-Elbassioni2001

学位: -

訴訟

表示:

Project information

表示:

出版物 1

表示:

非表示:

出版物名: Automata, Languages and Programming, 28th International Colloquium, ICALP 2001

種別: 会議論文集

著者・編者:

所属:

出版社, 出版地: Berlin, Germany : Springer

ページ: - 巻号: - 通巻号: - 開始・終了ページ: 92 - 103 識別子（ISBN, ISSN, DOIなど）: -

出版物 2

表示:

非表示:

出版物名: Lecture Notes in Computer Science

種別: 連載記事

著者・編者:

所属:

出版社, 出版地: -

ページ: - 巻号: 2076 通巻号: - 開始・終了ページ: - 識別子（ISBN, ISSN, DOIなど）: -

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物 1

出版物 2