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

DOI10.1016/j.dam.2020.10.016OpenAlexW3111419358MaRDI QIDQ2235285

Matthew Williamson, Piotr J. Wojciechowski, K. Subramani and Vahan Mkrtchyan

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

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

Cites Work

• A combinatorial certifying algorithm for linear feasibility in UTVPI constraints
• Optimal length tree-like refutations of linear feasibility in UTVPI constraints
• Optimal length resolution refutations of difference constraint systems
• The octagon abstract domain
• The intractability of resolution
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Randomized algorithms for finding the shortest negative cost cycle in networks
• A certifying algorithm for lattice point feasibility in a system of UTVPI constraints
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• Grammar Analysis and Parsing by Abstract Interpretation
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Parametric dispatching of hard real-time tasks
• The Complexity of Propositional Proofs
• Optimal length tree-like resolution refutations for 2SAT formulas
• Frontiers of Combining Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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