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]
|
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 |
Altmetric
Altmetric
