Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints

DOI10.1016/J.DAM.2020.10.016MaRDI QIDQ2235285zbMATH OpenOpenAlexFDO

Authors Matthew Williamson, Piotr Wojciechowski, K. Subramani

Publication date 21 October 2021

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

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

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Algorithms in computer science (68Wxx) Theory of computing (68Qxx)

Recommendations

• Optimal length tree-like refutations of linear feasibility in UTVPI constraints
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• Read-once certification of linear infeasibility in UTVPI constraints
• On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
• Integer feasibility and refutations in UTVPI constraints using bit-scaling

Cites work

• scientific article; zbMATH DE number 4083375 (Why is no real title available?)
• scientific article; zbMATH DE number 1222561 (Why is no real title available?)
• scientific article; zbMATH DE number 1179974 (Why is no real title available?)
• scientific article; zbMATH DE number 1765669 (Why is no real title available?)
• scientific article; zbMATH DE number 1361489 (Why is no real title available?)
• scientific article; zbMATH DE number 2086430 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• A certifying algorithm for lattice point feasibility in a system of UTVPI constraints
• A combinatorial certifying algorithm for linear feasibility in UTVPI constraints
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• Frontiers of Combining Systems
• Grammar Analysis and Parsing by Abstract Interpretation
• Optimal length resolution refutations of difference constraint systems
• Optimal length tree-like refutations of linear feasibility in UTVPI constraints
• Optimal length tree-like resolution refutations for 2SAT formulas
• Parametric dispatching of hard real-time tasks
• Randomized algorithms for finding the shortest negative cost cycle in networks
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• The Complexity of Propositional Proofs
• The intractability of resolution
• The octagon abstract domain
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

Cited in

(1)

• An Optimal Algorithm for Computing the Integer Closure of UTVPI Constraints

This page was built for publication: Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints

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