Vi presenterar en optimal, kombinatorial 1 − 1/e approximationsalgoritm för submodulär monoton optimering över en matrisrestriktion. Jämfört med den kontinuerliga giriga algoritmen (Calinescu, Chekuri, Pál och Vondrák, 2008) är vår algoritm extremt enkel och kräver ingen avrundning. Den består av den giriga algoritmen följt av lokal sökning. Båda faserna drivs inte på den faktiska objektiva funktionen, utan på en tillhörande kompletterande potentialfunktion, som också är monoton och submodulär. I vårt tidigare arbete med maximal täckning (Filmus and Ward, 2012) ger den potentiella funktionen mer tyngd åt element som täcks flera gånger. Vi generaliserar detta tillvägagångssätt från täckningsfunktioner till godtyckliga monotona submodulära funktioner. När den objektiva funktionen är en täckningsfunktion sammanfaller båda definitionerna av den potentiella funktionen. Vårt tillvägagångssätt generaliserar till fallet där den monotona submodulära funktionen har begränsat krökning. För alla krökningar c, anpassar vi vår algoritm för att producera en (1 − e − c ) / c approximation. Detta matchar resultaten av Vondrák (2008), som har visat att den kontinuerliga giriga algoritmen producerar en (1 − e − c ) / c approximation när den objektiva funktionen har krökning c med avseende på den optimala, och visat att uppnå någon bättre approximation förhållande är omöjligt i värde oracle modellen. * yuvalf@cs.toronto.edu † J.D.Ward@dcs.warwick.ac.uk Arbete som stöds av EPSRC bidrag EP/J021814/1. I fallet med en monoton submodulär objektiv funktion, standard girig algoritm, som tar vid varje steg det element som ger den största ökningen i f samtidigt som självständighet, är (endast) en 1/2 approximation [20]. Nyligen, Calinescu et al. [7, 34, 8] har utvecklat en (1 − 1/e) approximation för detta problem via den kontinuerliga giriga algoritmen, som påminner om den klassiska Frank-Wolfe-algoritmen [21], som producerar en fraktionerad lösning. Den fraktionerade lösningen avrundas med hjälp av pipageavrundning [1] eller swapavrundning [10]. Nyligen har en snabb variant av denna algoritm som körs i tid Õ(n 2 ) utformats av Ashwinkumar och Vondrák [3]. Feige [12] har visat att förbättring av gränsen (1 −1/e) är NP-hård även om f är en explicit given täckningsfunktion (den objektiva funktionen för en instans med maximal täckning). Nemhauser och Wolsey [30] har visat att varje förbättring över (1 − 1/e) kräver ett exponentiellt antal frågor i värde- orakelinställningen. Efter Vondrák [35] tar vi också hänsyn till fallet när f har begränsat krökning. Vi säger att f har krökning c om för två olika A, B U, När c = 1, detta är en omräkning av monotonitet f, och när c = 0, linjäritet f. Vondrák [35] har visat att den kontinuerliga giriga algoritmen producerar en (1 − e −c ) / c approximation när f har krökning c. I själva verket visar han att detta gäller även för den svagare definitionen av krökning med avseende på den optimala. Dessutom, för denna svagare uppfattning om krökning, har han visat att varje förbättring över (1 − e − c ) / c kräver ett exponentiellt antal frågor i värde orakel inställning. Det optimala approximationsförhållandet för funktioner med obegränsad krökning c har nyligen fastställts vara (1 − c/e) av Sviridenko och Ward [33], som använder den icke-omedvetna lokala sökmetoden som beskrivs i detta dokument.
Senare fick Filmus och Ward REF en (1 − e −1 ) - approximation för submodulär maximering i en godtycklig matris genom att använda en icke-obliviös lokal sökalgoritm som inte kräver avrundning.
Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
{'venue': 'SIAM Journal on Computing', 'journal': 'SIAM Journal on Computing', 'mag_field_of_study': ['Mathematics', 'Computer Science']}