A Nearly Linear Time PTAS for Explicit Fractional

arXiv:0801.1987v2[cs.DS]13Mar2013ANearlyLinear-TimePTASforExplicitFractionalPackingandCoveringLinearProgramsChristosKoufogiannakis·NealE.YoungAbstractWegiveanapproximationalgorithmforfractionalpackingandcoveringlinearprograms(linearprogramswithnon-negativecoefficients).Givenaconstraintmatrixwithnnon-zeros,rrows,andccolumns,thealgorithm(withhighprobability)computesfeasibleprimalanddualsolutionswhosecostsarewithinafactorof1+εofopt(theoptimalcost)intimeO((r+c)log(n)/ε2+n).11IntroductionApackingproblemisalinearprogramoftheformmax{a·x:Mx≤b,x∈P},wheretheentriesoftheconstraintmatrixMarenon-negativeandPisaconvexpolytopeadmittingsomeformofoptimizationoracle.Acoveringproblemisoftheformmin{a·ˆx:Mˆx≥b,ˆx∈P}.Thispaperfocusesonexplicitlygivenpackingandcoveringproblems,thatis,max{a·x:Mx≤b,x≥0}andmin{a·ˆx:Mˆx≥b,ˆx≥0},wherethepolytopePisjustthepositiveorthant.Explicitlygivenpackingandcoveringareimportantspecialcasesoflinearprogramming,including,forexample,fractionalsetcover,multicommodityflowproblemswithgivenpaths,two-playerzero-summatrixgameswithnon-negativepayoffs,andvariantsoftheseproblems.Thepapergivesa(1+ε)-approximationalgorithm—thatis,analgorithmthatreturnsfeasibleprimalanddualsolutionswhosecostsarewithinagivenfactor1+εofopt.Withhighprobability,itrunsintimeO((r+c)log(n)/ε2+n),wheren–theinputsize–isthenumberofnon-zeroentriesintheconstraintmatrixandr+cisthenumberofrowspluscolumns(i.e.,constraintsplusvariables).Fordenseinstances,r+ccanbeassmallasO(√n).Formoderatelydenseinstances–aslongasr+c=o(n/logn)–the1/ε2factormultipliesasub-linearterm.Generally,thetimeislinearintheinputsizenaslongasε≥Ω(p(r+c)log(n)/n).1.1RelatedworkThealgorithmisaLagrangian-relaxation(a.k.a.price-directeddecomposition,multiplicativeweights)algo-rithm.Broadly,thesealgorithmsworkbyreplacingasetofhardconstraintsbyasumofsmoothpenalties,oneperconstraint,andtheniterativelyaugmentingasolutionwhiletradingofftheincreaseintheobjectiveagainsttheincreaseinthesumofpenalties.Herethepenaltiesareexponentialintheconstraintviolation,and,ineachiteration,onlythefirst-order(linear)approximationisusedtoestimatethechangeinthesumofpenalties.Suchalgorithms,whichcanprovideusefulalternativestointerior-pointandSimplexmethods,havealonghistoryandalargeliterature.Bienstockgivesanimplementation-oriented,operations-researchper-spective[2].Aroraetal.discussthemfromacomputer-scienceperspective,highlightingconnectionstootherfieldssuchaslearningtheory[1].AnoverviewbyToddplacestheminthecontextofgenerallinearprogramming[18].DepartmentofComputerScienceandEngineering,UniversityofCalifornia,Riverside.ThefirstauthorwouldliketothanktheGreekStateScholarshipFoundation(IKY).Thesecondauthor’sresearchwaspartiallysupportedbyNSFgrants0626912,0729071,and1117954.1AcceptedtoAlgorithmica,2013.Theconferenceversionofthispaperwas“BeatingSimplexforfractionalpackingandcoveringlinearprograms”[13].Therunningtimesofalgorithmsofthistypeincreaseastheapproximationparameterεgetssmall.Foralgorithmsthatrelyonlinearapproximationofthepenaltychangesineachiteration,therunningtimesgrowatleastquadraticallyin1/ε(timesapolynomialintheotherparameters).Forexplicitlygivenpackingandcovering,thefastestprevioussuchalgorithmthatweknowofrunsintimeO((r+c)¯clog(n)/ε2),where¯cisthemaximumnumberofcolumnsinwhichanyvariableappears[21].Thatalgorithmappliestomixedpackingandcovering—amoregeneralproblem.Usingsomeofthetechniquesinthispaper,onecanimprovethatalgorithmtorunintimeO(nlog(n)/ε2)(anunpublishedresult),whichisslowerthanthealgorithmherefordenseproblems.Technically,thestartingpointfortheworkhereisaremarkablealgorithmbyGrigoriadisandKhachiyanforthefollowingspecialcaseofpackingandcovering[9].Theinputisatwo-playerzero-summatrixgamewithpayoffsin[−1,1].Theoutputisapairofmixedstrategiesthatguaranteeanexpectedpayoffwithinanadditiveεofoptimal.(Notethatachievingadditiveerrorεis,however,easierthanachievingmultiplicativeerror1+ε.)ThealgorithmcomputesthedesiredoutputinO((r+c)log(n)/ε2)time.Thisisremarkableinthat,fordensematrices,itissub-linearintheinputsizen=Θ(rc).2(Foramachine-learningalgorithmcloselyrelatedtoGrigoriadisandKhachiyan’sresult,see[5,6].)Wealsousetheideaofnon-uniformincrementsfromalgorithmsbyGargandK¨onemann[8,12,7].Dependenceonε.BuildingonworkbyNesterov(e.g.,[16,17]),recentalgorithmsforpackingandcov-eringproblemshavereducedthedependenceon1/εfromquadratictolinear,attheexpenseofincreaseddependenceonotherparameters.Roughly,thesealgorithmsbetterapproximatethechangeinthepenaltyfunctionineachiteration,leadingtofeweriterationsbutmoretimeperiteration(althoughnottothesameextentasinterior-pointalgorithms).Forexample,BienstockandIyengargiveanalgorithmforconcurrentmulticommodityflowthatsolvesO∗(ε−1k1.5|V|0.5)shortest-pathproblems,wherekisthenumberofcom-moditiesand|V|isthenumberofvertices[3].ChudakandEleuteriocontinuethisdirection—forexample,theygiveanalgorithmforfractionalsetcoverrunninginworst-casetimeO∗(c1.5(r+c)/ε+c2r)[4].ComparisontoSimplexandInterior-Pointmethods.Currently,themostcommonlyusedalgorithmsforsolvinglinearprogramsinpracticeareSimplexandinte