Constraint Satisfaction Problems over Numeric Domains
From MaRDI portal
Publication:4993596
DOI10.4230/DFU.Vol7.15301.79zbMath1482.68162OpenAlexW2592282387MaRDI QIDQ4993596
Marcello Mamino, Manuel Bodirsky
Publication date: 15 June 2021
Full work available at URL: https://doi.org/10.4230/DFU.Vol7.15301.3
Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)
Related Items
An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains, Unnamed Item, \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's, Unnamed Item, The Complexity of Valued CSPs, Tractability conditions for numeric CSPs, Solving equation systems in ω-categorical algebras, Piecewise linear valued constraint satisfaction problems with fixed number of variables
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distance constraint satisfaction problems
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- Computational complexity of linear constraints over the integers
- A new polynomial-time algorithm for linear programming
- Combinatorial structure and randomized subexponential algorithms for infinite games
- Semidefinite representation of convex sets
- The complexity of equality constraint languages
- Semidefinite programming and arithmetic circuit evaluation
- Cyclic games and linear programming
- Worst case behavior of the steepest edge simplex method
- Positional strategies for mean payoff games
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- The complexity of stochastic games
- Transitivity of permutation groups on unordered sets
- NP-complete decision problems for binary quadratics
- A unifying approach to temporal constraint reasoning
- Intersection graphs of segments
- The complexity of mean payoff games on graphs
- An exact duality theory for semidefinite programming and its complexity implications
- The wonderland of reflections
- Tropical convexity
- A subexponential bound for linear programming
- Hilbert's Nullstellensatz is in the polynomial hierarchy
- Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
- The simplex algorithm with the pivot rule of maximizing criterion improvement
- THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
- Realizability of Graphs and Linkages
- On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
- An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
- Constraint satisfaction tractability from semi-lattice operations on infinite sets
- Tropical Effective Primary and Dual Nullstellens"atze
- A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Integer Programming with a Fixed Number of Variables
- Essential Convexity and Complexity of Semi-Algebraic Constraints
- Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Towards a Genuinely Polynomial Algorithm for Linear Programming
- Linear matrix inequality representation of sets
- Constraint Satisfaction Problems over the Integers with Successor
- Non-dichotomies in Constraint Satisfaction Complexity
- Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets
- The complexity of temporal constraint satisfaction problems
- On the Complexity of Numerical Analysis
- The Complexity of Solving Stochastic Games on Graphs
- The Computational Complexity of Simultaneous Diophantine Approximation Problems
- Linear Programming in Linear Time When the Dimension Is Fixed
- Definability in reducts of algebraically closed fields
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Universal diophantine equation
- Algorithms for the Solution of Systems of Linear Diophantine Equations
- Additive reducts of real closed fields
- A Decision Procedure for the First Order Theory of Real Addition with Order
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Reducts of some structures over the reals
- Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Reasoning about temporal relations
- Closure properties of constraints
- Semidefinite Representation for Convex Hulls of Real Algebraic Curves
- The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
- Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
- Scheduling with AND/OR Precedence Constraints
- The interior-point revolution in optimization: History, recent developments, and lasting consequences
- Reducibility among Combinatorial Problems
- An Exact Duality Theory for Semidefinite Programming Based on Sums of Squares
- Combinatorial Simplex Algorithms Can Solve Mean Payoff Games
- Cores of Countably Categorical Structures
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
- The Max-Atom Problem and Its Relevance
- Stochastic Games with Perfect Information and Time Average Payoff
- Max-Closed Semilinear Constraint Satisfaction
- Reducts of (C, +, ·) which contain +
- Tractable constraints on ordered domains
- Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning
