English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities

Boros, E., Elbassioni, K. M., Khachiyan, L., Gurvich, V., & Makino, K. (2002). Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities. SIAM Journal on Computing, 31, 20.

Item is

Files

show Files
hide Files
:
38876.ps (Any fulltext), 545KB
 
File Permalink:
-
Name:
38876.ps
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/postscript
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Boros, Endre1, Author
Elbassioni, Khaled M.2, Author           
Khachiyan, Leonid1, Author
Gurvich, Vladimir1, Author
Makino, Kazuhisa1, Author
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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 r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the number of minimal integer solutions to the system. This bound is accurate up to a polylog(r) 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 all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time.

Details

show
hide
Language(s): eng - English
 Dates: 2002
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: Elbassioni2002a
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: SIAM Journal on Computing
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Philadelphia, PA : SIAM
Pages: - Volume / Issue: 31 Sequence Number: - Start / End Page: 20 Identifier: -