Att hitta den största oberoende uppsättningen i en graf är ett notoriskt svårt N P-kombinatoriellt optimeringsproblem. Dessutom, även för grafer med största grad 3, ingen polynom tid approximation algoritm finns med en 1.0071-faktor approximation garanti, un- Vi anser det relaterade problemet att hitta den maximala vikten oberoende set i en begränsad grad graf, när nod vikter genereras i.i.d. från en gemensam distribution. Förvånansvärt nog upptäcker vi att problemet blir lättåtkomligt för vissa distributioner. Specifikt, vi konstruerar en randomiserad PTAS (Polynomial-Time Caimation Scheme) för fallet med exponentiellt fördelade vikter och godtyckliga grafer med grad högst 3. Vi utökar vårt resultat till grafer med större konstant grader men för distributioner som är blandningar av exponentiella fördelningar. Samtidigt bevisar vi att inga PTAS finns för beräkning av den förväntade storleken på den maximala vikt oberoende uppsättningen i fallet med exponentiellt fördelade vikter för grafer med tillräckligt stor konstant grad, om inte P=NP. Vår algoritm, hålrumsexpansion, är ny och bygger på kombinationen av flera kraftfulla idéer, inklusive nyligen deterministiska approximationsalgoritmer för att räkna på grafer och lokala svaga konvergens/korrelationsförfall metoder.
I arbetet med REF undersöktes problemet med att hitta en maximal oberoende uppsättning i regelbundna diagram där vikterna för hörnen är i.i.d.
PTAS for maximum weight independent set problem with random weights in bounded degree graphs
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}