A Faster Deterministic Approximation Algorithm for TTP-2
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914695322009600 |
|---|---|
| author | Kanaya, Yuga Takazawa, Kenjiro |
| author_facet | Kanaya, Yuga Takazawa, Kenjiro |
| contents | The traveling tournament problem (TTP) is to minimize the total traveling distance of all teams in a double round-robin tournament. In this paper, we focus on TTP-2, in which each team plays at most two consecutive home games and at most two consecutive away games. For the case where the number of teams $n\equiv2$ (mod 4), Zhao and Xiao (2022) presented a $(1+5/n)$-approximation algorithm. This is a randomized algorithm running in $O(n^3)$ time, and its derandomized version runs in $O(n^4)$ time. In this paper, we present a faster deterministic algorithm running in $O(n^3)$ time, with approximation ratio $1+9/n$. This ratio improves the previous approximation ratios of the deterministic algorithms with the same time complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_02592 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Faster Deterministic Approximation Algorithm for TTP-2 Kanaya, Yuga Takazawa, Kenjiro Data Structures and Algorithms Combinatorics The traveling tournament problem (TTP) is to minimize the total traveling distance of all teams in a double round-robin tournament. In this paper, we focus on TTP-2, in which each team plays at most two consecutive home games and at most two consecutive away games. For the case where the number of teams $n\equiv2$ (mod 4), Zhao and Xiao (2022) presented a $(1+5/n)$-approximation algorithm. This is a randomized algorithm running in $O(n^3)$ time, and its derandomized version runs in $O(n^4)$ time. In this paper, we present a faster deterministic algorithm running in $O(n^3)$ time, with approximation ratio $1+9/n$. This ratio improves the previous approximation ratios of the deterministic algorithms with the same time complexity. |
| title | A Faster Deterministic Approximation Algorithm for TTP-2 |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2310.02592 |