A complexity perspective on entailment of parameterized linear constraints

DOI10.1007/S10601-012-9127-XMaRDI QIDQ487646zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(4)

Multistage robust discrete optimization via quantified integer programming
scientific article; zbMATH DE number 1692939 (Why is no real title available?)
An algorithm-independent measure of progress for linear constraint propagation
On quantified linear implications

Describes a project that uses

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)