Trichotomy for integer linear systems based on their sign patterns

DOI10.1016/J.DAM.2015.07.004zbMATH Open1339.90240OpenAlexW2119239813MaRDI QIDQ906434FDOQ906434

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

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

zbMATH Keywords

sign patterncomplexity indexHorn systeminteger linear systemTVPI system

Mathematics Subject Classification ID

Integer programming (90C10)

Cites Work

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

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)