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

DOI10.1016/J.DAM.2020.10.016OpenAlexW3111419358MaRDI QIDQ2235285FDOQ2235285

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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)