Online submodular maximization with preemption

Niv Buchbinder, Moran Feldman, Roy Schwartz

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

Submodular function maximization has been studied extensively in recent years under various constraints and models. The problem plays a major role in various disciplines. We study a natural online variant of this problem in which elements arrive one by one and the algorithm has to maintain a solution obeying certain constraints at all times. Upon arrival of an element, the algorithm has to decide whether to accept the element into its solution and may preempt previously chosen elements. The goal is tomaximize a submodular function over the set of elements in the solution. We study two special cases of this general problem and derive upper and lower bounds on the competitive ratio. Specifically, we design a 1/e-competitive algorithm for the unconstrained case in which the algorithm may hold any subset of the elements, and constant competitive ratio algorithms for the case where the algorithm may hold at most k elements in its solution.

שפה מקוריתאנגלית
מספר המאמר0076
כתב עתACM Transactions on Algorithms
כרך15
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מאי 2019

הערה ביבליוגרפית

Publisher Copyright:
© 2019 Association for Computing Machinery.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Online submodular maximization with preemption'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי