A combinatorial certifying algorithm for linear feasibility in UTVPI constraints

DOI10.1007/S00453-016-0131-1MaRDI QIDQ527418zbMATH OpenOpenAlexFDO

Authors K. Subramani, Piotr Wojciechowski

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

half-integral solutionslinear feasibilityrelaxationtheorem of the alternativeUTVPI constraints

Mathematics Subject Classification ID

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

Recommendations

• A certifying algorithm for lattice point feasibility in a system of UTVPI constraints
• Integer feasibility and refutations in UTVPI constraints using bit-scaling
• A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• Frontiers of Combining Systems

Cites work

• A combinatorial algorithm for Horn programs
• A new polynomial-time algorithm for linear programming
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• An Improved Tight Closure Algorithm for Integer Octagonal Constraints
• Certifying algorithms
• Computer Aided Verification
• Frontiers of Combining Systems
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Incremental satisfiability and implication for UTVPI constraints
• Introduction to algorithms
• Parametric dispatching of hard real-time tasks
• The octagon abstract domain

Cited in

(23)

• A certifying algorithm for lattice point feasibility in a system of UTVPI constraints
• On integer closure in a system of unit two variable per inequality constraints
• Analyzing fractional Horn constraint systems
• Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• Integer feasibility and refutations in UTVPI constraints using bit-scaling
• A Graphical Theorem of the Alternative for UTVPI Constraints
• An Optimal Algorithm for Computing the Integer Closure of UTVPI Constraints
• A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints
• Frontiers of Combining Systems
• Reachability in choice networks
• On the parallel complexity of constrained read-once refutations in UTVPI constraint systems
• A faster algorithm for determining the linear feasibility of systems of BTVPI constraints
• Unit read-once refutations for systems of difference constraints
• Farkas Bounds on Horn Constraint Systems
• Parameterized and exact-exponential algorithms for the read-once integer refutation problem in UTVPI constraints
• Constrained read-once refutations in UTVPI constraint systems: a parallel perspective
• On the computational and approximation complexities of selected unit refutations in UTVPI constraint systems
• Finding short tree-like unit refutations in UTVPI constraint systems
• A combinatorial certifying algorithm for linear programming problems with gainfree Leontief substitution systems
• Dag-like unit refutations in UTVPI constraint systems
• A combinatorial certifying algorithm for linear programming problems with gainfree Leontief substitution systems
• Optimal length tree-like refutations of linear feasibility in UTVPI constraints

This page was built for publication: A combinatorial certifying algorithm for linear feasibility in UTVPI constraints

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