文档介绍：,algorithms,runtime,hardness(puterscience)VincentConitzerSetCover(acomputationalproblem)Wearegiven:AfinitesetS={1,…,n}AcollectionofsubsetsofS:S1,S2,…,SmWeareasked:FindasubsetTof{1,…,m}suchthatUjinTSj=SMinimize|T|Decisionvariantoftheproblem:weareadditionallygivenatargetsizek,andaskedwhetheraTofsizeatmostkwillsufficeOneinstanceofthesetcoverproblem: S={1,…,6},S1={1,2,4},S2={3,4,5},S3={1,3,6},S4={2,3,5},S5={4,5,6},S6={1,3}VisualizingSetCoverS={1,…,6},S1={1,2,4},S2={3,4,5},S3={1,3,6},S4={2,3,5},S5={4,5,6},S6={1,3}136542AlgorithmsandruntimeWesaw:theruntimeofglpsolonsetcoverinstancesincreasesrapidlyastheinstances’sizesincreaseifwedroptheintegralityconstraint,canscaletolargerinstancesQuestions:Usingglpsolonourintegerprogramformulationisbutonealgorithm–maybeotheralgorithmsarefaster?differentformulation;differentoptimizationpackage();binationsonebyone;…Whatis“fastenough”?Do(mixed)integerprogramsalwaystakemoretimetosolvethanlinearprograms?Dosetcoverinstancesfundamentallytakealongtimetosolve?PolynomialtimeLet|x|bethesizeofprobleminstancex()LetabeanalgorithmfortheproblemSupposethatforanyx,runtime(a,x)<cf(|x|)forsomeconstantcandfunctionf Thenwesayalgorithma’sruntimeisO(f|x|)aisapolynomial-timealgorithmifitisO(f(|x|))forsomepolynomialfunctionfPistheclassofallproblemsthathaveatleastonepolynomial-timealgorithmManypeopleconsideranalgorithmefficientifandonlyifitispolynomial-timeTwoalgorithmsforaproblemn=|x|runtime2n22nrunofalgorithm1runofalgorithm2Algorithm1isO(n2)(apolynomial-timealgorithm)Algorithm2isnotO(nk)foranyconstantk(notapolynomial-timealgorithm)TheproblemisinPLinearprogrammingand(mixed)integerprogrammingLPand(M)putationalproblemsLPisinPIronically,monlyusedLPalgorithmsarenotpolynomial-time(but“usually”polynomialtime)(M)IPisnotknowntobeinPMostpeopleconsiderthisunlikelyReductionsSometimesyoucanreformulateproblemAintermsofproblemB()