A combinatorial algorithm for Horn programs

DOI10.1016/j.disopt.2012.11.001zbMath1284.90038OpenAlexW1972648192MaRDI QIDQ2445839

R. Chandrasekaran, K. Subramani and Vahan Mkrtchyan

Publication date: 15 April 2014

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2012.11.001

zbMATH Keywords

linear programminginteger programminglifting algorithmlattice pointHorn constraints

Mathematics Subject Classification ID

Integer programming (90C10) Nonnumerical algorithms (68W05) Linear programming (90C05)

Related Items (11)

Exact and parameterized algorithms for read-once refutations in Horn constraint systems ⋮ On a generalization of Horn constraint systems ⋮ Analyzing read-once cutting plane proofs in Horn systems ⋮ A faster algorithm for determining the linear feasibility of systems of BTVPI constraints ⋮ Unit read-once refutations for systems of difference constraints ⋮ Analyzing fractional Horn constraint systems ⋮ Tree-like unit refutations in Horn constraint systems ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ A combinatorial certifying algorithm for linear feasibility in UTVPI constraints ⋮ On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems ⋮ On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations

Uses Software

• Yices

Cites Work

• The octagon abstract domain
• Small solutions of linear diophantine equations
• Representation of general and polyhedral subsemilattices and sublattices of product spaces
• Symmetric space-bounded computation
• A rounding algorithm for integer programs
• A heuristic improvement of the Bellman-Ford algorithm
• A zero-space algorithm for negative cost cycle detection in networks
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Two Variables per Linear Inequality as an Abstract Domain
• A Combinatorial Algorithm for Horn Programs
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
• Automated Reasoning
• Theoretical Computer Science
• Computability and complexity theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A combinatorial algorithm for Horn programs