Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Online Set Cover with Set Requests

Kshipra Bhawalkar, Sreenivas Gollapudi, and Debmalya Panigrahi

Abstract

We consider a generic online allocation problem that generalizes the classical online set cover framework by considering requests comprising a set of elements rather than a single element. This problem has multiple applications in cloud computing, crowd sourcing, facility planning, etc. Formally, it is an online covering problem where each online step comprises an offline covering problem. In addition, the covering sets are capacitated, leading to packing constraints. We give a randomized algorithm for this problem that has a nearly tight competitive ratio in both objectives: overall cost and maximum capacity violation. Our main technical tool is an online algorithm for packing/covering LPs with nested constraints, which may be of interest in other applications as well.

Details

Publication typeInproceedings
Published inAPPROX 2014
PublisherLeibniz International Proceedings in Informatics
> Publications > Online Set Cover with Set Requests