Hard problems in max-algebra, control theory, hypergraphs and other areas
From MaRDI portal
Publication:990130
DOI10.1016/j.ipl.2009.11.007zbMath1206.68284OpenAlexW2154682386MaRDI QIDQ990130
Marc Bezem, Robert Nieuwenhuis, Enric Rodríguez-Carbonell
Publication date: 2 September 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.11.007
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Control/observation systems involving computers (process control, etc.) (93C83) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES, Extremality criteria for the supereigenvector space in max-plus algebra, Computing the vertices of tropical polyhedra using directed hypergraphs, Tropical linear-fractional programming and parametric mean payoff games, New algorithms for solving tropical linear systems, A note on tropical linear and integer programs, Geometric Quantifier Elimination Heuristics for Automatically Generating Octagonal and Max-plus Invariants, Tropical Cryptography, Tropical polar cones, hypergraph transversals, and mean payoff games, On Special Cases of the Generalized Max-Plus Eigenproblem, A strongly polynomial method for solving integer max-linear optimization problems in a generic case, Complexity of tropical and MIN-plus linear prevarieties
Cites Work
- Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra
- Positional strategies for mean payoff games
- On-line computation of minimal and maximal length paths
- Min-max functions
- Directed hypergraphs and applications
- A strongly polynomial algorithm for solving two-sided linear systems in max-algebra
- Solving SAT and SAT Modulo Theories
- Scheduling with AND/OR Precedence Constraints
- The Max-Atom Problem and Its Relevance
