Buyback problem: approximate matroid intersection with cancellation costs

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