Tropically convex constraint satisfaction
From MaRDI portal
Publication:1635805
DOI10.1007/s00224-017-9762-0zbMath1390.68333arXiv1506.04184OpenAlexW2606220637MaRDI QIDQ1635805
Manuel Bodirsky, Marcello Mamino
Publication date: 1 June 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.04184
computational complexitystochastic gamesconstraint satisfactiontropical convexitymax-closuremax-plus-average inequalitiespiecewise linear constraintssemi-linear relations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
Tropical Carathéodory with matroids ⋮ Tropical Complementarity Problems and Nash Equilibria ⋮ Unnamed Item ⋮ Max-Closed Semilinear Constraint Satisfaction
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- Computational complexity of linear constraints over the integers
- Mean-payoff games and propositional proofs
- Semidefinite representation of convex sets
- A representation of convex semilinear sets
- A unifying approach to temporal constraint reasoning
- The complexity of mean payoff games on graphs
- Tropical convexity
- Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
- TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
- Tropical Effective Primary and Dual Nullstellens"atze
- Essential Convexity and Complexity of Semi-Algebraic Constraints
- Constraint Satisfaction Problems over the Integers with Successor
- Semilinear Program Feasibility
- The Complexity of Solving Stochastic Games on Graphs
- A Decision Procedure for the First Order Theory of Real Addition with Order
- `` Strong NP-Completeness Results
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Scheduling with AND/OR Precedence Constraints
- Classifying the Complexity of Constraints Using Finite Algebras
- The Max-Atom Problem and Its Relevance
- Stochastic Games with Perfect Information and Time Average Payoff
- Tractable constraints on ordered domains
This page was built for publication: Tropically convex constraint satisfaction
