Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'487'895
Articles rated: 2609

28 March 2024
 
  » arxiv » 2007.10704

 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
AbstractInspired 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   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  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






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica