Trichotomy for integer linear systems based on their sign patterns

DOI10.1016/J.DAM.2015.07.004MaRDI QIDQ906434zbMATH OpenOpenAlexFDO

Authors Kei Kimura, Kazuhisa Makino

Publication date 21 January 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.07.004

zbMATH Keywords

sign patterncomplexity indexHorn systeminteger linear systemTVPI system

Mathematics Subject Classification ID

Integer programming (90C10)

Recommendations

• Trichotomy for integer linear systems based on their sign patterns
• Solving linear programs from sign patterns
• A fast algorithm for unbounded monotone integer linear systems with two variables per inequality via graph decomposition

Cites work

• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 3880440 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 825098 (Why is no real title available?)
• scientific article; zbMATH DE number 3330532 (Why is no real title available?)
• 50 Years of Integer Programming 1958-2008
• A Complexity Index for Satisfiability Problems
• A combinatorial algorithm for Horn programs
• A new algorithm for linear and integer feasibility in Horn constraints
• An Improved Tight Closure Algorithm for Integer Octagonal Constraints
• Efficient algorithms for integer programs with two variables per constraint.
• Frontiers of Combining Systems
• Incremental satisfiability and implication for UTVPI constraints
• Integer Programming with a Fixed Number of Variables
• On a routing problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the complexity of integer programming
• Polynomial-time inference of all valid implications for Horn and related formulae
• Recognition of q-Horn formulae in linear time
• Renaming a Set of Clauses as a Horn Set
• Scaling Algorithms for the Shortest Paths Problem
• Sign-solvable linear complementarity problems
• Simplicial pivoting algorithms for a tractable class of integer programs
• Solving linear programs from sign patterns
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Trichotomy for integer linear systems based on their sign patterns
• Unit Refutations and Horn Sets

Cited in

(3)

• On connectedness of solutions to integer linear systems
• On \((h,k, \mu, \nu)\)-trichotomy of discrete linear systems
• Trichotomy for integer linear systems based on their sign patterns

This page was built for publication: Trichotomy for integer linear systems based on their sign patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906434)