on N. Each item has a size and an associated weigh

Partially-OrderedKnapsackandApplicationstoSchedulingStavrosG.Kolliopoulos∗GeorgeSteiner†AbstractInthepartially-orderedknapsackproblem(POK)wearegivenasetNofitemsandapartialorder≺PonN.Eachitemhasasizeandanassociatedweight.TheobjectiveistopackasetN′⊆Nofmaximumweightinaknapsackofboundedsize.N′shouldbeprecedence-closed,i.e.,beavalidprefixof≺P.POKisanaturalgeneralization,forwhichverylittleisknown,oftheclassicalKnapsackproblem.Inthispaperwepresentbothpositiveandnegativeresults.WegiveanFPTASfortheimportantcaseofa2-dimensionalpartialorder,aclassofpartialorderswhichisasubstantialgeneralizationoftheseries-parallelclass,andweidentifythefirstnon-trivialspecialcaseforwhichapolynomial-timealgorithmexists.WealsocharacterizecaseswherethenaturallinearrelaxationforPOKisusefulforapproximationbutwedemonstrateitslimitationsaswell.Ourresultshaveimplicationsforapproximationalgorithmsforschedulingprecedence-constrainedjobsonasinglemachinetominimizethesumofweightedcompletiontimes,aproblemcloselyrelatedtoPOK.1IntroductionLetapartially-orderedset(poset)bedenotedasP=(N,≺P),whereN={1,2,...,n}.AsubsetI⊆Nisanorderideal(oridealorprefix)ofPifb∈Ianda≺Pbimplya∈I.Inthepartially-orderedknapsackproblem(denotedPOK),theinputisatuple(P=(N,≺P),w,p,b)wherePisaposet,w:N→R+,p:N→R+,andb∈R+.ForasetS⊆N,p(S)(w(S))denotesPi∈Spi(Pi∈Swi).WearegivenaknapsackofcapacitybandthesoughtoutputisanidealN′thatmaximizesw(N′)andfitsintheknapsack,i.e.,p(N′)≤b.Aρ-approximationalgorithm,ρ1,findsanidealN′suchthatp(N′)≤bandw(N′)isatleastρtimestheoptimum.WeoccasionallyabusenotationanddenoteaposetbyN,oromitPfrom≺Pwhenthisleadstonoambiguity.ForsimplicityweshallalsosometimesdenoteaPOKinstancebyNwith≺P,w,pimpliedfromthecontext.POKisanaturalgeneralizationoftheclassicalKnapsackproblem.AninstanceofthelatterisaPOKinstancewithanemptypartialorder.JohnsonandNiemi[15]viewPOKasmodeling,forexample,aninvestmentsituationwhereeveryinvestmenthasacostandapotentialprofitandinwhichcertaininvestmentscanbemadeonlyifothershavebeenmadepreviously.POKisstronglyNP-complete,evenwhenpi=wi,∀i∈N,andthepartialorderisbipartite[15]andhencedoesnothaveanFPTAS,unlessP=NP.Toourknowledge,thisistheonlyhardnessofapproximationresultknown.However,theproblemisbelievedtohavemuchmoreintricatestructure.Thereisastraightforwardapproximation-preservingreductionfromthedensestk-subgraphproblem(DkS)∗DepartmentofComputingandSoftware,McMasterUniversity,Hamilton,Ontario,L8S4K1,Canada([e-mail]).ResearchpartiallysupportedbyNSERCGrant227809-00.†ManagementScienceandInformationSystems,McMasterUniversity,Hamilton,Ontario,L8S4M4,Canada([e-mail]).ResearchpartiallysupportedbyNSERCGrantOG0001798.toPOK.NoNP-hardnessofapproximationresultexistsforDkSbutthebestapproximationratiocurrentlyknownisO(min{nδ,n/k}),δ1/3[10,1].Recently,FeigeshowedthatDkSishardtoapproximatewithinsomeconstantfactorunderanassumptionabouttheaverage-casecomplexityof3SAT[9].IntermsofpositiveresultsforPOK,thereisverylittleknown.In1983JohnsonandNiemigaveanFPTASforthecasewhentheprecedencegraphisadirectedout-tree[15].RecentlytherehasbeenrevivedinterestduetotherelevanceofPOKforscheduling.AnO(1)-factorapproximationforPOKwouldleadtoa(2−β)-approximation,forsomeconstantβ0,forminimizingaveragecompletiontimeofprecedence-constrainedjobsonasinglemachine,aproblemdenotedas1|prec|PwjCj.Improvingontheknownfactorof2for1|prec|PwjCj(see,e.g.,[4],[5],[12],[21],[24])isoneofthemajoropenquestionsinschedulingtheory[25].TherelationshipbetweenPOKand1|prec|PwjCjwasexploredinarecentpaperbyWoeginger[28].Duetotheschedulingconnection,weadoptschedulingterminologyforPOKinstances:itemsinNarejobs,functionwassignsweightsandfunctionpprocessingtime.Toourknowledge,WoegingergaveaftermanyyearsthefirstnewresultsforPOKbyshowingpseudopolynomialalgorithmsforthecaseswheretheunderlyingpartialorderisanintervalorderorabipartiteconvexorder[28].InthispaperwepresentbothpositiveandnegativeresultsforPOK.Ourpositiveresultsarebasedonstructuralinformationofposets.Oneofthemainapplicationsofposetsisinschedulingproblemsbutthereareonlyafewrelevantresults(e.g.,[6],[12]).Moreover,theseresultsareusuallyderivedeitherbysimplegreedyschedulingorbyrelyingonanLPsolutiontoresolvetheordering.However,alargeamountofcombinatorialtheoryexistsforposets.Tappingthissourcecanonlyhelpindesigningapproximationalgorithms.Followingthisapproach,weobtaincombinatorialalgorithmsforcomprehensiveclassesofPOKinstances.Theseleadtoimprovedapproximationalgorithmsforthecorrespondingcasesof1|prec|PwjCj.Perhapsironically,wethenshowthatthenaturalLPrelaxationforPOKprovidesonlylimitedinformation.ThefirstpartofourpaperdealswiththecomplexityofPOKontwoclassesofpartialorders.First,wegiveanFPTASforPOKwhentheunderlyingorderis2-dimensional.Second,wegiveapolynomial-timealgorithmforaspecialclassofbipartiteorders.2-dimensionalorders.InSection2weprovideanFPTASforPOKwhentheunderlyingorderis2-dimensional.Itachievesa(1−ε)-approximationfortheoptimumweightwhilemeetingtheupperboundontheprocessingtime.Weproceedtogivebackgroundon2-dimensionalorders.AlinearextensionofaposetP=(N,≺