Två genrer av heuristik som ofta rapporteras prestera mycket bättre på "real-world" fall än i värsta fall är giriga algoritmer och lokala sökalgoritmer. I detta dokument studerar vi systematiskt dessa två typer av algoritmer för problemet med maximering av en monoton submodulär uppsättning funktion som är föremål för nedstängda genomförbarhetsbegränsningar. Vi anser perturbation-stabila fall, i betydelsen Bilu och Linial [11], och exakt identifiera den stabilitet tröskel över vilken dessa algoritmer garanteras att återställa den optimala lösningen. Biprodukter av vårt arbete inkluderar den första definitionen av perturbation-stabilitet för icke additiva objektiva funktioner, och en lösning av den värsta-fall approximation garanti för lokal sökning i p-extendible system.
REF visar att den giriga algoritmen återvinner den unika optimala lösningen för 2-stabila instanser.
Stability and Recovery for Independence Systems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}