Online set cover with set requests

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Bhawalkar, K; Gollapudi, S; Panigrahi, D

Published Date

  • September 1, 2014

Published In

Volume / Issue

  • 28 /

Start / End Page

  • 64 - 79

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783939897743

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.APPROX-RANDOM.2014.64

Citation Source

  • Scopus