侶コ窃＝瑠
田本オペレーションズ0リサーチ学会
2￠04年容季節究発乗合TheBreakMinimization Problem
O2602190 TheUniversityofTbkyo ＊MIYÅSHIRORyuhei
O1605000 TheUniversityofTbkyo MATSUITbmomi
In this abstract，We prOVe a previously proposed
COnjecture about the bl％k minimization prDblem，
Whichisaproblemintheareaofsportsscheduling．
VVe consider around−rObin tournament that sat−
isfiesthefo1lowlngprOperties：
Othenumberofteamsis2nandthatofslotsis2n−1；
OeaChteamplaysonegameineachslot；
OeaChteamplayseveryotherteamonce；
OeaChteamhasitshomeandeachgameisheldat
thehomeofoneoftheplayingtwoteams．Figurelis a schedule of a tournament satisfying
theseproperties．Inthefigure，eaChgamewith ＠ means that the game is held at the home of the
OpPOnent；without ◎ meansthatthegameisheld atthehomeoftheteamcorrespondingtotherow．
Fbr example，team4plays team2at the home of team2inslot3．
Ifateam plays either both at homeorboth at
awqyinslots sand s＋1，itis said that theteam has a break at slot s＋1．h a schedule，a break isexpressedasanunderlineataslotwhereabreak
OCCurS．Fbrexample，inFig．1，team3playsathome inslotsland2，andwesaythatteam3ha5abreak
atslot2．htotal，theschedulehassixbreaks．
Given aschedule without a home−aWay aSSlgn−
ment，anOrganizerofthetournamentshoulddecidea
home−aWayaSSignment，Whichthenumberofbreaks dependson．Fbrapracticalreason，anOrganizergen−
erallyprefbrsahome−aWayaSSignmentinwhichthe
numberofbreaksissma11．Inthiscontext，thebreak minimizationproblemisde丘nedasfo1lows．Break
Inpu七‥ A schedulewithout ahome−aWay aSSlgn−
ment．
Ouもp血：A home−aWqy aSSignment consistent to
the given input and in which the number of
breaksis minimized．
The schedule without a home−aWay aSSlgnment Of
Fig．2isaninputforthebreakmimimi2；ationprob−
1em．AlthoughthescheduleofFig．1showsafbasible home−aWayaSSlgnmentfortheinput，itis subopti−
mal．ThescheduleofFig．2isanOPtimalsolution，
Whoseoptimalvalueisfbur．
There are some previous results on the break mimimizationproblem．R6ginsoIvedupto20teams
instances with constraint programming t5】・取ick
︶ t
O
I S
︵ 5
4
3
2 1 4 3 2 1一6一5 ◎ ＠ ◎ 2 1 5 亡U 3 4 ◎ ＠◎
5一4一6 2 1 3 ◎ ◎＠
3一6 1一5 4 2 ◎ ◎◎
6 5 4 3 2 1 ◎＠ ◎
1 2 3 4
Figurel．Aschedulewithsixbreaks
proposed integer programming formulations and
SOIvedinstancesupto22teamS［6］・Elf，J仏ngerand RinaldiformulatedthisproblemasMAXCUT，and
SOlvedinstancesupto26teams［3】・Theauthorsfor−
mulatedthisproblemaBMAXRESCUT，andpro−
posed analgoritlmbased on positive semidefinite programmingrelaxation［4】．
Therearesomeopenproblemsabout thebreak
minimization problem．Althoughitis conjectured that the breakminimization problemis NP−hard，
the complexity status of this problem is not yet
determined．Concernlng the complexity，Elfetal．
reportedthefo1lowingresult【3】‥theirin5tanCeSOf the bresbk minimizaeion problem were solved very quicklywith their method when theinstanCeS had
theoptimalvalue2n−2・（Thevalue2n−2is a
lowerboundoftheobjectivevalueforanyinstanceof 2nteams，becauseascheduleof2nteamsha5atleast
2n−2breaks f2］・）Accordingtotheirexperience，
theyconjecturedthatthebreakminimizationprob−
lemissoIvableinpolynomialtimeifaglVeninstanCe Of2nteamshastheoptimalvalue2n−2．
Weprovetheirco可ectureafRrmativelybyshow−
ingthatthefo1lowingproblemPIcanbesoIvedin polynomialtime．
Problem Pl
Imp血：A schedule of2n teams andwithout a
home−aWqyaSSignment．
Outpu七：A home−aWay aSSignmentwith2n−2
breaks，ifexists；elseinfeasible．
Inthe払Ilowing，WeShowthatProblemPlissoIvable inO（n3）steps．FbrProblemPl，WedefineSubprob−
1em Pl（k）asfo1lows（k∈T，WhereTis aset of teams，i・e・（1，2，・・・，2n））・ItisnotdifRculttosee
−176−
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
Xt，S∈（TRUE，FALSE）
現，8＝FALSE エ土，β≠ち（t，βい
「ごt，8V∬t，叶1
∬t，β−1Vr∬t，5 ごり∨エt，2れ−1
︶ ︶ ︶ J g g ︐ ．
外
∈ ∈ ∈ ∈ ∈
⊥ん ぐU・TV・ナし β ∀ ∀ ∀ ∀ ∀ ︵ ︵ ︵ ︵
2 5 4 3 2 1 6 5 2 1 5 6 3 4 5 4 6 2 1 3
3 6 1 5 4 2
ごU 5 4 3 2 1
1 2 3 4 5 6 ︸ 呵＞ ︷ β ＼ r鼠 ∈ ∈ ・ナし OU ∀ ∀ ︵ ︶
■レ
︻∂
（∀f∈r＼（り），
where
T（t，S）：theteamwhichteamtplaysatslotsin theinputofPl′（k）；
Sk．t‥theslotatwhichteamkplaysteamtinthe inputofPl′（k）・
Each of the constraints can be represented as
Clause（s）withtwoliterals；thenumberofvariables andthatofclauseswithtwoliteralsarebothO（n2）．
Since2SATwithpliteralsandqclausesissoIvable
inO（p＋q）steps［1】，ProblemPl （k）canbesoIved in0（n2）steps，andhenceProblemPlissoIvablein 0（れ3）steps．
References
【1］B．Aspval，M．F．Plass and R．E．T叫an：A Linear−TimeAlgorithmforTbstingtheTruthof
Certain Quantified BooleanFbrmulas．htfbmna一 如mク和αβ血クエe比erβ，8（1979）12ト123・
【2】D．de Werra：Geography，Gamesand Graphs．
β由crefeAppJ豆ed〟α仇emα而cβ，2（1980）327−337・
【3】M・Elf7M・Jdngr
．
エe操erβ，31（2003）343−349・
【4］R・Miyashiro，・T・MqtSui：SemidefiniteProgrm−
mlngBasedApproachestothelBreakMinimlZa−
tionProblem．MathematicalEn9ineerin9Tbchわi−
CalReports，METR2003−28（Department of MathematicalInformatics，Graduate Schoolof
InformationScienceandTbchnology，TheUniver−
SityofTbkyo，2003）．（availableathttp：／／ⅥW・
keisu・t・u−tOkyo．ac．jp／Research／techrep・0・html）
【5】J．−C．R6gin：Minimization ofthe Number of Breaksin Sports Scheduling Problems Using
Constraint Programming．InE．C．Fteuderand R．J・Ⅵね1lace（eds．）：Construint Prpgrummin9 andLaryeScaleDisc†℃teOptimization（DIMACS Seriesin Discrete Mathematics and Theoretical
Computer Science，57，AmericanMathematical Society，2001），115−130．
【6］M・A・nick：ASchedule−Then−BreakAppr？aCh
toSportsTimetabling．InE．BurkeandW．Erben
（eds．）：Pmc亡戎ααれdmeo相可At血mαねd乃me−
tablin9IH（LectureNotesinComputerScience，
2079，＄pringer，2001），242−253．
2 5
5 4一ごじ一2 1 3 ＠ ◎◎
3 ごU 1 5 4 2 ◎ ＠◎
ごU 5 4 3 2 1 ◎＠ ◎ 4 3 2 1一ごじ一5 ◎ ◎ ◎ 2 1 5 6 3 4
1 2 3 4 5 ごU ＠ ◎＠
Figure2・Aschedulewithoutahome−aWayaSSlgn−
mentandanoptimalasslgnment・
thatProblemPlisfeasibleifandonlyifatleastone OfPl（1），Pl（2），‥．，andPl（2n）isfeasible．
SubproblemPl（k）
Input：ThesameinputasthatofProblemPl．
Output：A home−aWay aSSignment with2n−2
breaks andin which team k haB nO break and
playsathomeinslotl，ifexists；elseinfeasible．
ThefbasibilityofSubproblemPl（k）isequivalent tothatofSubproblemPl′（k）definedbelow．Inaddi−
tion，．afbasiblehome−aWayaSSignmentofPl（k）can beconstructedfromthatofPl′（k），byalternating homewithawayinal1evenslots・（Moregenerally，
thefo1lowing statement holds：by the above men−
tionedalternation，anOptimalsolutionofthebreak minimizationproblemisobtained from thatofthe
breakmaximizationproblemandviceversa・）
SubproblemPl′（k）
Input：ThesameinputasthatofProblemPl．
Output‥Ahome−aWayaSSignmentwith2n（2n−
2）−（2n−2）breaksandinwhichteamkhas
2n−2breaks and plays at homein slotl，if exists；elseinfeaBible・（Inotherwords，teamk playsonlyathomeandeveryotherteamhasat
mostone non−break・ ）
NowweformulateSubproblemPl′（k）（k∈T）as 2SAT・LetSbeasetofslots，i・e・（1，2，・・・，2n−1）・
Wedefine aBoolean variablext，S（t∈T，S∈S）
asfo1lows＝ a Variable xt，Sis FALSEifand onlyif teamtpl如sathomeinslots．Then，aninstanceof SubproblemPl′（k）canbetranSfbrmedasfollows．
−177−
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
