Vi anser att prestanda av två klassiska approximation algoritmer som fungerar genom att skanna input och girigt bygga en lösning. Vi undersöker om köra dessa algoritmer på en slumpmässig permutation av indata kan öka deras prestanda förhållande. Vi får följande resultat: 1. Johnsons approximationsalgoritm för MAX-SAT är en av de första approximationsalgoritmerna som noggrant analyseras. Det har visats att prestandaförhållandet för denna algoritm är 2/3. Vi visar att när den utförs på en slumpmässig permutation av variablerna förbättras prestandaförhållandet för denna algoritm till 2/3 + c för vissa c > 0 Detta löser ett öppet problem med Chen, Friesen och Zhang [JCSS 1999]. (Se även tidningen av Poloczek och Schnitger i dessa förfaranden för relaterade resultat på denna algoritm och dess varianter). 2. Utgångspunkten är följande: Motiverade av ovanstående förbättring, anser vi prestandan av den giriga algoritmen för MAX-CUT vars prestanda ratio är 1/2. Vår förhoppning var att köra den giriga algoritmen på en slumpmässig permutation av hörnen skulle resultera i en 1/2 + c approximation algoritm. Det visar sig dock att algoritmens prestanda i detta fall förblir 1/2. Detta löser ett öppet problem för Mathieu och Schudy [SODA 2008].
Costello et al REF visade att Johnsons algoritm uppnår en approximationsgrad på 2/3 + c för vissa c > 0 i ROM.
Randomized greedy: new variants of some classic approximation algorithms
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}