2026-08-11T02:58:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22233 2024-12-05T15:32:41Z ddc:004 open_access

On Controlling Knockout Tournaments Without Perfect Information Blažej, Václav Gupta, Sushmita Ramanujan, M. S. Strulo, Peter Parameterized algorithms Tournament design Imperfect information Over the last decade, extensive research has been conducted on the algorithmic aspects of designing single-elimination (SE) tournaments. Addressing natural questions of algorithmic tractability, we identify key properties of input instances that enable the tournament designer to efficiently schedule the tournament in a way that maximizes the chances of a preferred player winning. Much of the prior algorithmic work on this topic focuses on the perfect (complete and deterministic) information scenario, especially in the context of fixed-parameter algorithm design. Our contributions constitute the first fixed-parameter tractability results applicable to more general settings of SE tournament design with potential imperfect information. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Václav Blažej and Sushmita Gupta and M. S. Ramanujan and Peter Strulo 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.7 urn:nbn:de:0030-drops-222337 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode