Buyback Problem - Approximate matroid intersection with cancellation costs

Details Buyback Problem - Approximate matroid intersection with cancellation costs Buyback Problem - Approximate matroid intersection with cancellation costs

2010-09-25

arxiv.org/abs/1009.5037v2

ICALP'11 Lecture Notes in Computer Science, 2011, Volume 6755/2011, 379-390

Computer Science

Computer Science and Game Theory

Scientific paper

10.1007/978-3-642-22006-7_32

In the buyback problem, an algorithm observes a sequence of bids and must decide whether to accept each bid at the moment it arrives, subject to some constraints on the set of accepted bids. Decisions to reject bids are irrevocable, whereas decisions to accept bids may be canceled at a cost that is a fixed fraction of the bid value. Previous to our work, deterministic and randomized algorithms were known when the constraint is a matroid constraint. We extend this and give a deterministic algorithm for the case when the constraint is an intersection of $k$ matroid constraints. We further prove a matching lower bound on the competitive ratio for this problem and extend our results to arbitrary downward closed set systems. This problem has applications to banner advertisement, semi-streaming, routing, load balancing and other problems where preemption or cancellation of previous allocations is allowed.

Affiliated with

Also associated with

No associations

Rating

Buyback Problem - Approximate matroid intersection with cancellation costs 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 Buyback Problem - Approximate matroid intersection with cancellation costs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Buyback Problem - Approximate matroid intersection with cancellation costs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-560657