Reducing Stochastic Games to Semidefinite Programming
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
We present a polynomial-time reduction from max-average constraints to the feasibility problem for semidefinite programs. This shows that Condon’s simple stochastic games, stochastic mean payoff games, and in particular mean payoff games and parity games can all be reduced to semidefinite programming.
Details
| Originalsprache | Englisch |
|---|---|
| Titel | 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025 |
| Redakteure/-innen | Keren Censor-Hillel, Fabrizio Grandoni, Joel Ouaknine, Gabriele Puppis |
| Herausgeber (Verlag) | Schloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing |
| Seitenumfang | 15 |
| ISBN (elektronisch) | 9783959773720 |
| Publikationsstatus | Veröffentlicht - 30 Juni 2025 |
| Peer-Review-Status | Ja |
Publikationsreihe
| Reihe | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Band | 334 |
| ISSN | 1868-8969 |
Konferenz
| Titel | 52nd EATCS International Colloquium on Automata, Languages, and Programming |
|---|---|
| Kurztitel | ICALP 2025 |
| Veranstaltungsnummer | 52 |
| Dauer | 8 - 11 Juli 2025 |
| Webseite | |
| Ort | Aarhus University |
| Stadt | Aarhus |
| Land | Dänemark |
Externe IDs
| ORCID | /0000-0001-8228-3611/work/208071917 |
|---|
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- max-atom problem, max-average constraints, Mean-payoff games, semidefinite programming, stochastic games