Lovász Local Lemma (LLL) är ett kraftfullt verktyg som ger tillräckliga förutsättningar för att undvika alla "dåliga" händelser, med positiv sannolikhet. En rad resultat har tillhandahållit algoritmer för att effektivt konstruera strukturer vars existens är icke-konstruktivt garanterad av LLL, vilket kulminerar i Mosers och Tardos senaste genombrott [2010] för den fullständiga asymmetriska LLL. Vi visar att utdatadistributionen av Moser-Tardos algoritmen väl approximerar den villkorliga LLL-distributionen, den distribution som erhålls genom konditionering på alla dåliga händelser som undviks. Vi visar hur en känd bindning till sannolikheterna för händelser i denna distribution kan användas för ytterligare probabilistisk analys och ge nya konstruktiva och icke-konstruktiva resultat. Vi visar också att när en LLL-applikation ger en liten mängd slack, antalet omamplingar av Moser-Tardos algoritm är nästan linjär i antalet underliggande oberoende variabler (inte händelser!), och kan därför användas för att ge effektiva konstruktioner i fall där det underliggande beviset gäller LLL för super-polynomiskt många händelser. Även i fall där hitta en dålig händelse som håller är beräknings svårt, visar vi att tillämpa algoritmen för att undvika en polynom-stor "kärna" delmängd av dåliga händelser leder till ett önskat resultat med hög sannolikhet. Detta visas via en enkel förening bunden över sannolikheterna för icke-kärnhändelser i den villkorliga LLL-distributionen, och leder automatiskt till enkla och effektiva Monte-Carlo-algoritmer (och i de flesta fall RNC). Vi demonstrerar denna idé i flera tillämpningar. Vi ger den första konstant-faktor approximation algoritm för Santa Claus problem genom att göra ett LLL-baserat bevis på Feige konstruktiv. Vi tillhandahåller Monte Carlo algoritmer för acyklisk kantfärgning, icke-repetitiva graffärger, och Ramsey-typ grafer. I alla dessa applikationer faller algoritmen direkt ut ur det icke-konstruktiva LLL-baserade beviset. Våra algoritmer är mycket enkla, ger ofta bättre gränser än tidigare algoritmer, och är i flera fall de första effektiva algoritmer som är kända. Som en andra typ av tillämpning visar vi att egenskaperna hos den villkorade LLL-distributionen kan användas i fall som ligger utanför LLL: att undvika alla dåliga händelser är omöjligt i dessa fall. Som det första (även icke-konstruktiva) resultatet av detta slag, visar vi att genom provtagning av en utvald mindre kärna från LLL-distributionen, kan vi undvika en bråkdel av dåliga händelser som är högre än förväntningarna. MAX k-SAT är ett belysande exempel på detta.
betecknar produktdistributionen av variabler i R. e följande version av Lovász lokala lemma är från REF.
New Constructive Aspects of the Lovász Local Lemma
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}