Optimization Online


A Note on Complexity of Traveling Tournament Problem

Rishiraj Bhattacharyya (rishi_r***at***isical.ac.in)

Abstract: Sports league scheduling problems have gained considerable amount of attention in recent years due to its huge applications and challenges. Traveling Tournament problem, proposed by Trick et. al. (2001), is a problem of scheduling round robin leagues which minimizes the total travel distance maintaining some constraints on consecutive home and away matches. No good algorithm is known to tackle this problem. Many issues including complexity of the problem is open. In this article we show that traveling tournament problem without the constraint of consecutive home and away matches is NP-hard. We hope our technique will be useful in proving the hardness of original TTP.

Keywords: Tournament Scheduling, NP-Hard

Category 1: Applications -- OR and Management Sciences (Scheduling )


Download: [PDF]

Entry Submitted: 11/29/2009
Entry Accepted: 12/01/2009
Entry Last Modified: 12/20/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society