6 papers
Duality attainment and strict feasibility of the generalized moment problem and its relaxations
Sami Halaseh, Victor Magron, Mateusz Skomra
The generalized moment problem (GMP) is an infinite dimensional linear problem over the cone of finite nonnegative Borel measures. When a GMP instance involves finitely many polyno…
Finite Convergence of the Moment-SOS Hierarchy on the Product of Spheres
Sami Halaseh, Victor Magron, Mateusz Skomra
We study the polynomial optimization problem of minimizing a multihomogeneous polynomial over the product of spheres. This polynomial optimization problem models the tensor optimiz…
Reducing Stochastic Games to Semidefinite Program Feasibility
Manuel Bodirsky, Georg Loho, Mateusz Skomra
We present a polynomial-time reduction from max-plus-average constraints to the feasibility problem for semidefinite programs. This shows that Condon's simple stochastic games, sto…
Games on Graphs: From Logic and Automata to Algorithms
Nathanaël Fijalkow, C. Aiswarya, Guy Avni +22
The objective of this book is to give a comprehensive presentation of the research field concerned with infinite duration games on graphs. Historically, these game models appeared…
Cycle Patterns and Mean Payoff Games
Georg Loho, Matthew Maat, Mateusz Skomra
We introduce the concept of a \emph{cycle pattern} for directed graphs as functions from the set of cycles to the set . The key example for such a pattern is derived fro…
Universal Complexity Bounds Based on Value Iteration for Stochastic Mean Payoff Games and Entropy Games
Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz +1
We develop value iteration-based algorithms to solve in a unified manner different classes of combinatorial zero-sum games with mean-payoff type rewards. These algorithms rely on a…