Snabba algoritmer för submodulära maximeringsproblem har en stor potentiell användning i tillämpningar, såsom maskininlärning, sociala nätverk och ekonomi. Även om snabba algoritmer var kända för vissa speciella fall, bara nyligen Badanidiyuru och Vondrák [4] var de första att uttryckligen leta efter sådana algoritmer i det allmänna fallet att maximera en monoton submodulär funktion som är föremål för en matris oberoende begränsning. Algoritmen i Badanidiyuru och Vondrák matchar bästa möjliga approximation garanti, samtidigt som man försöker minska antalet värde oracle frågor algoritmen utför. Vårt huvudsakliga resultat är en ny algoritm för detta allmänna fall som etablerar en överraskande avvägning mellan två till synes orelaterade mängder: antalet värde oracle frågor och antalet frågor matroid självständighet utförs av algoritmen. I synnerhet kan man minska den förra genom att öka den senare och vice versa, samtidigt som man bibehåller bästa möjliga approximationsgaranti. En sådan avvägning är mycket användbar eftersom olika tillämpningar kan medföra betydligt olika kostnader i fråga om värde och matroid oberoende oracles. Dessutom, om rankningen av matroid är O(n c ), där n är storleken på marken uppsättning och c är en absolut konstant mindre än 1, det totala antalet oracle frågor vår algoritm använder kan göras för att ha en mindre storlek jämfört med vad som krävs av [4]. Vi tillhandahåller även ännu snabbare algoritmer för väl studerade specialfall av en kardinalitetsrestriktion och en partition matroid självständighetsrestriktion, som båda fångar många verkliga tillämpningar och har studerats brett både teoretiskt och i praktiken.
REF beskrev också en annan (1 − 1/e − ε) - approximationsalgoritm för maximering av en monoton submodulär funktion som är föremål för en allmän matrisrestriktion.
Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}