UvA-VU student Kristian Verduin published and defended a paper on Evostar2023. It was a direct result of his MSc-thesis Software Engineering at UvA-VU.
The Traveling Tournament Problem sounds a lot like the Traveling Salesman Problem. But it isn’t. It’s much harder.
Both the Traveling Tournament Problem and the Traveling Salesman Problem are constrained optimization problems, but the constraints on the Traveling Tournament Problem are so severe that just finding any kind of solution – good or bad – is a problem. “And the problem gets bigger over time”, says Kristian Verduin. “My investigation shows that for scheduling between 6 and 50 teams in a tournament, constraint violations grow quadratically. That doesn’t sound so bad, but even the best found tournament schedule still has over 3000 contraint violations. Imagine that in a university timetable!”
A time estimate for sampling a random valid tournament schedule is even worse: over millions of times the lifespan of the universe. “That’s why the Traveling Salesman Problem is easier, even though both are NP-complete” says Daan van den Berg, Kris’ supervisor. “For the Traveling Salesman, you can have a few guesses. For the Traveling Tournament Problem? Out of the question.”