The stable crews problem

内容需要下载文档才能查看 内容需要下载文档才能查看

DiscreteAppliedMathematics140(2004)1–

http://wendang.chazidian.com/locate/dam

Thestablecrewsproblem??

KatarÃ??naCechlÃarovÃaa;?,SoÄnaFerkovÃab

ÄarikUniversity,JesennÃofMathematics,FacultyofScience,P.J.SafÃa5,04154KoÄsice,SlovakiabTatraBanka,a.s.,SoftwareDevelopmentDepartment,ITDivision,HodÄzovonÃam.,81421Bratislava,SlovakiaaInstitute

Received27November2001;receivedinrevisedform13February2003;accepted26May2003Abstract

Inthispapertheclassicalstableroommatesproblemisgeneralizedtosituationswhenthetwopartnersinapairperformdi??erentroles.Weproposeane??cientalgorithmtodecidetheexistenceofastablematchinginthisproblem.?2003ElsevierB.V.Allrightsreserved.

MSC:90C12;68Q25

Keywords:Thestableroommatesproblem;Thestablecrewsproblem;Polynomialalgorithms

1.Introduction

Theclassicalstableroommatesproblem(SRPforshort)introducedin[1]dealswithsituationswhenasetofparticipants,saystudents,hastobepartitionedintopairs,i.e.eachstudenthastobeassignedaroommate.Inthismodelitissupposedthatallthestudentshaveclearpreferencesovertheirprospectiveroommatesandthataparticipant’ssatisfactionwithaparticularmatchingisbasedsolelyontheidentityofhisroommate.Providedtherearenotwoparticipantswhoprefereachothertotheirpartnersinaparticularmatching,thenthematchingiscalledstable.Insomecasesasimplepartitionofpeopleintopairsisnotanappropriatemodel.Imagineagroupofpilots,whohavetobepartitionedintotwo-personaeroplanecrews.Inacrew,say,onepilotisthecaptainandtheotherthenavigator.ItisnaturaltoThisworkwassupportedbytheSlovakAgencyforScience,“CombinatorialStructuresandComplexityofAlgorithms”,1/0425/03.?Correspondingauthor.E-mailaddress:cechlarova@science.upjs.sk(K.CechlÃarovÃa).

0166-218X/$-seefrontmatter?2003ElsevierB.V.Allrightsreserved.doi:10.1016/j.dam.2003.05.003??

2K.CechlÃarovÃa,S.FerkovÃa/DiscreteAppliedMathematics140(2004)1–17

expectthatapilot’sevaluationofacrewdependsnotonlyontheidentityofhispartner,butalsoonthedistributionoftheroles.Forexample,pilotimaylikepilotjasanavigator,butconsiderhimtobequiteapoorcaptain.Inthispaper,weproposetomodelsuchsituationsbyallowingeachparticipantitoincludeinhispreferencelisttwocopiesofeveryotherparticipantj,representingthetwopossiblerolesjcanperforminacrewconsistingofiandj.Weshowthatour‘stablecrewsproblem’(SCPforshort)isageneralizationofthestableroommatesproblem.Further,ifthepreferencesofparticipantsarestrict,itispossibletodecidetheexistenceofastablematchingbyapolynomialalgorithmthatisanextensionofIrving’sclassicalstableroommatesalgorithm[2,3].InSection2,wedeÿneformallythestablecrewsproblemandintroducetheessentialterminologyusedinthepaper.Section3isdevotedtotherelationbetweentheSRPandtheSCP.ThestablecrewsalgorithmisderivedinSection4.Finally,Section5summarizestheresultsandoutlinespossibletopicsforfutureresearch.

2.Deÿnitionsandnotation

Nisthesetofparticipantsandwesupposethat|N|=niseven.ThesetN×{1;2}willrepresenttheparticipantswithassignedroles.Anelement[i;t]∈N×{1;2}willusuallybedenotedbyit.Foreachparticipanti∈Nthereisacomplete,re exiveandtransitivepreferencerelationdeÿnedonasubsetof(N\{i})×{1;2}denotedby??i.Ifat??ibs,thenwesaythatparticipantiprefersparticipantainrolettoparticipantbinroles.Ifat??ibsandbs??iat,thenwesaythatparticipantiisindi??erentbetweenparticipantsa;bintherespectiverolesandweshallwriteat?ibs.Ifat??ibsandbs??iatdoesnothold,thenparticipantistrictlyprefersparticipantainrolettoparticipantbinrolesandweshallwriteat??ibs.Thepreferencerelationofparticipanti∈NwillberepresentedbyanorderedpreferencelistdenotedbyP(i).WesaythatparticipantjinroletisacceptableforparticipantiifjtappearsinP(i).Otherwise,jtisunacceptablefori.(Notethatjinrole3?tmaystillbeacceptablefori.)Ann-tupleofpreferencelistsofallparticipantsfromNwillbecalledapreferenceproÿleanddenotedbyP.

Deÿnition1.Aninstanceofthestablecrewsproblemisapair{N;P}.

Deÿnition2.Foragiveninstance{N;P}oftheSCP,afunction??:N→N×{1;2}willbecalledamatching,ifforalli;j∈Nandt∈{1;2}thefollowingconditionsarefulÿlled:

(i)??(i)∈P(i),(ii)if??(i)=jt,thenj=i,(iii)??(i)=jt???(j)=i3?t.

If??(i)=j2(or,equivalently,??(j)=i1)weshallwrite,withsomeabuseofnotation,(i1;j2)∈??.

K.CechlÃarovÃa,S.FerkovÃa/DiscreteAppliedMathematics140(2004)1–173

Deÿnition3.Apair(i1;j2)∈[N×{1;2}]2iscalledablockingpairforamatching??ifj2??i??(i)andi1??j??(j).Amatchingiscalledstableifitisfreeofblockingpairs.Apair(i1;j2)willbecalledastablepairifthereexistsastablematching??suchthat(i1;j2)∈??.

Example1.ConsiderthefollowingpreferenceproÿleforthesetofparticipantsN={a;b;c;d}:

P(a)

P(b)

P(c)===b1;b2;d2;c1;c2;d1;a2;d1;c2;d2;a1;a2;b2;b1;a1;d1;d2;

P(d)=b1;a1;c1:

Here,forexample,theÿrstchoiceofparticipantbisparticipantainthesecondrole,hissecondchoiceisparticipantdintheÿrstrole,histhirdchoiceparticipantcinthesecondrole,etc.Noticethatb’sÿrstchoiceisparticipantainthesecondrolewhileb’slastchoiceisparticipantainÿrstrole;alsocintheÿrstroleisunacceptableforb.Noticealsothatthepair(a1;b2)couldneverbeastablepair,sinceitwouldalwaysbeblockedby(a2;b1)(theparticipantswouldsimplyswitchtheirrolesinacrew).

3.Stablecrewsgeneralizestableroommates

Theorem4.ForeveryinstanceIoftheSRPwithnparticipantsthereexistsaninstanceI??oftheSCPwithnparticipantssuchthateverystablematchingofIcorrespondstoastablematchingofI??andviceversa.

Proof.SupposethatI=(N;P)isaninstanceoftheSRP.Letusdeÿneanarbitrarystrictlinearordering onNanddeÿneaninstanceI??=(N;P??)oftheSCPinthefollowingway:Foreachx∈Nreplaceeachparticipanty∈P(x)bytwoconsecutivecopiesofyinordery1;y2ify xandinordery2;y1otherwise.Let??beastablematchingforI.Letusdeÿneamatching????forI??asfollows:if{x;y}∈??inIandx y,then(x1;y2)∈????.Clearly,????isamatchingforI??andweshowthatitisstableaswell.First,??(x)∈P(x)foreachx,henceduetotheconstructionofP??and????wehave????(x)∈P??(x).Nowsupposethatapair(u1;v2)blocks????.Thismeansthat????(u)?uv2and????(v)?vu1.Letusconsiderthreepossiblecases:

(1)????(u)=v1and????(v)=u2.Then????(u)?uvtand????(v)?vutforbotht=1;2inP??.Butthenv??u??(u)andu??v??(v)inP,whichimpliesthatthepair{u;v}blocks??inI.Acontradiction.(2)????(u)=v1and????(v)=u2or????(u)=v1and????(v)=u2inI??.Thiscontradictsthedeÿnitionofamatching.

4K.CechlÃarovÃa,S.FerkovÃa/DiscreteAppliedMathematics140(2004)1–17

(3)????(u)=v1and????(v)=u2.Sincev2??u????(u)=v1andu1??v????(v)=u2,wehaveu v.But,thedeÿnitionof????implies(u1;v2)∈????,acontradiction.

Toprovetheconverseimplication,letusdeÿneforastablematching????inI??amatching??inIasfollows:if(x1;y2)∈????inI??(noticethatinthiscase(y1;x2)isnotastablepairinI??),then{x;y}∈??inI.Obviously,??isamatchingforI.Nowsupposethat??isnotstable,i.e.,thereexistsablockingpair{u;v}for??.Then??(u)?uvand??(v)?vuandso??(u)t?uvsand??(v)t?vusfort;s=1;2whichimpliesthat????isnotstable,acontradiction.

AconverseofTheorem4isnottrue,i.e.thereareinstancesoftheSCPforwhichitisnotclearhowtodeÿnea‘corresponding’instanceoftheSRP(seeExample1);orthiscorrespondinginstanceisquitenatural,buttheSCP-matchingsdonotleadunambiguouslytoSRP-matchings,asisillustratedbythefollowingexample.

Example2.ConsiderthefollowingpreferenceproÿlesfortheSCPwithtwopartici-pantsa;b.

P1:P(a)=b1,P(b)=a1.P2:P(a)=b1;b2,P(b)=a2;a1.P3:P(a)=b1;b2,P(b)=a1;a2.

Obviously,toallthreepreferenceproÿlesonlyonepreferenceproÿle

P:P(a)=b;

P(b)=a

fortheSRPcanbeassigned;givingauniquestablematching??={a;b}.Nevertheless,P1doesnotadmitanymatching,forP2thereisauniquestablematching??2=??{(b1;a2)},whileinP3therearetwostablematchings??3={(b1;a2)}and??3={(a1;b2)}.

4.Thestablecrewsalgorithm

InthissectionwealwaysconsideraninstanceoftheSCPwithstrictpreferences.ThealgorithmdescribedinthissectionisanextensionofIrving’sclassicalStableRoommatesAlgorithm,see[3,2].Thereforeletusnowrecallthisalgorithminbrief.TheStableRoommatesAlgorithmstartswithaso-calledconsistentpreferenceproÿle(apreferenceproÿleisconsistent,ifforeachpairofparticipantsx;y∈N:x∈P(y)ifandonlyify∈P(x))anditconsistsoftwophases.Phase1isbasedonasequenceofproposals.Afreeparticipant,sayx,proposestotheÿrstparticipantinhislist,sayy.Asaresult,participantxbecomessemiengagedtoyandydeletesalltheparticipantsworsethanxfromhispreferencelist.Phase1terminateswhensomepreferencelistbecomesempty(thenthegiveninstanceoftheSRPhasnostablesolution)orwhentherearenomorefreeparticipantsleft.Ifonterminationeverypreferencelistcontainsjustoneentry,thenthereducedproÿleconstitutesastablesolution.Otherwise,thealgorithmproceedswithPhase2.

K.CechlÃarovÃa,S.FerkovÃa/DiscreteAppliedMathematics140(2004)1–175

InPhase2pairsofparticipantsarefurtherdeletedfromtheproÿlebymeansofrotationelimination.(Thenotionofarotationwillbeexplainedlater.)TheterminationconditionsforPhase2areidenticaltothoseforPhase1.DuetothefactthattheSCP,incontrasttotheSRP,considersparticipantsinroles,weneedtoincorporatecertainmodiÿcationsandrevisionstoIrving’soriginalalgo-rithm:

(1)Werequireastrictlyconsistentproÿleastheinputtothealgorithm.(2)Phase1is,apartfromtechnicaldetails,identicalwithPhase1ofIrving’salgorithm.(3)Phase2isanalogoustoIrving’sPhase2,butweintroduceanewelement,calledthedoublefavouriteelimination.

Everyproÿlegeneratedduringtheexecutionofthealgorithmwillbereferredtoasareducedproÿle.ForagivenreducedpreferenceproÿleTandaparticipantx,theÿrst,thesecondandthelastparticipantintherespectiverolesinx’spreferencelistPT(x)willbedenotedbyfT(x);sT(x)andlT(x),respectively.(Iftheproÿleisclearfromthecontext,thenthesubscriptsindicatingtheproÿlecanbeomitted.)

4.1.Strictconsistency

ThenotionofstrictconsistencyisageneralizationofconsistencydeÿnedfortheSRP.

Deÿnition5.Let{N;P}beaninstanceoftheSCP.WesaythatapreferenceproÿlePisstrictlyconsistent,ifforallparticipantsx;y∈Nandt∈{1;2}thefollowingholds:(i)xt∈P(y)ifandonlyify3?t∈P(x).(ii)ifyt;y3?t∈P(x)andyt??xy3?t,thenxt??yx3?t.

Thesecondconditionisimpliedbytheconsiderationthatifyt??xy3?t,andx3?t??yxt,thenthepair(xt;y3?t)isalwaysblockedbythepair(yt;x3?t).Weshallsupposethattheinputpreferenceproÿleisstrictlyconsistent(whichisotherwisetrivialtoachievebyappropriatedeletions).Inthealgorithmeverydeletion,e.g.deletionofxtfromP(y),alwaysmeansdeletionofthepair(xt;y3?t),i.e.y3?tisalsodeletedfromP(x)thuspreservingstrictconsistency.

Example3.Considertheinstance{N;P}oftheSCPwiththesetofparticipantsN={a;b;c;d;e;f}andthepreferenceproÿleP:

P(a)

P(b)

P(c)

P(d)=d1;f2;b1;d2;b2;e1;e2;f1,=c1;c2;a1;e1;e2;a2;d1;f2,==d2;e2;b1;e1;f1;b2,b2;f1;c1;a2;e1;f2;e2,