Vi anser att problemet med att maximera en icke-negativ (eventuellt icke-monoton) submodulär uppsättning funktion med eller utan begränsningar. Feige och al. [9] visade en 2/5-approximation för det okonstruerade problemet och visade också att ingen approximation bättre än 1/2 är möjlig i värde-orakelmodellen. Tillnärmningen av konstantfaktorn har också varit känd för submodulär maximering som är föremål för en begränsning av matrisens oberoende (en faktor på 0,309 [33] ) och för submodulär maximering som är föremål för en begränsning av matrisbasen, förutsatt att packningsnumret för fraktionerad bas är begränsat från 1 (en 1/4- approximation med antagande av att mot ≥ 2 [33]). I detta dokument föreslår vi en ny algoritm för submodulär maximering som bygger på idén om simulerad glödgning. Vi bevisar att denna algoritm uppnår förbättrad approximation för två problem: en 0,41- approximation för okonstruerad submodulär maximering, och en 0,325 approximation för submodulär maximering som är föremål för en matroid självständighetsbegränsning. På hårdheten sida, visar vi att i värdet oracle modell är det omöjligt att uppnå en 0.478-calimation för submodulär maximering som är föremål för en matroid oberoende begränsning, eller en 0.394-calimation som är föremål för en matroid bas begränsning i matroider med två separata baser. Även för det speciella fallet med kardinalitetsbegränsningar, bevisar vi att det är omöjligt att uppnå en 0,491-uppskattning. (Tidigare var det tänkbart att det finns en halv approximation för dessa problem.) Det är fortfarande en öppen fråga om en 1/2-uppskattning är möjlig för oöverskådlig submodulär maximering.
På hårdhet sidan, är det känt att ingen polynom tid algoritm kan ha en approximation förhållande bättre än 0.491 REF.
Submodular maximization by simulated annealing
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}