Thread View: gwene.acm.algorithms.transactions
1 messages
1 total messages
Started by unknown
Fri, 07 Jun 2019 02:00
Online Submodular Maximization with Preemption
Author: unknown
Date: Fri, 07 Jun 2019 02:00
Date: Fri, 07 Jun 2019 02:00
1 lines
809 bytes
809 bytes
Niv Buchbinder, Moran Feldman, Roy Schwartz<br /><br />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 to maximize 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. <p><a href="http://dl.acm.org/citation.cfm?id309764">Link</a>
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads