Complexity of the Unconstrained Traveling Tournament Problem

Rishiraj Bhattacharyya

doi:10.1016/j.orl.2016.07.011

Complexity of the Unconstrained Traveling Tournament Problem

Rishiraj Bhattacharyya

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	649-654
Number of pages	6
Journal	Operations Research Letters
Volume	44
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2016.07.011
Publication status	Published - 1 Sept 2016

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

Access to Document

10.1016/j.orl.2016.07.011

Cite this

@article{22370f2edf004700b7aeea7dd4f4eec9,

title = "Complexity of the Unconstrained Traveling Tournament Problem",

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.",

keywords = "NP-hard, Scheduling, Traveling Tournament Problem",

author = "Rishiraj Bhattacharyya",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2016",

month = sep,

day = "1",

doi = "10.1016/j.orl.2016.07.011",

language = "English",

volume = "44",

pages = "649--654",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - Complexity of the Unconstrained Traveling Tournament Problem

AU - Bhattacharyya, Rishiraj

PY - 2016/9/1

Y1 - 2016/9/1

N2 - 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.

AB - 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.

KW - NP-hard

KW - Scheduling

KW - Traveling Tournament Problem

UR - http://www.scopus.com/inward/record.url?scp=84980335869&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2016.07.011

DO - 10.1016/j.orl.2016.07.011

M3 - Article

AN - SCOPUS:84980335869

SN - 0167-6377

VL - 44

SP - 649

EP - 654

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

Complexity of the Unconstrained Traveling Tournament Problem

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this