9 Search Results for "Bhaskar, Umang"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.6
Online Facility Location with Weights and Congestion

Authors: Arghya Chakraborty and Rahul Vaze

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
The classic online facility location problem deals with finding the optimal set of facilities in an online fashion when demand requests arrive one at a time and facilities need to be opened to service these requests. In this work, we study two variants of the online facility location problem; (1) weighted requests and (2) congestion. Both of these variants are motivated by their applications to real life scenarios and the previously known results on online facility location cannot be directly adapted to analyse them. - Weighted requests: In this variant, each demand request is a pair (x,w) where x is the standard location of the demand while w is the corresponding weight of the request. The cost of servicing request (x,w) at facility F is w⋅ d(x,F). For this variant, given n requests, we present an online algorithm attaining a competitive ratio of 𝒪(log n) in the secretarial model for the weighted requests and show that it is optimal. -Congestion: The congestion variant considers the case when there is a congestion cost that grows with the number of requests served by each facility. For this variant, when the congestion cost is a monomial, we show that there exists an algorithm attaining a constant competitive ratio. This constant is a function of the exponent of the monomial and the facility opening cost but independent of the number of requests.
Cite as

Arghya Chakraborty and Rahul Vaze. Online Facility Location with Weights and Congestion. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2023.6,
  author =	{Chakraborty, Arghya and Vaze, Rahul},
  title =	{{Online Facility Location with Weights and Congestion}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.6},
  URN =		{urn:nbn:de:0030-drops-193797},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.6},
  annote =	{Keywords: online algorithms, online facility location, probabilistic method, weighted-requests, congestion}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.1
On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources

Authors: Umang Bhaskar, A. R. Sricharan, and Rohit Vaish

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
We study the fair allocation of undesirable indivisible items, or chores. While the case of desirable indivisible items (or goods) is extensively studied, with many results known for different notions of fairness, less is known about the fair division of chores. We study envy-free allocation of chores and make three contributions. First, we show that determining the existence of an envy-free allocation is NP-complete even in the simple case when agents have binary additive valuations. Second, we provide a polynomial-time algorithm for computing an allocation that satisfies envy-freeness up to one chore (EF1), correcting a claim in the existing literature. A modification of our algorithm can be used to compute an EF1 allocation for doubly monotone instances (where each agent can partition the set of items into objective goods and objective chores). Our third result applies to a mixed resources model consisting of indivisible items and a divisible, undesirable heterogeneous resource (i.e., a bad cake). We show that there always exists an allocation that satisfies envy-freeness for mixed resources (EFM) in this setting, complementing a recent result of Bei et al. [Bei et al., 2021] for indivisible goods and divisible cake.
Cite as

Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.APPROX/RANDOM.2021.1,
  author =	{Bhaskar, Umang and Sricharan, A. R. and Vaish, Rohit},
  title =	{{On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{1:1--1:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.1},
  URN =		{urn:nbn:de:0030-drops-146944},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.1},
  annote =	{Keywords: Fair Division, Indivisible Chores, Approximate Envy-Freeness}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.46
Partial Function Extension with Applications to Learning and Property Testing

Authors: Umang Bhaskar and Gunjan Kumar

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Partial function extension is a basic problem that underpins multiple research topics in optimization, including learning, property testing, and game theory. Here, we are given a partial function consisting of n points from a domain and a function value at each point. Our objective is to determine if this partial function can be extended to a function defined on the domain, that additionally satisfies a given property, such as linearity. We formally study partial function extension to fundamental properties in combinatorial optimization - subadditivity, XOS, and matroid independence. A priori, it is not clear if partial function extension for these properties even lies in NP (or coNP). Our contributions are twofold. Firstly, for the properties studied, we give bounds on the complexity of partial function extension. For subadditivity and XOS, we give tight bounds on approximation guarantees as well. Secondly, we develop new connections between partial function extension and learning and property testing, and use these to give new results for these problems. In particular, for subadditive functions, we give improved lower bounds on learning, as well as the first subexponential-query tester.
Cite as

Umang Bhaskar and Gunjan Kumar. Partial Function Extension with Applications to Learning and Property Testing. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.ISAAC.2020.46,
  author =	{Bhaskar, Umang and Kumar, Gunjan},
  title =	{{Partial Function Extension with Applications to Learning and Property Testing}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.46},
  URN =		{urn:nbn:de:0030-drops-133906},
  doi =		{10.4230/LIPIcs.ISAAC.2020.46},
  annote =	{Keywords: Partial function extension, subadditivity, matroid rank, approximation algorithms, learning, property testing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.11
Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations

Authors: Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We develop polynomial-time algorithms for the fair and efficient allocation of indivisible goods among n agents that have subadditive valuations over the goods. We first consider the Nash social welfare as our objective and design a polynomial-time algorithm that, in the value oracle model, finds an 8n-approximation to the Nash optimal allocation. Subadditive valuations include XOS (fractionally subadditive) and submodular valuations as special cases. Our result, even for the special case of submodular valuations, improves upon the previously best known O(n log n)-approximation ratio of Garg et al. (2020). More generally, we study maximization of p-mean welfare. The p-mean welfare is parameterized by an exponent term p ∈ (-∞, 1] and encompasses a range of welfare functions, such as social welfare (p = 1), Nash social welfare (p → 0), and egalitarian welfare (p → -∞). We give an algorithm that, for subadditive valuations and any given p ∈ (-∞, 1], computes (in the value oracle model and in polynomial time) an allocation with p-mean welfare at least 1/(8n) times the optimal. Further, we show that our approximation guarantees are essentially tight for XOS and, hence, subadditive valuations. We adapt a result of Dobzinski et al. (2010) to show that, under XOS valuations, an O (n^{1-ε}) approximation for the p-mean welfare for any p ∈ (-∞,1] (including the Nash social welfare) requires exponentially many value queries; here, ε > 0 is any fixed constant.
Cite as

Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram. Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barman_et_al:LIPIcs.ESA.2020.11,
  author =	{Barman, Siddharth and Bhaskar, Umang and Krishna, Anand and Sundaram, Ranjani G.},
  title =	{{Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.11},
  URN =		{urn:nbn:de:0030-drops-128775},
  doi =		{10.4230/LIPIcs.ESA.2020.11},
  annote =	{Keywords: Discrete Fair Division, Nash Social Welfare, Subadditive Valuations, Submodular Valuations}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.30
The Complexity of Partial Function Extension for Coverage Functions

Authors: Umang Bhaskar and Gunjan Kumar

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
Coverage functions are an important subclass of submodular functions, finding applications in machine learning, game theory, social networks, and facility location. We study the complexity of partial function extension to coverage functions. That is, given a partial function consisting of a family of subsets of [m] and a value at each point, does there exist a coverage function defined on all subsets of [m] that extends this partial function? Partial function extension is previously studied for other function classes, including boolean functions and convex functions, and is useful in many fields, such as obtaining bounds on learning these function classes. We show that determining extendibility of a partial function to a coverage function is NP-complete, establishing in the process that there is a polynomial-sized certificate of extendibility. The hardness also gives us a lower bound for learning coverage functions. We then study two natural notions of approximate extension, to account for errors in the data set. The two notions correspond roughly to multiplicative point-wise approximation and additive L_1 approximation. We show upper and lower bounds for both notions of approximation. In the second case we obtain nearly tight bounds.
Cite as

Umang Bhaskar and Gunjan Kumar. The Complexity of Partial Function Extension for Coverage Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.APPROX-RANDOM.2019.30,
  author =	{Bhaskar, Umang and Kumar, Gunjan},
  title =	{{The Complexity of Partial Function Extension for Coverage Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{30:1--30:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.30},
  URN =		{urn:nbn:de:0030-drops-112457},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.30},
  annote =	{Keywords: Coverage Functions, PAC Learning, Approximation Algorithm, Partial Function Extension}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.27
On the Welfare of Cardinal Voting Mechanisms

Authors: Umang Bhaskar and Abheek Ghosh

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
A voting mechanism is a method for preference aggregation that takes as input preferences over alternatives from voters, and selects an alternative, or a distribution over alternatives. While preferences of voters are generally assumed to be cardinal utility functions that map each alternative to a real value, mechanisms typically studied assume coarser inputs, such as rankings of the alternatives (called ordinal mechanisms). We study cardinal mechanisms, that take as input the cardinal utilities of the voters, with the objective of minimizing the distortion - the worst-case ratio of the best social welfare to that obtained by the mechanism. For truthful cardinal mechanisms with m alternatives and n voters, we show bounds of Theta(mn), Omega(m), and Omega(sqrt{m}) for deterministic, unanimous, and randomized mechanisms respectively. This shows, somewhat surprisingly, that even mechanisms that allow cardinal inputs have large distortion. There exist ordinal (and hence, cardinal) mechanisms with distortion O(sqrt{m log m}), and hence our lower bound for randomized mechanisms is nearly tight. In an effort to close this gap, we give a class of truthful cardinal mechanisms that we call randomized hyperspherical mechanisms that have O(sqrt{m log m}) distortion. These are interesting because they violate two properties - localization and non-perversity - that characterize truthful ordinal mechanisms, demonstrating non-trivial mechanisms that differ significantly from ordinal mechanisms. Given the strong lower bounds for truthful mechanisms, we then consider approximately truthful mechanisms. We give a mechanism that is delta-truthful given delta in (0,1), and has distortion close to 1. Finally, we consider the simple mechanism that selects the alternative that maximizes social welfare. This mechanism is not truthful, and we study the distortion at equilibria for the voters (equivalent to the Price of Anarchy, or PoA). While in general, the PoA is unbounded, we show that for equilibria obtained from natural dynamics, the PoA is close to 1. Thus relaxing the notion of truthfulness in both cases allows us to obtain near-optimal distortion.
Cite as

Umang Bhaskar and Abheek Ghosh. On the Welfare of Cardinal Voting Mechanisms. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 27:1-27:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.FSTTCS.2018.27,
  author =	{Bhaskar, Umang and Ghosh, Abheek},
  title =	{{On the Welfare of Cardinal Voting Mechanisms}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{27:1--27:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.27},
  URN =		{urn:nbn:de:0030-drops-99260},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.27},
  annote =	{Keywords: computational social choice, voting rules, cardinal mechanisms, price of anarchy, distortion}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.1
Algorithms for Inverse Optimization Problems

Authors: Sara Ahmadian, Umang Bhaskar, Laura Sanità, and Chaitanya Swamy

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We study inverse optimization problems, wherein the goal is to map given solutions to an underlying optimization problem to a cost vector for which the given solutions are the (unique) optimal solutions. Inverse optimization problems find diverse applications and have been widely studied. A prominent problem in this field is the inverse shortest path (ISP) problem [D. Burton and Ph.L. Toint, 1992; W. Ben-Ameur and E. Gourdin, 2004; A. Bley, 2007], which finds applications in shortest-path routing protocols used in telecommunications. Here we seek a cost vector that is positive, integral, induces a set of given paths as the unique shortest paths, and has minimum l_infty norm. Despite being extensively studied, very few algorithmic results are known for inverse optimization problems involving integrality constraints on the desired cost vector whose norm has to be minimized. Motivated by ISP, we initiate a systematic study of such integral inverse optimization problems from the perspective of designing polynomial time approximation algorithms. For ISP, our main result is an additive 1-approximation algorithm for multicommodity ISP with node-disjoint commodities, which we show is tight assuming P!=NP. We then consider the integral-cost inverse versions of various other fundamental combinatorial optimization problems, including min-cost flow, max/min-cost bipartite matching, and max/min-cost basis in a matroid, and obtain tight or nearly-tight approximation guarantees for these. Our guarantees for the first two problems are based on results for a broad generalization, namely integral inverse polyhedral optimization, for which we also give approximation guarantees. Our techniques also give similar results for variants, including l_p-norm minimization of the integral cost vector, and distance-minimization from an initial cost vector.
Cite as

Sara Ahmadian, Umang Bhaskar, Laura Sanità, and Chaitanya Swamy. Algorithms for Inverse Optimization Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ahmadian_et_al:LIPIcs.ESA.2018.1,
  author =	{Ahmadian, Sara and Bhaskar, Umang and Sanit\`{a}, Laura and Swamy, Chaitanya},
  title =	{{Algorithms for Inverse Optimization Problems}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.1},
  URN =		{urn:nbn:de:0030-drops-94646},
  doi =		{10.4230/LIPIcs.ESA.2018.1},
  annote =	{Keywords: Inverse optimization, Shortest paths, Approximation algorithms, Linear programming, Polyhedral theory, Combinatorial optimization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.58
Equilibrium Computation in Atomic Splittable Routing Games

Authors: Umang Bhaskar and Phani Raj Lolakapuri

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We present polynomial-time algorithms as well as hardness results for equilibrium computation in atomic splittable routing games, for the case of general convex cost functions. These games model traffic in freight transportation, market oligopolies, data networks, and various other applications. An atomic splittable routing game is played on a network where the edges have traffic-dependent cost functions, and player strategies correspond to flows in the network. A player can thus split its traffic arbitrarily among different paths. While many properties of equilibria in these games have been studied, efficient algorithms for equilibrium computation are known for only two cases: if cost functions are affine, or if players are symmetric. Neither of these conditions is met in most practical applications. We present two algorithms for routing games with general convex cost functions on parallel links. The first algorithm is exponential in the number of players, while the second is exponential in the number of edges; thus if either of these is small, we get a polynomial-time algorithm. These are the first algorithms for these games with convex cost functions. Lastly, we show that in general networks, given input C, it is NP-hard to decide if there exists an equilibrium where every player has cost at most C.
Cite as

Umang Bhaskar and Phani Raj Lolakapuri. Equilibrium Computation in Atomic Splittable Routing Games. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.ESA.2018.58,
  author =	{Bhaskar, Umang and Lolakapuri, Phani Raj},
  title =	{{Equilibrium Computation in Atomic Splittable Routing Games}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.58},
  URN =		{urn:nbn:de:0030-drops-95211},
  doi =		{10.4230/LIPIcs.ESA.2018.58},
  annote =	{Keywords: Routing Games, Equilibrium Computation, Convex costs, Splittable flows}
}
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
  • 8 Bhaskar, Umang
  • 2 Kumar, Gunjan
  • 2 Vaze, Rahul
  • 1 Ahmadian, Sara
  • 1 Barman, Siddharth
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Algorithmic game theory
  • 3 Theory of computation → Approximation algorithms analysis
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Network flows
  • 1 Theory of computation → Exact and approximate computation of equilibria
  • Show More...

  • Refine by Keyword
  • 1 Adwords
  • 1 Approximate Envy-Freeness
  • 1 Approximation Algorithm
  • 1 Approximation algorithms
  • 1 Budgeted Matching
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 3 2018
  • 2 2020
  • 1 2016
  • 1 2019
  • 1 2021
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact