资源描述：
《3CVP Algorithm》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、TelAvivUniversity,Fall2004Lecture3Lecturer:OdedRegevLatticesinComputerScienceCVPAlgorithmScribe:EyalKaplanInthislecture,wedescribeanapproximationalgorithmtotheClosestVectorProblem(CVP).Thisalgorithm,knownastheNearestPlaneAlgorithm,wasdevelopedbyL.Babaiin1986.It2n
2、obtainsa2(p)approximationratio,wherenistherankofthelattice.Inmanyapplications,this3algorithmisappliedforaconstantn;insuchcases,weobtainaconstantapproximationfactor.Onecandefineapproximate-CVPasasearchproblem,asanoptimizationproblem,orasadecisionproblem(wherethelat
3、terisoftenknownasagapproblem).Inthefollowingdefinitions,°¸1istheapproximationfactor.Bysetting°=1weobtaintheexactversionoftheproblems.DEFINITION1(CVP°,SEARCH)GivenabasisB2Zm£nandapointt2Zm,findapointx2L(B)suchthat8y2L(B);kx¡tk·°ky¡tk.DEFINITION2(CVP°,OPTIMIZATION)Gi
4、venabasisB2Zm£nandapointt2Zm,findr2Qsuchthatdist(t;L(B))·r·°¢dist(t;L(B)).DEFINITION3(CVP°,DECISION)GivenabasisB2Zm£n,apointt2Zmandr2Q,decideifdist(t;L(B))·rordist(t;L(B))>°¢r.2nBabai’snearestplanealgorithmsolvesthesearchvariantofCVP°for°=2(p).Itiseasy3toseethatth
5、isimpliesasolutiontotheothertwovariantsofCVP°astheyarenotharderthanthensearchversion.Forsimplicity,thealgorithmwepresenthereachieves°=22.Itispossibleto2nachieve°=2(p)byastraightforwardmodificationoftheparameters.31TheNearestPlaneAlgorithmThealgorithmhastwomainstep
6、s.First,itappliestheLLLreductiontotheinputlattice.Itthenlooksforanintegercombinationofthebasisvectorsthatisclosetothetargetvectort.ThisstepisessentiallythesameasoneinnerloopinthereductionstepoftheLLLalgorithm.INPUT:BasisB2Zm£n,t2ZmnOUTPUT:Avectorx2L(B)suchthatkx¡
7、tk·22dist(t;L(B))1.Run±-LLLonBwith±=342.bÃtforj=nto1dobÃb¡cjbjwherecj=dhb;~bji=h~bj;~bjicOutputt¡bItcanbeseenthatthisalgorithmrunsinpolynomialtimeintheinputsize;indeed,theLLLprocedurerunsinpolynomialtimeandthereductionstepwasalreadyanalyzedinthepreviousclass.Noti
8、cethatunlikeourdescriptionoftheLLLalgorithm,hereweconsiderthealgorithmforarbitrarylatticesthatarenotnecessarilyfull-rank.Thiswill,infact,makeouranalysisslightl
