机动车安全技术检验机构检验

Chapter4Partition(1)ShiftingDing-ZhuDu汽车防盗器•GivenasetofnpointsintheEuclideanplane,findtheminimumnumberofunitdiskstocoverthengivenpoints.(x,x)PartitionP(x)aConstructMinimumUnitDiskCoverinEachCell1/√2Eachsquarewithedgelength1/√2canbecoveredbyaunitdisk.Hence,eachcellcanbecoveredByatmostdisks.Supposeacellcontainsnipoints.Thenthereareni(ni-1)possiblepositionsforeachdisk.MinimumcovercanbecomputedIntimeniO(a)222aSolutionS(x)associatedwithP(x)Foreachcell,constructminimumcover.S(x)istheunionofthoseminimumcovers.Supposenpointsaredistributedintokcellscontainingn1,…,nkpoints,respectively.ThencomputingS(x)takestimen1+n2+···+nknO(a)O(a)O(a)O(a)2222ApproximationAlgorithmForx=0,-2,…,-(a-2),computeS(x).ChooseminimumonefromS(0),S(-2),…,S(-a+2).Analysis•Consideraminimumcover.•Modifyittosatisfytherestriction,i.e.,aunionofdiskcoverseachforacell.•Todosuchamodification,weneedtoaddsomedisksandestimatehowmanyaddeddisks.AddedDisksCounttwiceCountfourtimes22ShiftingEstimate#ofaddeddisksShiftingEstimate#ofaddeddisksVerticalstripsEachdiskappearsonce.Estimate#ofaddeddisksHorizontalstripsEachdiskappearsonce.Estimate#ofaddeddisks#ofaddeddisksforP(0)+#ofaddeddisksforP(-2)+···+#ofaddeddisksforP(-a+2)3optwhereoptis#ofdiskinaminimumcover.Thereisaxsuchthat#ofaddeddisksforP(x)(6/a)opt.PerformanceRatioP.R.1+6/a1+εwhenwechoosea=6⌠1/ε.Runningtimeisn.O(1/ε)2Unitdiskgraph1Dominatingsetinunitdiskgraph•Givenaunitdiskgraph,findadominatingsetwiththeminimumcardinality.•TheoremThisproblemhasPTAS.ConnectedDominatingSetinUnitDiskGraph•GivenaunitdiskgraphG,findaminimumconnecteddominatingsetinG.TheoremThereisaPTASforconnecteddominatingsetinunitdiskgraph.Boundaryareacentralareahh+1Whyoverlapping?cdsforGcdsforeachconnectedcomponent11.Ineachcell,constructMCDSforeachconnectedcomponentintheinnerarea.ConstructPTAS2.Connectthoseminimumconnecteddominatingsetswithapartof8-approximationlyinginboundaryarea.ForeachpartitionP(a,a),constructC(a)asfollows:ChoosesmallestC(a)fora=0,h+1,2(h+1),….Existenceof8-approximation1.Thereexists(1+ε)-approximationforminimumdominatingsetinunitdiskgraph.2.Wecanreduceoneconnectedcomponentwithtwonodes.Therefore,thereexists3(1+ε)-approximationformcds.8-approximation1.Amaximalindependentsethassizeatmost4mcds+1.2.Thereexistsamaximalindependentset,connectingitintocdsneedatmost4mcdsnodes.MCDS(Time)2/22)2(a1.Inasquareofedgelength,anynodecandominateeverybodeinthesquare.Therefore,minimumdominatingsethassizeatmost.a2/2MCDS(Time)2/22.ThetotalsizeofMCDSsforconnectedcomponentsinaninnersquareareaisatmost.a3)2(3annaOiiaOiinnaO)()(22)2(istimetotalthecells,allOver.timetakesareainnerinthecomponentsconnectedallforcellintheMCDSsallfindingThennodes.cotainscellaSupposeMCDS(Size)•ModifyamcdsforGintoMCDSsineachcell.•mcds(G):mcdsforG•mcdscell(inner):MCDSinacellforconnectedcomponentsininnerareaConnect&ChargechargeMultipleChargechargeHowmanypossiblechargesforeachnode?Howmanycomponentscaneachnodebeadjacentto?1.Howmanyindependentpointscanbepackedbyadiskwithradius1?115!Eachnodecanbechargedatmost10times!!!charges.10mostatreceivesnodeEachnodes.onmdebewillchanges10mostAtnodes.2tochargeamakecomponentEach.components5mostatconnecttocannodeskkkkShifting3a/(2(h+1))=integerTime=nO(a)2h=2dimesion.anyinintimeionapproximat-)1()/1(2OnWeightedDominatingSet•Givenaunitdiskgraphwithvertexweight,findadominatingsetwithminimumtotalweight.•Canthepartitiontechniquebeusedfortheweighteddominatingsetproblem?DominatingSetinIntersectionDiskGraph•Anintersectiondiskgraphisgivenbyasetofpoints(vertices)intheEuclideanplane,eachassociatedwithadiskandanedgeexistsbetweentwopointsifftwodisksassociatedwiththemintersects.•Canthepartitiontechniquebeusedfordominatingsetinintersectiondiskgraph?Thanks,End