| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
A Greedy Algorithm for the Social Golfer and the Oberwolfach Problem | Daniel Schmand
; Marc Schröder
; Laura Vargas Koch
; | Date: |
21 Jul 2020 | Abstract: | Inspired by the increasing popularity of Swiss-system tournaments in sports,
we study the problem of predetermining the total number of rounds that can at
least be guaranteed in a Swiss-system tournament. For tournaments with $n$
participants, we prove that we can always guarantee $n/2$ rounds under the
constraint that no player faces the same opponent more than once. We show that
this bound is tight. We generalize our results to two combinatorial problems,
namely the social golfer problem and the Oberwolfach problem. The social golfer
problem can be seen as a tournament with match sizes of $kgeq2$ players in
which no pair of players meets each other more than once. For a natural greedy
algorithm, we show that it calculates at least $lfloor n/(k(k-1))
floor$
rounds and that this bound is tight. This gives rise to a simple polynomial
time $1/k$-approximation algorithm for $k$-somes in golf tournaments. Up to our
knowledge, this is the first analysis of an approximation algorithm for the
social golfer problem. In the Oberwolfach problem, a match corresponds to a
group of $k$ players positioned in a cycle and the constraint is that no
participant should meet the same neighbor more than once. We show that the
simple greedy approach guarantees at least $lfloor (n+4)/6
floor$ rounds for
the Oberwolfach problem. Assuming that El-Zahar’s conjecture is true, we
improve the bound to be essentially tight. | Source: | arXiv, 2007.10704 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |