Datorer av hög kvalitet oberoende uppsättningar snabbt är ett viktigt problem i kombinatoriell optimering. Flera senaste algoritmer har visat att kärnorisering tekniker kan användas för att hitta exakt maximal oberoende uppsättningar i medelstora glesa grafer, samt högkvalitativa oberoende uppsättningar i enorma glesa grafer som är intractable för exakta (exponentiell-tid) algoritmer. En stor nackdel med dessa algoritmer är dock att de kräver betydande förbehandling overhead, och därför inte kan användas för att hitta en högkvalitativ oberoende uppsättning snabbt. I detta papper, visar vi att utföra enkla kärnorisering tekniker på ett online-mode avsevärt ökar prestandan för lokal sökning, och är mycket snabbare än pre-puting en kärna med hjälp av avancerade tekniker. Dessutom visar vi att kapning av höggradiga hörn kan öka lokal sökning prestanda ännu mer, särskilt på stora (sparse) komplexa nätverk. Våra experiment visar att vi drastiskt kan påskynda beräkningen av stora oberoende uppsättningar jämfört med andra toppmoderna algoritmer, samtidigt som vi producerar resultat som är mycket nära de mest kända lösningarna.
Dahlum m.fl. REF finner att standardkärnan tekniker är för långsam för att vara effektiv för lokal sökning och visar att tillämpa enkla minskningar på ett online-mode förbättrar hastigheten för lokal sökning.
Accelerating Local Search for the Maximum Independent Set Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}