Priority Promotion with Parysian Flair



Benerecetti, Massimo, Dell'Erba, Daniele ORCID: 0000-0003-1196-6110, Mogavero, Fabio, Schewe, Sven ORCID: 0000-0002-9093-9518 and Wojtczak, Dominik ORCID: 0000-0001-5560-0546
(2021) Priority Promotion with Parysian Flair. [Preprint]

[thumbnail of 2105.01738v1.pdf] Text
2105.01738v1.pdf - Submitted version

Download (1MB) | Preview

Abstract

We develop an algorithm that combines the advantages of priority promotion - one of the leading approaches to solving large parity games in practice - with the quasi-polynomial time guarantees offered by Parys' algorithm. Hybridising these algorithms sounds both natural and difficult, as they both generalise the classic recursive algorithm in different ways that appear to be irreconcilable: while the promotion transcends the call structure, the guarantees change on each level. We show that an interface that respects both is not only effective, but also efficient.

Item Type: Preprint
Uncontrolled Keywords: cs.DS, cs.DS
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 17 May 2021 07:17
Last Modified: 15 Mar 2024 00:25
DOI: 10.48550/arxiv.2105.01738
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3123001