资源描述：
《5integer_programming》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、TelAvivUniversity,Fall2004Lecture5Lecturer:OdedRegevLatticesinComputerScienceIntegerProgrammingScribe:IshayHavivInthislecturewepresentanotherapplicationoftheLLLalgorithm,namely,integerprogramminginfixeddimension.1IntegerProgrammingOverviewTheIntegerProgrammingproblem(IP)isthatofdecidingwhetherthe
2、reexistsanintegersolutiontoagivensetofmrationalinequalitiesonnvariables.Equivalently,givenamatrixA2Qm£nandb2Qm,decideifthereisaz2ZnsuchthatAz·b.Yetanotherequivalentformulationis:givenamatrixA2Qm£ndecidewhetherthesetZnfx2RnjAx·bgisnon-empty.Theintegerprogrammingproblemisquitepowerful,andmanycomb
3、inatorialproblemscanbeformulatedasinstancesofIP.Infact,itis‘toopowerful’sinceitisNP-complete,asthefollowingclaimshows.REMARK1Withouttherequirementonanintegersolution(i.e.,ifweallowz2Rn),theproblemisknownasLinearProgramming,andhasapolynomialtimesolution(suchastheellipsoidmethod).REMARK2Therearema
4、nyequivalentformulationsofintegerprogramming.Wecould,forinstance,allowequalitiesinadditiontoinequalities.Moreover,wecouldasktofindanintegersolutionandnotjustdecideifoneexists.CLAIM1TheintegerprogrammingproblemisNP-complete.PROOF:IPisinNPbecausetheintegersolutioncanbeusedasawitnessandcanbeverifiedi
5、npolynomialtime.1WenowprovethatIPisNP-hardbyreductionfromSAT.ASATinstanceisdescribedbyasetofBooleanvariablesandclauses.WereduceittoanIntegerProgramminginstancewiththesamenumberofvariables.Inaddition,foreachvariableviwehavetheconstraints0·vi·1:Foreachclausewehaveaconstraintthatcorrespondtoit;fore
6、xample,fortheclausev1_v3_v7intheSATinstance,wehavetheconstraintv1+(1¡v3)+v7¸1:Clearly,thisreductioncanbedoneinpolynomialtime.Moreover,itiseasytoverifythatifthegivenSATinstancehasasatisfyingassignmentthenthecorrespondingIPinstancehasanintegersolutionandviceversa.2AlthoughitisNP-complete,onemighth
7、opetoobtainefficientalgorithmsforthecasewherethedi-mension(i.e.,thenumberofvariables)isfixed.Forn=1,itiseasytocomeupwithanefficientsolution.However,evenforn=2,thisisnolongerobvious.Inthenextsection,wedescribethecelebratedalgori
