Det har gjorts stora framsteg på senare tid när det gäller förbättrade approximationer för problem som rör submodulära objektiva funktioner, och många intressanta tekniker har utvecklats. Men de resulterande algoritmerna är ofta långsamma och opraktiska. I detta papper utvecklar vi algoritmer som matchar de mest kända approximationsgarantierna, men med avsevärt förbättrade körtider, för att maximera en monoton submodulär funktion f : 2 [n] → R + med olika begränsningar. Liksom i tidigare arbeten mäter vi antalet orakletanrop till den objektiva funktion som är den dominerande termen i körtiden. Vårt första resultat är en enkel algoritm som ger en (1 − 1/e − ) - approximation för en kardinalitet begränsning med hjälp av O( n log n ) frågor, och en 1/(p + 2 + 1 + ) - approximation för skärningspunkten mellan ett p-system och knapsack (linjära) begränsningar med hjälp av O( n 2 log 2 n ) frågor. Detta är den första approximationen för ett p-system kombinerat med linjära begränsningar. (Vi visar också att faktorn p inte kan förbättras för att maximera över ett p-system.) Huvudidén bakom dessa algoritmer fungerar som en byggsten i våra mer sofistikerade algoritmer. Vårt huvudresultat är en ny variant av den kontinuerliga giriga algoritmen, som interpolerar mellan den klassiska giriga algoritmen och en verkligt kontinuerlig algoritm. Vi visar hur denna algoritm kan implementeras för matroid och knapsack begränsningar med Õ(n 2 ) oracle samtal till den objektiva funktionen. (Tidigare varianter och alternativa tekniker var kända för att använda minst O(n 4) oracle anrop.) Detta leder till en O( n 2 4 log 2 n ) - tid (1 − 1/ e − ) - approximation för en matroid begränsning. För en knapsackrestriktion utvecklar vi en mer involverad (1 − 1/e − ) - approximationsalgoritm som körs i tiden O(n 2 (1 log n)
Badanidiyuru och Vondrák REF tillhandahöll en (1 − 1/e − ) - approximation föremål för en kardinalitet begränsning med hjälp av O( n log 1 ) värdefrågor, och föremål för en matris begränsning med hjälp av O( n 2 4 log 2 n ) frågor.
Fast algorithms for maximizing submodular functions
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}