Sammanfattning Vi anser att en robust formulering, introducerad av Krause et al. (2008), av den klassiska kardinalitet begränsad monoton submodulär funktion maximering problem, och ge den första konstant faktor approximation resultat. Den robusthet som beaktas är w.r.t. adversariellt avlägsnande av upp till τ-element från den valda uppsättningen. För det grundläggande fallet av τ = 1, ger vi en deterministisk (1 − 1/e) − (1/m) approximation, vilket gör O (n m+1 ) frågor. Under processens gång utvecklar vi en deterministisk (1 − 1/e) − (1/m) ungefärlig girig algoritm för bi-objektiv maximering av (två) monotona submodulära funktioner. Generalisera idéerna och använda ett resultat från Chekuri et al. (2010), visar vi en randomiserad (1 − 1/ e) − approximation för konstant τ och vi ger en snabb och praktisk 0,387 algoritm. Slutligen ger vi också ett resultat för en mer allmän miljö.
För det speciella fallet med kardinalitetsbegränsning (som kommer att vara vårt fokus här) visade REF nyligen att den giriga algoritmen kan generaliseras för att uppnå en deterministisk 1 − 1/e − approximation för specialfallet av bi-objektiv maximering.
Robust Monotone Submodular Function Maximization
{'venue': 'IPCO', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}