Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2308.14124 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908382152097792 |
|---|---|
| author | Zhao, Jingyang Xiao, Mingyu |
| author_facet | Zhao, Jingyang Xiao, Mingyu |
| contents | The Traveling Tournament Problem (TTP-$k$) is a well-known benchmark problem in sports scheduling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other's home venue, no pair of teams plays each other on two consecutive days, each team plays at most $k$ consecutive home games or away games, and the total traveling distance of all the $n$ teams is minimized. TTP-$k$ allows a polynomial-time approximation scheme when $k=2$ and becomes APX-hard when $k\geq n-1$. In this paper, we reduce the gap by showing that TTP-$k$ is APX-hard for any fixed $k\geq3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14124 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The APX-hardness of the Traveling Tournament Problem Zhao, Jingyang Xiao, Mingyu Data Structures and Algorithms The Traveling Tournament Problem (TTP-$k$) is a well-known benchmark problem in sports scheduling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other's home venue, no pair of teams plays each other on two consecutive days, each team plays at most $k$ consecutive home games or away games, and the total traveling distance of all the $n$ teams is minimized. TTP-$k$ allows a polynomial-time approximation scheme when $k=2$ and becomes APX-hard when $k\geq n-1$. In this paper, we reduce the gap by showing that TTP-$k$ is APX-hard for any fixed $k\geq3$. |
| title | The APX-hardness of the Traveling Tournament Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2308.14124 |