License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.30
URN: urn:nbn:de:0030-drops-68651
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6865/
Go to the corresponding LIPIcs Volume Portal

Bhaskar, Umang ; Jalal, Ajil ; Vaze, Rahul

The Adwords Problem with Strict Capacity Constraints

pdf-format:
LIPIcs-FSTTCS-2016-30.pdf (0.6 MB)

Abstract

We study an online assignment problem where the offline servers have capacities, and the objective is to obtain a maximum-weight assignment of requests that arrive online. The weight of edges incident to any server can be at most the server capacity. Our problem is related to the adwords problem, where the assignment to a server is allowed to exceed its capacity. In many applications, however, server capacities are strict and partially-served requests are of no use, motivating the problem we study.

While no deterministic algorithm can be competitive in general for this problem, we give an algorithm with competitive ratio that depends on the ratio of maximum weight of any edge to the capacity of the server it is incident to. If this ratio is 1/2, our algorithm is tight. Further, we give a randomized algorithm that is 6-competitive in expectation for the general problem. Most previous work on the problem and its variants assumes that the edge weights are much smaller than server capacities. Our guarantee, in contrast, does not require any assumptions about job weights. We also give improved lower bounds for both deterministic and randomized algorithms. For the special case of parallel servers, we show that a load-balancing algorithm is tight and near-optimal.

BibTeX - Entry

@InProceedings{bhaskar_et_al:LIPIcs:2016:6865,
  author =	{Umang Bhaskar and Ajil Jalal and Rahul Vaze},
  title =	{{The Adwords Problem with Strict Capacity Constraints}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6865},
  URN =		{urn:nbn:de:0030-drops-68651},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.30},
  annote =	{Keywords: Online Algorithms, Adwords, Budgeted Matching, Greedy Algorithms}
}

Keywords: Online Algorithms, Adwords, Budgeted Matching, Greedy Algorithms
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI