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.
När det gäller k = o(n) visade sig REF vara en starkare hårdhet på 0,491-uppskattning.
Submodular maximization by simulated annealing
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}