2
$\begingroup$

A sports league wants to use an algorithm to decide when & where each team will be playing another team in the league. Each team will play the other team in either the first team's home city or the second team's home city. For example, if this is the National (American) Football League, the Houston Texans would play the Jacksonville Jaguars in either Houston or Jacksonville.

This sounds like a special case of Multiple Travelling Salesmen. Can this be trivially reduced to Multiple Travelling Salesmen? At the very least, can we use similar algorithms?

Requirements

  1. Each team in the league plays each other team in the league. If the league consists of teams A,B,and C, A will play B and C, B will play A and C, and C will play A and B.

  2. All teams play between 6 and 10 PM local time.

$\endgroup$
3
  • $\begingroup$ It's impossible to say without knowing what requirements you have on the schedule. $\endgroup$
    – D.W.
    Jan 30, 2022 at 3:46
  • $\begingroup$ I'm finding that hard to imagine. For instance, if the schedule says that the Jaguars play zero games, I doubt you'll be happy. If the schedule says that the Jaguars play ten games, each one against the Texans, I doubt you'll be happy. I wonder if you're trying to minimize something, like travel time, subject to some constraints, such as that each team plays each other team once. $\endgroup$
    – D.W.
    Jan 30, 2022 at 21:52
  • $\begingroup$ Please don't put the requirements in the comments. Instead, edit the question so it is self-contained and reads well for someone who encounters this for the first time. Make sure that all requirements are listed. Why do you think this has any connection to the travelling salesman problem? I suggest elaborating on that as well. $\endgroup$
    – D.W.
    Jan 31, 2022 at 5:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.