1 Search Results for "Jalal, Ajil"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2016.30

The Adwords Problem with Strict Capacity Constraints

Authors: Umang Bhaskar, Ajil Jalal, and Rahul Vaze

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

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.

Cite as

Umang Bhaskar, Ajil Jalal, and Rahul Vaze. The Adwords Problem with Strict Capacity Constraints. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.FSTTCS.2016.30,
  author =	{Bhaskar, Umang and Jalal, Ajil and Vaze, Rahul},
  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 =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.30},
  URN =		{urn:nbn:de:0030-drops-68651},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.30},
  annote =	{Keywords: Online Algorithms, Adwords, Budgeted Matching, Greedy Algorithms}
}

Refine by Author
1 Bhaskar, Umang
1 Jalal, Ajil
1 Vaze, Rahul

Refine by Classification

Refine by Keyword
1 Adwords
1 Budgeted Matching
1 Greedy Algorithms
1 Online Algorithms

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Jalal, Ajil"

The Adwords Problem with Strict Capacity Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message