A complexity perspective on entailment of parameterized linear constraints
From MaRDI portal
Publication:487646
DOI10.1007/s10601-012-9127-xzbMath1309.90107OpenAlexW2052028847MaRDI QIDQ487646
Salvatore Ruggieri, Pavlos Eirinakis, K. Subramani and Vahan Mkrtchyan, Piotr J. 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 complexitypolynomial algorithmentailmentparameterized linear constraintquantified linear implicationquantified linear program
Abstract computational complexity for mathematical programming problems (90C60) Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05)
Related Items
Multistage robust discrete optimization via quantified integer programming, On quantified linear implications
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Geometric algorithm for multiparametric linear programming
- Solving satisfiability problems with preferences
- A new polynomial-time algorithm for linear programming
- Tractable fragments of Presburger arithmetic
- A self-adaptive multi-engine solver for quantified Boolean formulas
- Value ordering for quantified CSPs
- Efficient handling of universally quantified inequalities
- Relatively quantified constraint satisfaction
- 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
- Real addition and the polynomial hierarchy
- Polyhedral functions and multiparametric linear programming
- The complexity of linear problems in fields
- Real quantifier elimination is doubly exponential
- Solution of parametrized linear inequalities by Fourier elimination and its applications
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Partial cylindrical algebraic decomposition for quantifier elimination
- A geometric view of parametric linear programming
- A new approach for automatic theorem proving in real geometry
- On the complexity of entailment in propositional multivalued logics
- Consistency, redundancy, and implied equalities in linear systems
- On a decision procedure for quantified linear programs
- An analysis of totally clairvoyant scheduling
- Generalizing the Template Polyhedral Domain
- Typing Linear Constraints for Moding CLP( ${\cal R}$ ) Programs
- Computational complexity of parametric linear programming
- On the combinatorial and algebraic complexity of quantifier elimination
- QEPCAD B
- Efficient solving of quantified inequality constraints over the real numbers
- Hybrid Systems: Computation and Control
- Theory and Applications of Satisfiability Testing
- Formal Methods in Computer-Aided Design
- Correct Hardware Design and Verification Methods
- On Parametric Linear Programming
