Computer Science – Discrete Mathematics
Scientific paper
2010-09-21
Computer Science
Discrete Mathematics
Scientific paper
In this paper we study a general class of online maximization problems which are as follows. We are given a time constraint T. We have to choose a sequence of actions from a set of possible actions and also the length of time to run each action subject to the total time being no more than T. Each action has a marginal profit. We show that if the problem has the following two properties, then there is a greedy algorithm that can yield O(1-1/e) of the optimal. -Performing an action earlier does not decrease the marginal profit of the action. -Running a sequence of actions "A" followed by a sequence of actions "B" yields at least as much profit as the maximum profit of "A" or "B". The greedy algorithm also has the advantage that it can still be applied in many settings where complete knowledge of the problem is not available or in online settings where the input is revealed gradually. We also give examples of non-trivial problems, for some of which we are not aware of any better algorithm.
Alaei Saeed
Malekian Azarakhsh
No associations
LandOfFree
Maximizing Sequence-Submodular Functions and its Application to Online Advertising does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maximizing Sequence-Submodular Functions and its Application to Online Advertising, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximizing Sequence-Submodular Functions and its Application to Online Advertising will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-697847