A combinatorial certifying algorithm for linear feasibility in UTVPI constraints

DOI10.1007/s00453-016-0131-1zbMath1360.68889OpenAlexW2343984626MaRDI QIDQ527418

Piotr J. Wojciechowski, K. Subramani and Vahan Mkrtchyan

Publication date: 11 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0131-1

zbMATH Keywords

relaxationtheorem of the alternativelinear feasibilityhalf-integral solutionsUTVPI constraints

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Related Items

A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints ⋮ Reachability in choice networks ⋮ On the parallel complexity of constrained read-once refutations in UTVPI constraint systems ⋮ Integer feasibility and refutations in UTVPI constraints using bit-scaling ⋮ A faster algorithm for determining the linear feasibility of systems of BTVPI constraints ⋮ Unit read-once refutations for systems of difference constraints ⋮ A certifying algorithm for lattice point feasibility in a system of UTVPI constraints ⋮ Analyzing fractional Horn constraint systems ⋮ Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints ⋮ On integer closure in a system of unit two variable per inequality constraints ⋮ A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Certifying algorithms
• A new polynomial-time algorithm for linear programming
• The octagon abstract domain
• A combinatorial algorithm for Horn programs
• Incremental Satisfiability and Implication for UTVPI Constraints
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Parametric dispatching of hard real-time tasks
• An Improved Tight Closure Algorithm for Integer Octagonal Constraints
• Frontiers of Combining Systems
• Computer Aided Verification