14 novembre 2019, Salle A, 12:00
Katarína Cechlárová: The Young Physicists' Tournament – how to find a fair schedule
joint work with Marián Kireš, Lukáš Miňo (Košice) and Agnes Cseh, Zsuzsanna Jankó (Budapest)
Abstract: The Young Physicists' Tournament is an international competition of teams that can get into the international final through regional and national tournaments. The competing teams learn not only how to solve physical problems published by the international jury and present their solutions in a scientific way, but also how to oppose and evaluate solutions of other teams.
The rules valid for regional tournaments in Slovakia require each team to indicate 3 chosen problems (out of 17 published) in their application – the chosen problems will be presented. The rules lead to a nontrivial scheduling problem. The organizers have to decide about FIGHTs: scientific workshops of three or four team, where the teams alternate in the roles of Presenter, Opponent and Reviewer. The necessary feasibility constraints are: (1) each team presents all their chosen problems and nothing else, (2) no problem is presented more than once in one FIGHT. We also formulated additional fairness conditions, ensuring that no team will see a presentation of some of their chosen problem before they present it themselves.
To find fair schedules we formulated an integer program and tested it on real and randomly generated data. In most cases we were able to find schedules fulfilling weak fairness conditions within seconds, but strong fairness was unsolvable withing the time limit. Therefore we formulated as an open problem a possible change of the rules.