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

zbMATH Keywords

computational complexitypolynomial algorithmentailmentparameterized linear constraintquantified linear implicationquantified 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)

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

Describes a project that uses

Uses Software

• PolyLib
• MPT
• RSOLVER
• REDLOG
• QuBE++
• QEPCAD

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)