DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2021.79

Distributed Load Balancing: A New Framework and Improved Guarantees

Authors: Sara Ahmadian, Allen Liu, Binghui Peng, and Morteza Zadimoghaddam

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract

Inspired by applications on search engines and web servers, we consider a load balancing problem with a general convex objective function. In this problem, we are given a bipartite graph on a set of sources S and a set of workers W and the goal is to distribute the load from each source among its neighboring workers such that the total load of workers are as balanced as possible. We present a new distributed algorithm that works with any symmetric non-decreasing convex function for evaluating the balancedness of the workers' load. Our algorithm computes a nearly optimal allocation of loads in O(log n log² d/ε³) rounds where n is the number of nodes, d is the maximum degree, and ε is the desired precision. If the objective is to minimize the maximum load, we modify the algorithm to obtain a nearly optimal solution in O(log n log d/ε²) rounds. This improves a line of algorithms that require a polynomial number of rounds in n and d and appear to encounter a fundamental barrier that prevents them from obtaining poly-logarithmic runtime [Berenbrink et al., 2005; Berenbrink et al., 2009; Subramanian and Scherson, 1994; Rabani et al., 1998]. In our paper, we introduce a novel primal-dual approach with multiplicative weight updates that allows us to circumvent this barrier. Our algorithm is inspired by [Agrawal et al., 2018] and other distributed algorithms for optimizing linear objectives but introduces several new twists to deal with general convex objectives.

Cite as

Sara Ahmadian, Allen Liu, Binghui Peng, and Morteza Zadimoghaddam. Distributed Load Balancing: A New Framework and Improved Guarantees. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ahmadian_et_al:LIPIcs.ITCS.2021.79,
  author =	{Ahmadian, Sara and Liu, Allen and Peng, Binghui and Zadimoghaddam, Morteza},
  title =	{{Distributed Load Balancing: A New Framework and Improved Guarantees}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{79:1--79:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.79},
  URN =		{urn:nbn:de:0030-drops-136186},
  doi =		{10.4230/LIPIcs.ITCS.2021.79},
  annote =	{Keywords: Load balancing, Distributed algorithms}
}

Document

DOI: 10.4230/LIPIcs.STACS.2013.550

Constrained Binary Identification Problem

Authors: Amin Karbasi and Morteza Zadimoghaddam

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract

We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the "20 questions game" of information theory and is closely related to lossless source compression. If any query is admissible, Huffman coding is optimal with close to H[P] questions on average, the entropy of the prior distribution P over objects. However, in many realistic scenarios, there are constraints on which queries can be asked, and solving the problem optimally is NP-hard. We provide novel polynomial time approximation algorithms where constraints are defined in terms of "graph", general "cost", and "submodular" functions. In particular, we show that under graph constraints, there exists a constant approximation algorithm for locating the target in the set. We then extend our approach for scenarios where the constraints are defined in terms of general cost functions that depend only on the size of the query and provide an approximation algorithm that can find the target within O(log(log n)) gap from the cost of the optimum algorithm. Submodular functions come as a natural generalization of cost functions with decreasing marginals. Under submodular set constraints, we devise an approximation algorithm that can find the target within O(log n) gap from the cost of the optimum algorithm. The proposed algorithms are greedy in a sense that at each step they select a query that most evenly splits the set without violating the underlying constraints. These results can be applied to network tomography, active learning and interactive content search.

Cite as

Amin Karbasi and Morteza Zadimoghaddam. Constrained Binary Identification Problem. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 550-561, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{karbasi_et_al:LIPIcs.STACS.2013.550,
  author =	{Karbasi, Amin and Zadimoghaddam, Morteza},
  title =	{{Constrained Binary Identification Problem}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{550--561},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.550},
  URN =		{urn:nbn:de:0030-drops-39647},
  doi =		{10.4230/LIPIcs.STACS.2013.550},
  annote =	{Keywords: Network Tomography, Binary Identification Problem, Approximation Algorithms, Graph Algorithms, Tree Search Strategies, Entropy}
}

Document

DOI: 10.4230/LIPIcs.STACS.2009.1839

The Price of Anarchy in Cooperative Network Creation Games

Authors: Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract

We analyze the structure of equilibria and the price of anarchy in the family of network creation games considered extensively in the past few years, which attempt to unify the network design and network routing problems by modeling both creation and usage costs. In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost~$\alpha$. Together the agents create a network (a subgraph of the host graph) while selfishly minimizing the link creation costs plus the sum of the distances to all other players (usage cost). In this paper, we pursue two important facets of the network creation~game. First, we study extensively a natural version of the game, called the cooperative model, where nodes can collaborate and share the cost of creating any edge in the host graph. We prove the first nontrivial bounds in this model, establishing that the price of anarchy is polylogarithmic in $n$ for all values of~$\alpha$ in complete host graphs. This bound is the first result of this type for any version of the network creation game; most previous general upper bounds are polynomial in~$n$. Interestingly, we also show that equilibrium graphs have polylogarithmic diameter for the most natural range of~$\alpha$ (at most $n \mathop{\rm polylg}\nolimits n$). Second, we study the impact of the natural assumption that the host graph is a general graph, not necessarily complete. This model is a simple example of nonuniform creation costs among the edges (effectively allowing weights of $\alpha$ and~$\infty$). We prove the first assemblage of upper and lower bounds for this context, establishing nontrivial tight bounds for many ranges of~$\alpha$, for both the unilateral and cooperative versions of network creation. In particular, we establish polynomial lower bounds for both versions and many ranges of~$\alpha$, even for this simple nonuniform cost model, which sharply contrasts the conjectured constant bounds for these games in complete (uniform) graphs.

Cite as

Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam. The Price of Anarchy in Cooperative Network Creation Games. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 301-312, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.STACS.2009.1839,
  author =	{Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Mahini, Hamid and Zadimoghaddam, Morteza},
  title =	{{The Price of Anarchy in Cooperative Network Creation Games}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{301--312},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1839},
  URN =		{urn:nbn:de:0030-drops-18390},
  doi =		{10.4230/LIPIcs.STACS.2009.1839},
  annote =	{Keywords: }
}

3 Search Results for "Zadimoghaddam, Morteza"

Distributed Load Balancing: A New Framework and Improved Guarantees

Abstract

Cite as

Constrained Binary Identification Problem

Abstract

Cite as

The Price of Anarchy in Cooperative Network Creation Games

Abstract

Cite as

Thanks for your feedback!

Could not send message