Complexity of the Unconstrained Traveling Tournament Problem

Rishiraj Bhattacharyya

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

The Traveling Tournament problem is a problem of scheduling round robin leagues which minimizes the total travel distance maintaining some constraints on consecutive home and away matches. The problem was proven NP-hard when the upper bound on any consecutive home or away stint is 3. In this paper, we prove that even without the constraints on the consecutive home or away matches, the problem remains NP-Hard.

Original languageEnglish
Pages (from-to)649-654
Number of pages6
JournalOperations Research Letters
Volume44
Issue number5
DOIs
Publication statusPublished - 1 Sep 2016
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2016 Elsevier B.V.

Keywords

  • NP-hard
  • Scheduling
  • Traveling Tournament Problem

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Complexity of the Unconstrained Traveling Tournament Problem'. Together they form a unique fingerprint.

Cite this