文章基本信息

标题：Online Set Cover with Set Requests
本地全文：下载
作者：Kshipra Bhawalkar ; Sreenivas Gollapudi ; Debmalya Panigrahi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：28
页码：64-79
DOI：10.4230/LIPIcs.APPROX-RANDOM.2014.64
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Online Algorithms; Set Cover