Minimizing breaks by minimizing odd cycle transversals
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909401176080384 |
|---|---|
| author | Fujii, Koichi Matsui, Tomomi |
| author_facet | Fujii, Koichi Matsui, Tomomi |
| contents | Constructing a suitable schedule for sports competitions is a crucial issue in sports scheduling. The round-robin tournament is a competition adopted in many professional sports. For most round-robin tournaments, it is considered undesirable that a team plays consecutive away or home matches; such an occurrence is called a break. Accordingly, it is preferable to reduce the number of breaks in a tournament. A common approach is first to construct a schedule and then determine a home-away assignment based on the given schedule to minimize the number of breaks (first-schedule-then-break). In this study, we concentrate on the problem that arises in the second stage of the first-schedule-then-break approach, namely, the break minimization problem(BMP). We prove that this problem can be reduced to an odd cycle transversal problem, the well-studied graph problem. These results lead to a new approximation algorithm for the BMP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_15463 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minimizing breaks by minimizing odd cycle transversals Fujii, Koichi Matsui, Tomomi Discrete Mathematics Constructing a suitable schedule for sports competitions is a crucial issue in sports scheduling. The round-robin tournament is a competition adopted in many professional sports. For most round-robin tournaments, it is considered undesirable that a team plays consecutive away or home matches; such an occurrence is called a break. Accordingly, it is preferable to reduce the number of breaks in a tournament. A common approach is first to construct a schedule and then determine a home-away assignment based on the given schedule to minimize the number of breaks (first-schedule-then-break). In this study, we concentrate on the problem that arises in the second stage of the first-schedule-then-break approach, namely, the break minimization problem(BMP). We prove that this problem can be reduced to an odd cycle transversal problem, the well-studied graph problem. These results lead to a new approximation algorithm for the BMP. |
| title | Minimizing breaks by minimizing odd cycle transversals |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2411.15463 |