Plongements Métriques et Algorithmes

De
Publié par

Niveau: Supérieur, Master, Bac+5

  • mémoire


Plongements Métriques et Algorithmes d'Approximation Mémoire de M2 Arnaud de Mesmay Septembre 2010 Sous la direction de James R. Lee

  • algorithmes d'approximation

  • théorie de la complexité

  • algorithme du simplexe

  • solution optimal

  • graphe quelconque

  • couverture optimales de graphes

  • problème d'optimisation np

  • plongement d'arbres arbitraires


Publié le : mercredi 1 septembre 2010
Lecture(s) : 46
Source : di.ens.fr
Nombre de pages : 41
Voir plus Voir moins

brePlongementsLeeM?triquesdirectionetyAlgorithmesSousd'ApprJamesoMesmaximaSeptemtion2010M?moireladedeM2R.Arnaudde‘1
‘1
.TI?RES.1.T.able.des.mati?res.1.Inbtroourduction.2.2.Algor.ithmes.d'iapp.r.o.ximation.4.2.1DESRelaxations.lin?airesR?ductionet.semi-d?niesCas.....l'arbre.........Mesma.......ossibili.........R?duction.........T.......5.1........45.22.2completComplexit?.des.algorithmes.d'approPlongemenximatio.n........de.Searc...........4.3.?.espaces...............24.dimension......7.3.Plongem.en.t24sdimensionm?tri.ques.10.3.1.In.tro.duction25auxarbresplongemenprobabilistests.m?triques................t.r...............32.d'arbres.a.................A.1013.2NeighConstructionordehplongemen.ts..................22.Imp.t.p.d'autres.................................4.3.1.de.dans.ABLE..12.3.3.Sparsest.Cut....................4.3.2.deMAdans...............................5.des.31.Pr?liminaires............................15.4.R?duction.de.dimension3119Plongemen4.1deLemmebinaideeJohnson-Lindenstrauss..............................5.3.t.arb.tr.ires..........................19.4.2.Probl?mes.de35prodeximyit?M?moireetM2Nearestalgorithmes1.troIncommentroRemerciemenductionv2des1troisi?meInaientrot,ductionvL'obpjetmotivdesceEnn,m?moireunestd'optimisatiodeinpr?senseterol?enneunPCPs,panoramaLesdesordip?rendonteslin?airestecdeuxi?mehniquesadelesploR.nrgA.ementtseg?ao-l'?tenduem?triquesnotammenappliqu?eshniques?partirl'informatiquepth?orique.RC'estdeundedomaineladeCerec?t?hercon.heth?orie?lecturel'activit?ttoujoursolgrandissang?n?ralete,oncommedimensionenprobl?met?moigneelleleecnomtbreceimpWortanVtexpdeconf?rences/wprogrammorkshopsdequiLaluilasonpartconnectivit?unique-ossiblemenquelquestqu'eeur?sconsacr?sth?orie(marsainsi2002,ourieao?tconstruction2003,Gamesune?journ?eexhaustivauKKMOwporkshopFBarriers?ricateursinproCrio?mputaa[tcommeim?triquesond?-Complexitd'approyleIviennenIespaces?traiteronsprpartieid'approncetonutilisanenainsiao?tcomplexit?2010)troettslaleurfoisonsestdeshniquesarticlesossibilit?quimeluibsonexptr?ductionplusloppouemoinsremereli?esondanspleshercprincipaleUnivsainsiconf?rencesetd'informatiquequith?oriqueduit(FJeOCS,2STOC,tecSOD(programmationA).semi-d?nie)L'id?eladeplupartd?partximation.dedestoutesnotammencessptecthnilienqecuesceux-ci.estestl'observcouvriratiosujetntsqu'enonmceunissantn?raleunPCPgraphelesqudeeblconquedansder?ductionslaladistanceNousdeyplusABcourtunecdeshemin,?onettransformeg08savnaturel'analysefpodesnoptimaux.damtre-exemplesenenantalemeg?om?n(sous-)riemannienne.tconsul-comebinatoiretationenAssafunl'ICMob].jetestblaeaucoupenplusvg?oti?remenm?trique.eloppCettelesid?e,tquin'estinettervienhistoriquestdenaturellemencaletBanaclnousorsGuidequeLal'onunecauxhercethetec?desrsem?sur-desoudretelsdesNousprobl?mesladeplnaturedansplusainsiouatmoinsSpm?triques.surleslesr?ductiongraphesleur(plusd'autrescourteccprincipalehemin,NearestarbreSearcdederni?reSteiner,unevhniqueodimensionyd?vageuradR.eMohammedcommerce),.fournitcdeprincipauxfa?on??tonnanquitedelesdemeilleurslorsr?sultats?pyour?desu'?prPoblColin?mesrfondamenatalemenintdecomdebinatoires?galemencommeMesmaceuxdedeLescouphniquesesn(lin?aire,Max-Cutation,sonSp?arbasesestlaCutdes)d'approetdeth?oriecouvgraphes,erturet(tVerth?orieteectralexterviennenCodeverleur).directC'estvcettelaconnexiondefrappan?videmmenteilqueimpndeotouteudusetexp?l?menoseronsneici,r?ttradansvtexte,erstessenLatiellg?emendest?ricateursdeux,exemplesque?teclad'analysepFort?erconsid?rableo:utilis?esd'unelapartdescelui?dedeSpUniquearConjecture.sren-eostonsCut[,]o?ourlath?orieconnexioneestth?or?mesexpliciteetet[fournit]les[meilleursaalgorithmes]connourus,oirettd'autredepartourierdansermetl'exemplcr?erevdePCPstecconhniquessophistiqu?sdevr?ductiontdeladimension,tquiesonOntourrauneterapplicationcspsujetectaculairepr?sendesqu'enph?nom?nesfaitecNaon?tre-in2010tuitifsNaodelatexteg?om?trieconstruitensigrandeth?oriedimension.plongemDetsparasaaitnatureenm?me,tc'estvun?edomaineourdealgorithmesrecximaherciheCesitu?pas?cas,l'inlesterfaceationsenprotretl'informatiquelaetlolesdesmath?matiquesdeeth,cetmne?moirepas.iden.cpremi?relutconstituedesintecductionhniquesalgorithmesdeximation,nomnotammenbreuxauxdomaineshniques:trelaxationsL'algorithmiqueouesti-d?nies,bienqu'uns?rvomnipr?senrapidete.ladeLaalgorithmeth?o.riniduisonseth?oriededeslaongemencomplexit?m?triquesplaermetpartied'obtenirquedesapplicbiornes?inf?rieures,arconstituanCuttLaautand?critttecd'obdejectifsde?ouatteindre.impdansLesespaces,probabilvit?scomsonapplicationtleprimordialesdedansNeighleordeh.slaipartiegnoseetnouvl'anateclydeseded'algorithmes,dansausarbressiebien?elesvprobabi-Jameslit?sLeediscr?testqueMoharrami.contstinMesues,rlaiemenm?thosdevprobabilistetouJameslesLeemartingales.m'aermisLad?couvrirg?om?triedomainederecgrandehedimensiod'nstage,laetersitnotammenoftashingtonlesSeattle,ph?nomq?nesPiedereconcenansutration?ricdedelaerdi?mesure,esonm'ytvlatcl?troplorsourmoncomprendreos?unema?trise.bremercieonnetpartiededesyth?or?mesM?moirepr?senM2t?s.ainsi1.c?t?Inacctrodeductionour3ordonn?MohammedMesmaMcoharrDurandamvietdonstagetA.l'in3tuitiond'od?routancasions,tequ'Arnaudm'ap?vit?adeoirnomept?breuxcofaux-pasceetdu?clair?parisien.endeunygrandM?moirenomM2bre

A "> 0 A (1 +")" "
ationcroissanoutiltecommendesunsyst?mesP=NP),danslatousprogrammationlesteldomainedesondem?triques,laagranviedanscouranunteerendC'estindispvensabletelaemd?couvouvragesertenaturellemend'alordgorithmesersp.ouretr?soudreptouteMesmauneUngpammeadepprobl?mesximationcomAlgorithmesbinatoires.espaceEntparticultrerier,?videmmenles?sprobl?mesedits[d'optimisationetdiscr?teg?om?triques,constituencetsonunsurcmhallengeappara?tconsid?rableetenl'algorithmeinformatique,th?o-srique,tecar,dplaourd'aunenbsonned'appropartiearbitraired'encomplexit?treel?eux,apprleurd'algorithmesr?solutionourexactealgorithmeestcomme(tr?sdeprobablemensact)eimpthossiblepenatemps-apr?s.pbitionolynomial.panoplieL'exempledeslecplusec?l?breVdeestprobl?meaud'optimisationalNP-compleenitl'outilestleprobablementrotpharesceluirogramdu,vg?om?triqueovyis?menageurecdeSpcommerce,?maislitiellayr?soudreenexpacas,unedesmt?rieur,ultitude,r?soudreparmiplesquelslaondepesteutauparsolutionexempled'approciterpceluiNP-completduunsettanalecune?endos,tlesolynomiale.probl?meestsPTdePolynomialcoupschemeeseouolynomiauxdequecouv2ertureimoptimalesxded'apprographes,exempleceuxydedanscoloriageououdos,debreuxsatisfactionn'endeetconorietrainth?or?mestes.deL'impn'yortance(saufdoiresectiontouspascescouvrirprobl?mestjustied?vlelebd'approesoinourradeulco?nltournerr?f?rencecette]NP-c].ompl?tudemond'unelafa?onoinouded'unefonautreinendesrelaxannotammentplongemenl'uneconstituendeseurtroisNouscompd'osantectesdomained'unlaalgorithmelin?aired'optimsemi-d?nieisationinsistan:dimceux-citradoivexemples,entttrerenlath?oriea?treg?om?trierapides,l'analyseablesrsestetRelaxationsceirsurLatoutesconstituelessinstancesoptimisation.qu'onsimplexe,leprimeuruprprogrammefournit.uneSinendanspirecertainsautrcas,bas?srelaxerhniqueslatpremi?reerme(entautorisaninstancetenunRapptempsabexpA.onen4tiel)dontouvaleurla?troisi?mefacteur(enplusespd'une?ranoptimale.talgorithmequeximatiol'onid?alneourtomprobl?mebeetpasalgorithmesurermunetinstanceximerdicileprobl?m,?parpr?cisionexempletoutlorsqu'onconservutilisenl'algorithmeunedupsimplexeUnpr?sultatourappr?soudreununASprobl?meourdetimeprogrammaoximationt:iunonfamillelin?aire),ppAlgorithmesermettelsd'obtenirpuntoutr?sultat4ppro,L'automatisationestapprounCertainsd'ond'approdescsatisfaisanximation.t,probl?mesl'approtctelsheh?mascouranximation,teparestleplutotodeageurs'attaquercommerce?unlaeuclidienseconde.leEn?eet,maisdansnomdeautrnomsbreuxoncaspas,d'application,latrouv?err?cenunedessolutionPCPoptimaleermetn'estmonpasqu'ilindienspaspsiensablevetcil'onCettepn'aeutttr?sl'ambiendeseexhaustivconentenlaterd'outilsd'uneeloppbdansonne.domainePalgorithmesarximation,exemple,pleplutotponsroblt?merdectrouvtitreeresunedecoup[eazmaximaleoudansSWunL'id?eprobl?mededetrerptamiserptittl'analyseitelsonnemengorithmesttdetgraphestervestrNP-comploutilset,etmaistsidesl'obtsjectifquiesttd'encod?duiredeunm?moire.algorithmeindeduisonstabyplesehniques'diviserdupqueourtr?gner',ponmationpeteutprogrammationtr?ssbienensetsatisfaireleurd'uneensionb?ovnquelquesneaapproanximationdedeonlapr?ccoupteconnexionoptimale.teOnvestlaainsiquinaturellemendanstdeamen?a?Cutd?nir2.1lalinnotionasuivesasemi-d?niesnprogrammationtein?aire:un[2.A]eD?finitionsen(AenlgorithmeSid'apprduoximquiatlaion)historiqueUnheuristiquealgoriourtunhmelin?aired'a2.complexit?-appro-oximationtiellepleourdesund'preobl?mealgorithmes,d'optimisationsuresttecundealgorithmeoinenintempspptolynomialnquideprtouteodeduitlin?aireptempsourolynomial.touteselonsles'instancordesformedudepryobl?meM?moireuneM2solutiond md;m 1 c2R b2R A md
dx2R
hx;ci
Ax b
x 0
Pd
c xj jj=1Pd
a x b i = 1:::mi;j j ij=1
x 0 j = 1:::dj
C (A ) S nn bi 1im n i
X
hC;Xi
8i2 J1;mK; hA ;Xi =bi i
X2Sn
X 0
X 0 X
2x =x x 2f0; 1gi ii
wij
P
1 w (1 y y )ij i j2 (i;j)2E
8i;y 2f 1; +1gi
unpeut,detesti?res.trainRonetcconditionslesd'exprimerSousdesMaximiserqui,obl?mepestouroin:cenermeti(cioureetcoeformulerouverOneamatricainsialeer?sultatensuivl'ellipso?de.ancta:quetoutgrprobl?meerd'optimisatio)nobl(malesxdansilesmisationelsouprminimisation)signielin?aireMaximisersoumisc?formedesgrconlortrainottesSoientlin?airestermepeneutun?tretempsr?solum?thoenctempsdepdeolynomial.auLetr?sultatconestunefstandaroerptconsistanmaismaximalenedess'ap-enpliquesemi-d?niequeodicilemen:ttesauxAlgorithmesprobl?mcesesd'optimiMaximisersrav?rieteideonammationdiscr?teouver:v?rieceux-civeonSousttrainendeci?etlin?desprparam?treslene.vlaanrsignieipan.tenqueerdansDedesprogrammationesemi-d?nisr?solupaco-estdiscretsde(parinexemplel'algorithmelesnen?tiers),petjouterappliquertr?suneletecthniqueprogrammdeecprogramma-testionarlin?airete?Soientcesformprobl?messtipulerfournitlin?le.risquepard'obtenirprobl?medes?solcouputuniond?r?onsprfractionnaires,unequidnederepr?senMaximisertend'unt(ExprrienD?finitranspprogrammeos?sonau5probl?mexconsid?r?.trainIlonest(ensemblealorsmatricn?cessairesym?triquesd'arrondirSousl)adessolution?obten:ue.en?soudrunelesolu-obl?metionprengrti?re,semi-d?nieettrtouteunlaquidicult?:decteurl'analyseunesttrdelesmonontrertesqueestl'onstandarn'asouspasassotropairpammationerduoendeapproprximationslorsAdeecetteo?phasend'arrondissemenatiot.uneLa,tecquehniqueestdeositiverelaxationalin?aireLeasemi-deniteuneanglaislimitationsup?videnutefran?ais:m?mlqu'eneslin?aire,conprogrammetrainptes?tresurenlespdi?renlynomialrutilisanA.uneMesmade5pdettt?rieur?treommelin?aires,deceL'iqt?r?tuirelaxerlimitedesfortemenquadratiquestermetl'expressionradedesnomonditionsbreuxstrictesprobl?mprogramme,esrapprocomhanbinatoiresfortemenend'untermesedevtelsdesprogrammes.trainUneeng?n?ralisationPnaturelleexemple,estconditioncellellede.lad)programmationesemi-d?nie,ppdeermettanentairdeammationspo?cierCeladesermetconexempletrainletesMAX-CUTquadratiquestautrouvlieuunedeelin?aires.dans[2.C]grapheD?finitionp(Exprparessionfacteursd'undeprcommeobl?meinstancedeti?repr'oprobl?megrprogrammationammation:semi-d?nie?meenprformenstan-essidarond)tSoit[2.B]eutlin?aireetSouspcontrainexplicite,d'unplusationeimmani?rd'approDe2.testsdepara-ym?tresM?moiredoivM2enU =fi;y =i
1g V =fi;y = +1gi
P1 w (1 v v )ij i j(i;j)2E2
8i;v v = 1i i
n8i;v 2Ri
v vi j
H S
1(i;j) S arccos(v v )i j
H
v vi j

0:878
X (i;j) 1 (i;j) S 0i;j P
W = w Xi;j ij(i;j)2E
X 1
E[W ] = w arccos(v v )i;j i j

(i;j)2E
1 1 arccosxx2 [ 1; 1] arccos(x) 0:878 (1 x) 2 1 x
X1
E[W ] 0:878 w (1 v v )i;j i j
2
(i;j)2E
constituenundonneespaceerplanenquegrande?dimension,etetfournitsonaanalyseconappestellesdoncdeuxnaturellemenopositiontunedesetteconhniquesundedeg?om?triesoitdepass?telst,espaces.planC'estlorscetteparclonnectionaquiMax-Cutjustiear?tel'utilisationlaextensivquieinstancedecesteconsid?r?cdehniquesoidsg?om?triques,pretLanotammenetdededeplongemenctsariancem?triquesprobl?medansvlaLath?oriel'angledesenalgorithmesed'approleximation.it?.Regardons])commen?tnaturecela[2.E].fonctionnepsurl'oncetduexemple.cetteLecetteprogramme6semi-d?niprogrammecorrespIlondandetourpcoupou-ainsivtableauaCene.tt?trelar?soluabilienartempsuspoupolynomial,aronbobtienunt.unL'hsc?tanh?maal?atoiremed'approinximationrotationend'analyserarrondissanltparlebinatoire,r?sultatpuremenqu'ils'estimefourmesurannitretecteurs,divisanc'est-?-dired'unencetransformannt?sasussolution[2.E]fractionnaire[eneuneoximationsolution?end'unti?re,oximationc'est-?-direPreuveunesacoupariableec.compl?temenLavtecc'esthniqueestutilis?eouppetourulationceremarquablefaireimest.remarquableourquoidete-t-ilsimplicit?MAX-CUT:tesilless'agitetsimplemenMaistblde,cduhoisirMaximiserunsemih(dresserypverplanseal?atoireourdansaincre),notrecetteespaceeetnotredegrandeurs?pareralesobptoinqu'unets?teobteng?om?trique.uslsuivcan?tpqu'ilpseaucoupsonnaturetprobl?med'un?c?t?estouPreuvede[2.D].l'autreypdeoncetthoisihnypparerplavnpar.ilD'apparenceutsurprenanletedans(peourquoiengendr?unleshecteursypcomerplantal?atoire.fourniraitprobabilit?uneabenonnetcoupen?),lescettevtecethniquelesetjustiel'angleassezdnaturellemenmi-cercle,tqui:exactemelterprogrammesutendtat?-cminimiserprobl?melaPrgrandeur(xGW95d'approLAlgorithmessch?m2.d'apprenpr,cdoncdent?uneles:pla-apprcerdele.plusdeloinSoitl'untransform?devl'autreal?atoiresurourlahaquesph?re.tDoncaaquivautecsifournitprobl?me,A.relaxationMesmadans6cdeeypeterplansinon,alsoit?atoireformledanssests?parera.CeSoitationdoncPsemi-d?nieOnunalorshceyprepr?senerplanuneadel?atoire,?etsutl'ontraind?nitcuneSouscoconsid?reru,p.eprelaxationensemdansesnotretgrapheuneoriginaleengraphec,h:o-d?nii-probl?mesissanentletousdelesariationsommetsrelaxeenprobl?mevpos'enyv?sdoncd'uncoupm?medec?t?pdell'hexactemengrapheestdanstplongementypmaximisererplan.?[2.D]eeunetLLemmebdeonneyprobabilit?,M?moireunM2h
1
2
" > 0 (1 +")1
lesaleurd?terminen'esttautreaqueoulaetv?aleurdeoptimis?edeparSetlearprtoegrlea?mmeourraitsemi-d?ni,lequionestunpardenatureelopppluscasgrandprobl?meque?ennelaLevIlaleurdesdedeslaquecouppr?cisionedi?renoptimalela(cartaicdans'enlesestd'autresuneconnaitrelaxation).aD'o?ximaleourr?sultat.d'uneCetteNP-compl?tudeL'ecacit?tousfrdea?plepanetealedequicettousalgorithmePC(a'existevformanisttofs),sacasd?couvnouserte,cluneepmeilleurortemenfacteurdesd'approvximationpuisqu'onconneux.ub?taitageur.uclidien,7c'est-?-dire),uneainsipqueesameilleurscompuneosanEnn,tetg?om?triquetiqu'?mprobableoireoncoloriage.tencplonetribu?les?r?sultatsfaireCommedesoutectrainhniquessonbas?esth?oriesuralali?,programmationprobl?me,semi-d?nieulelesntecl'onhniqaleuruebreslequellesximabilit?,plusTh?or?mep],oind'approtuesolynomialdansCeletedesignesd'algorithmes-d'approChecximation,nett?rac-dsousod?couvn?cximabilit?".?ermetrendreetn?cessaired'inapprounedescompr?her?sultatsnsM?moireiextr?memenonppr?cisequ'ondesenserph?nom?nesexactemendeeg?omeut?trieenencehauteprdimension?mes,(siol'analyseciespacecioss?denestPTtr?sprudimenximertaire,sceenn'estPpasVertoujoursCole,cas).queUermettennximationdesconstanoutilsprobl?messenparetielsdicilesd'analyseverdealgorithmescesialgorithmesfacteursesttr?e,cpireeluiprobl?mesdesr?sultatsplongemenmettentslam?triques,bieqsuiefournissendetvunehabituelles,connectionfourniraitdirectepdansprobl?mesl'exempleourdelaSpesardesSaeSastessenCfondationutleenontret?resserlaecomtitul?binatoireDansdesdonngraphesuneetolaformeg?om?trierene,hautehercdimension.uneL'obvjetledetermeslahistorique,partiefonden3.r?sultatsestled'exp.osore[rDin07cetteunvconnection.qu'il2.2asComplexit?Algorithmesdesquealgorithmesad'ap?quivproleximationeLa?riablesrqetc:hercablehessurunelesesalgorithmesesd'approetximationanglesord'maisest,miteronscommeoc'estc?t?souvpuissanceencomplettceleprobl?mcas,fournirdivis?edeen?deuxppartiesclassiques.:obtenird'uneforts,partylesM2algorithmicitsenstctshercourhanprobl?mestp?ptrouvaeroirdtem?mscomplexit?,algorithmesptoujourstousplusr?duirepuissantretsAinsi,prournsapprooximerldescommeprobl?mesvcl?s,yd'autredepartommercelesuncehercpheurstenscomplexit?AS,(qu'onquieutsapproo?npr?citisouvarbitraireentempstolynomial.lesourm?mescommequetlesxprevermiersMax-Cut!)lesessaalgorithmesyl'onanpttdeappromettre?aufacteurpt.oindestesunepth?oriemmenanalogueplus?commecelleCoden'onladesNP-compl?tuded'approdanstleoncadredesdeslogarithmiquesall'engorithmesvd'approm?meximation.pCettelessectiondeaCespextr?memenourdisparatesbuttde?videncepr?senn?cessit?terth?orielesnprincipauxur?sultatsd?vde?cettequth?oriecelledelalaadicult?ecd'apprr?ductionsoximerc,celle-cimaisdesdeuniformesfa?onourextr?memenlestconsid?r?s.informelle,psansled?monstrations.deEnNP-compl?tude,eet,llesprobl?mesr?sultatssatisfactionquiconsous-tendentetttous3-lestth?or?mestd'approtielsximation,lanotamd'unemeng?n?rale,tpremierleauquelth?or?mevPCPs'in,estsonprobl?mtd'optimisationextr?meminenMax-3Sat.teccehniqueslae?testleurformexpbositionolrigoureusesousd?passe3-largemoenmtconjonctivleetcadrecdehecertexte,vnousdesrenariablesvmaximiseonomydeonssatisfaits.?r?sultatlsur'ouvrseatgeles[d'inapproABest]th?or?mpPCPour[2.F]un(Th?traitemen?metPbAS98eaucoup[plus])compleexistetimduxsujet.telDunationpderni?red'algorithmepoximationd'our2.tp-approinptMax-3Sade,vuemoinsdeP=NP.lath?or?mecompleunexulationialent?,danslelangagesdomaineprdesuvalgorithmesvd'approprobabilximationifrappueemenpar(d'o?sonnom?trangeProbabilisticallyh?t?rog?n?it?.kAlorsProquequilaoth?orietdesg?n?ralisationprobl?mespreuvNP-completsinptivermetauderandomis?,s?parerc'estlescetprobl?mesqu'ilNPd'aben?t?uneert,dicnoushotomilieicitr?sn'?vmarqu?e,querceuxsonqui"inapprosonLatdudansalculPpetd'appliquerceuxr?sultatquid'autressones,tdedanstouteNPgammecompletsr?sultats(?ximabilit?l'exceptionunedearbitrairequelquesouruns),probl?meslaN?anmoins,situationourdesdesalgorithmeplussA.d'approMesmaximation7re?tededescompcn c
16=17 0:94
L =<V;W;E;m;f g >v;w (v;w)2E
EVxW
[m] =f1::mg
: [m]! [m]v;w
c : (V[W )! [m]
(c(w)) =v;w
c(v) OPT (L)
v;w
2x =x mod 72 1
3 + 4x =x mod 73 2
5 x =x mod 74 4
> 0 m =m ()PCP

danssculttatdd'inapprovximabildeit?sui-?ilun(Th?facteurcl'?nonc?.deoverpvouretunvcertaindesimplicit?des,ccetquiontrestobtenirconsid?rablemenptunplusoverfortpque:dansr?sultatsleariancasquedegorithmeMaxtoutes3-Sauntan.leLesenr?sultatsaintes.bas?saissurpluslesatisfaites,th?or?mearPCPdeson,tmefourniactionunsatisfgranduniquenomunbrelededi?renbdeornesleinf?rieurespauxtesprobl?mesam?nend'approdansximci-dessousation,.quiuniquesonytourdanselingcertainstraincasvrejoinettesparpartraindesth?or?mealgorittP)hmyes.que?MaisConjecturedansdeun1.grandquenomossiblebreaintesdeunecas,surilestrestesiunvfoss?papparemmendependenttninfranclehissablelaenmtrontrepleseling.deleoblemuxelr?sultats.oblemPtoutesaraintesexemple,sontdansUnleelcasProblemdeanMax-Cutle,desl'algorithmeapr?sen:t??pr?c?demmenr?ductionsttecobtientr?stdesuncult?sfacteurl'auned'appro.xourielmationproblem,d'enunvironolyn?mial0.878,?rieralorsunque?rianlacor?ductionilobtend'uneuepaoinvremonecgrapheleenth?or?melesPCPuniques.deersionsdonnenousunsuivr?sultat[2.H]d'inappro?meximabilit?toutque,au-del?und'unpfacteurdicile,decteUniqueL'apparenestconsid?r?.plusprobl?meth?or?me,autefoisphaquen[leHas01p].deCeontrcisoientao?amen?cSubashainteKhotune??te?satisfainoncerelar?ductionsUniqueecGamesaConjectureeut[onKho02Set]In-[2.G]OnD?finitionote(Lprobl?abourelAinsi,CfrovermaxiPraleoblem)cUnaintesLaitesabarellabCoverUnPrlaboblemccpr?estadapt?elabth?or?mecceprdedansequeltlesarianontrvts.d'unetd?monstrationdesuneermutations.parexempletLabpassanCodemand?,erestestailsuivvttraSatisfairelongpluscossibleonsiste?quationsenvnDeux1ensemblesextr?memendisjodesintstdeconsid?r?essommetslesV,WhniqueslesUnsubtilesensembletesd'arv?tes:un?nonc?ests,ierconstandesup?formant.unNotonsgrpaphelebiplabartitecorer?ilgauallierppUnvensemblesideexistelablabelsvstfacteurslesdesn?tes,ximationsutopartirapprassignationl'alideourUnpensembletplusdetelterqueleourbilabticsuivprtdeconletesilUneNP-durvdistinguerduePCPIldonneunr?sultatelingansatisf:toutesTh?or?mecortPCainPoursvisagereutnilyaaucuneelingonstantesatisfaitl'onunpr?cisesrd'unecercdelecpontrleainteseltover:oblemcteurtailconcernanm,8soitationdeimentrxd'approexisteAlgorithmeslab2.quicasaitselesenon?rexempletede.yIlM?moire'M2aslabtquideplustrfouverauntionlabdeselingontrdesLaarGames?tes(UGC)leuneleersionerfortetrompcepasmdoitrestreinneautr?sOnth?or?meeuunmoc'esttrertellequeg?n?ralpr?duitourfaittoutescetlesA.arMesma?tes.8L'objedectife; > 0 m = m ()PCP
1

[ 1; 1] R
(1)(log logn)
atteint(d'apr?soufacteurtSonPourte,e)decturetConjepartie).Gamesces,ililr?sultatyparaimite).uneqcdeonstantecanonique(Uniquel'analyseConjecturele[2.I]r?sultats:desproblemeerutilis?vestco9elesttelUniqueledansque[ptour(donleu'uniquetlabpeltscRemarquonsoverinprquoeb?lemlade2.tailourlenmr?ductions,oilg?om?soittreNP-durxded'indistinguerth?or?meentroteneautrementi?remenIlvexistedeun?remenlabueelingtousquitrsatiMax-3SasfaitilaurelaxationmoinsetuneGamesfrd'approactionslabnuetdesd'approcqontrCutalaintes.lad'obtenirIl:nc'yd'approataucunnlabmelingl'ordrequiCosatisfaitProblempluserd'uneximabilit?.frl'outilacttoutesilonourieruniq?enne,des?ciontrlienaintes.fonctionsL?imo?leslesprincipth?or?mesariance,PCPg?n?ralisationnetralpleermettendetConjectured'obtenirplusuneestbd?monornetrd'inapprosubsximabilit?nquevd'un],c?t?spdesestfractionsth?or?mesatisables,g?n?raliselaprobl?mecdeonjectureinestMax-Cutquefonl'onpr?cis?menptreeutexisteen-atelsvsuppoirladesceldeuxunc?t?s.optimal.LelevMax-Cutodecabledesdequiconjecturededeconstancelle-ciin'estourpaspduSptoutquegalvduisonsaud?,suivsaestvGames?racit?p?tanmetprounemondesuegrandesestquestionsaouviertesfacteurduossible,domaine,ersionsm?me?essiam?nendes?recximabilit?hercd'approheselr?cenvtesr[pABS10prouv]unond'inapprotEfaitfait,desphareprogr?sdansnotablescesvesters'analysesaFr?solution.bCetteolconjecturequipreli?eermetlad'obtenirtrdeesler?sultatsend'inapprolesximabilit?deam?lior?sationpdansourettoutgaussienneseleuneclassevdequiprobl?mes.uneTduoutcend'ablord,Maisdanspl'exempletieldelaMax-CutGames,estelletpgrand,ermetil(sienelletesttr?vraie),lesdeamonauxtrer?queuecettsalgorithmeRagha?trangeendraatteignanRag08tparticuliuntfacteurectaculaires.0.878r?sultatestqoptimal.le[2.J]pr?c?denTh?or?mese(?[lesKKMOs])satisfactionSiconlaaUniquetesGamestConjeetcttutrPluset,estmonvrqaie,ilalorsuneilsemiestd?nieNP-Durdedeprobl?mes,trqu'enouosanvvraieerUniqueuneConjecture,solu-le-citiontapprfacteuroxim?ximationeCommepourourcaMAX-CUTdeayant,unutilisemeilfa?oleurcrucialetauxargumend'apprg?om?triques,oximationexpliquenquel'originectoutesel?trangesletesdexGomation.emans-WilpliamsonnirCeuer?sultatourr?vprobl?me?arsestle,unnouslientrodirectdansenpartietreanlac'complexit?encoredesUniqueprobl?mesConjectured'approiximationermetetleslailleursg?om?trie.d'inap-Alorsximabilit?queoncelle-citrn'apparaitqquesidanselle-cil'analysevraie,den'yl'algorithmepasdexGmationounemans-Wiliamson,constanilpestetdesvcasreKV05forcA.deMesmaconjecture9tde?metundansd'inapprolader?ductionde?AlgorithmesunLabn?cessaire[de].ladefaireyapparaitreM?moiredirecM2temen

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.