Publication

Minimizing breaks in incomplete round-robin tournaments

Dominique de Werra
2025

Résumé

In round-robin schedules, a break occurs when a team plays two consecutive home or two consecutive away games. Minimizing breaks is important for ensuring competitive fairness and logistical efficiency. This article addresses the problem of minimizing breaks in incomplete round-robin schedules in which each pair of teams plays again each other at most once. The problem of minimizing breaks is a classical problem that was previously thoroughly studied in the context of complete round-robin schedules. Using a graph-theoretic model we analyze structural properties of incomplete round-robin schedules. We derive some bounds on the minimum number of breaks. Then, we propose an algorithm that is able to construct incomplete single round-robin schedules minimizing the number of breaks for given numbers of teams and rounds if the number of rounds is not larger than 3/4 of the number of teams.

Source officielle

https://infoscience.epfl.ch/entities/publication/f8ec4bb4-0a63-40ed-bbec-5953cb1de35a

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dominique de Werra
2025

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/f8ec4bb4-0a63-40ed-bbec-5953cb1de35a

À propos de ce résultat

Concepts associés (19)

Round-robin (informatique)

thumb|upright=1.5|Exemple de planification de tâches en round-robin Le Round-robin (ou tourniquet) est un algorithme d'ordonnancement courant dans les systèmes d'exploitation adapté aux systèmes travaillant en temps partagés. Une petite unité de temps, appelé quantum de temps, est définie. La file d'attente est gérée comme une file circulaire. L'ordonnanceur parcourt cette file et alloue un temps processeur à chacun des processus pour un intervalle de temps de l'ordre d'un quantum au maximum.

Kepler problem

In classical mechanics, the Kepler problem is a special case of the two-body problem, in which the two bodies interact by a central force F that varies in strength as the inverse square of the distance r between them. The force may be either attractive or repulsive. The problem is to find the position or speed of the two bodies over time given their masses, positions, and velocities. Using classical mechanics, the solution can be expressed as a Kepler orbit using six orbital elements.

Mouvement à force centrale

En mécanique du point, un mouvement à force centrale est le mouvement d'un point matériel M soumis uniquement à une force centrale, c'est-à-dire une force toujours dirigée vers le même point noté O appelé centre de force. Ce type de mouvement est une modélisation de certains phénomènes physiques : il n'est pas rigoureusement présent dans la nature, mais certains mouvements s'en rapprochent. Par exemple, on peut considérer que la Terre est soumise à une force centrale de la part du Soleil.

Afficher plus