A complexity perspective on entailment of parameterized linear constraints

DOI10.1007/S10601-012-9127-XzbMATH Open1309.90107OpenAlexW2052028847MaRDI QIDQ487646FDOQ487646

Authors: Pavlos Eirinakis, Salvatore Ruggieri, K. Subramani, Piotr Wojciechowski

Publication date: 22 January 2015

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-012-9127-x

Recommendations

Computer Science Logic
Complexity of clausal constraints over chains
Parameterized complexity of constraint satisfaction problems
Polynomial Constraints for Sets with Cardinality Bounds
Computational complexity of linear constraints over the integers

computational complexity polynomial algorithm entailment parameterized linear constraint quantified linear implication quantified linear program

Mathematics Subject Classification ID

Linear programming (90C05) Sensitivity, stability, parametric optimization (90C31) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

QEPCAD B
Hybrid Systems: Computation and Control
Formal Methods in Computer-Aided Design
A new polynomial-time algorithm for linear programming
Solving satisfiability problems with preferences
Partial cylindrical algebraic decomposition for quantifier elimination
Title not available (Why is that?)
A self-adaptive multi-engine solver for quantified Boolean formulas
Relatively quantified constraint satisfaction
On the complexity of entailment in propositional multivalued logics
Title not available (Why is that?)
On the combinatorial and algebraic complexity of quantifier elimination
On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
The complexity of linear problems in fields
Real quantifier elimination is doubly exponential
Polyhedral functions and multiparametric linear programming
Geometric algorithm for multiparametric linear programming
Title not available (Why is that?)
Real addition and the polynomial hierarchy
A new approach for automatic theorem proving in real geometry
On a decision procedure for quantified linear programs
Title not available (Why is that?)
Efficient solving of quantified inequality constraints over the real numbers
Consistency, redundancy, and implied equalities in linear systems
A geometric view of parametric linear programming
Computational complexity of parametric linear programming
Efficient handling of universally quantified inequalities
Value ordering for quantified CSPs
A solver for QBFs in negation normal form
On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls
Solution of parametrized linear inequalities by Fourier elimination and its applications
An analysis of totally clairvoyant scheduling
Generalizing the template polyhedral domain
Typing Linear Constraints for Moding CLP( ${\cal R}$ ) Programs
Title not available (Why is that?)
Title not available (Why is that?)
Theory and Applications of Satisfiability Testing
Correct Hardware Design and Verification Methods
On Parametric Linear Programming
Tractable fragments of Presburger arithmetic

Cited In (4)

An algorithm-independent measure of progress for linear constraint propagation
On quantified linear implications
Multistage robust discrete optimization via quantified integer programming
Title not available (Why is that?)

Uses Software

QEPCAD
QuBE++
REDLOG
RSOLVER
MPT
PolyLib

This page was built for publication: A complexity perspective on entailment of parameterized linear constraints

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