English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-31AB-E Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-31AD-A
Genre: Conference Paper

Files

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

Locators

show

Creators

show
hide
 Creators:
Boros, Endre, Author
Elbassioni, Khaled M.1, Author           
Khachiyan, Leonid, Author
Gurvich, Vladimir, Author
Makino, Kazuhisa, Author
Affiliations:
1Algorithms 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 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.

Details

show
hide
Language(s): eng - English
 Dates: 2007-05-022001
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518229
Other: Local-ID: C1256428004B93B8-DABCE3715C07BBADC1256FB000652C42-Elbassioni2001
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Heraklion, Crete, Greece
Start-/End Date: 2001-07-08 - 2001-07-12

Legal Case

show

Project information

show

Source 1

show
hide
Title: Automata, Languages and Programming, 28th International Colloquium, ICALP 2001
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 92 - 103 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2076 Sequence Number: - Start / End Page: - Identifier: -