2 Search Results for "Wasim, Omer"


Document
Improved Bounds for Online Balanced Graph Re-Partitioning

Authors: Rajmohan Rajaraman and Omer Wasim

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
We study the online balanced graph re-partitioning problem (OBGR) which was introduced by Avin, Bienkowski, Loukas, Pacut, and Schmid [Avin et al., 2020] and has recently received significant attention [Pacut et al., 2021; Henzinger et al., 2021; Henzinger et al., 2019; Tobias Forner et al., 2021; Bienkowski et al., 2021] owing to potential applications in large-scale, data-intensive distributed computing. In OBGR, we have a set of 𝓁 clusters, each with k vertices (representing processes or virtual machines), and an online sequence of communication requests, each represented by a pair of vertices. Any request (u,v) incurs unit communication cost if u and v are located in different clusters (and zero otherwise). Any vertex can be migrated from one cluster to another at a migration cost of α ≥ 1. We consider the objective of minimizing the total communication and migration cost in the competitive analysis framework. The only known algorithms (which run in exponential time) include an O(k²𝓁²) competitive [Avin et al., 2020] and an O(k𝓁 2^O(k)) competitive algorithm [Bienkowski et al., 2021]. A lower bound of Ω(k𝓁) is known [Pacut et al., 2021]. In an effort to bridge the gap, recent results have considered beyond worst case analyses including resource augmentation (with augmented cluster capacity [Avin et al., 2020; Henzinger et al., 2019; Henzinger et al., 2021]) and restricted request sequences (the learning model [Henzinger et al., 2019; Henzinger et al., 2021; Pacut et al., 2021]). In this paper, we give deterministic, polynomial-time algorithms for OBGR, which mildly exploit resource augmentation (i.e. augmented cluster capacity of (1+ε) k for arbitrary ε > 0). We improve beyond O(k²𝓁²)-competitiveness (for general 𝓁, k) by first giving a simple algorithm with competitive ratio O(k𝓁²log k). Our main result is an algorithm with a significantly improved competitive ratio of O(k𝓁 log k). At a high level, we achieve this by employing i) an ILP framework to guide the allocation of large components, ii) a simple "any fit" style assignment of small components and iii) a charging argument which allows us to bound the cost of migrations. Like previous work on OBGR, our algorithm and analysis are phase-based, where each phase solves an independent instance of the learning model. Finally, we give an Ω(α k𝓁 log k) lower bound on the total cost incurred by any algorithm for OBGR under the learning model, which quantifies the limitation of a phase-based approach.

Cite as

Rajmohan Rajaraman and Omer Wasim. Improved Bounds for Online Balanced Graph Re-Partitioning. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 83:1-83:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{rajaraman_et_al:LIPIcs.ESA.2022.83,
  author =	{Rajaraman, Rajmohan and Wasim, Omer},
  title =	{{Improved Bounds for Online Balanced Graph Re-Partitioning}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{83:1--83:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.83},
  URN =		{urn:nbn:de:0030-drops-170210},
  doi =		{10.4230/LIPIcs.ESA.2022.83},
  annote =	{Keywords: online algorithms, graph partitioning, competitive analysis}
}
Document
Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT

Authors: Omer Wasim and Valerie King

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)


Abstract
This paper initiates the study of the MAX-CUT problem in fully dynamic graphs. Given a graph G = (V,E), we present deterministic fully dynamic distributed and sequential algorithms to maintain a cut on G which always contains at least |E|/2 edges in sublinear update time under edge insertions and deletions to G. Our results include the following deterministic algorithms: i) an O(Δ) worst-case update time sequential algorithm, where Δ denotes the maximum degree of G, ii) the first fully dynamic distributed algorithm taking O(1) rounds and O(Δ) total bits of communication per update in the Massively Parallel Computation (MPC) model with n machines and O(n) words of memory per machine. The aforementioned algorithms require at most one adjustment, that is, a move of one vertex from one side of the cut to the other. We also give the following fully dynamic sequential algorithms: i) a deterministic O(m^{1/2}) amortized update time algorithm where m denotes the maximum number of edges in G during any sequence of updates and, ii) a randomized algorithm which takes Õ(n^{2/3}) worst-case update time when edge updates come from an oblivious adversary.

Cite as

Omer Wasim and Valerie King. Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{wasim_et_al:LIPIcs.FSTTCS.2020.33,
  author =	{Wasim, Omer and King, Valerie},
  title =	{{Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.33},
  URN =		{urn:nbn:de:0030-drops-132746},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.33},
  annote =	{Keywords: data structures, dynamic graph algorithms, approximate maximum cut, distributed computing, parallel computing}
}
  • Refine by Author
  • 2 Wasim, Omer
  • 1 King, Valerie
  • 1 Rajaraman, Rajmohan

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 approximate maximum cut
  • 1 competitive analysis
  • 1 data structures
  • 1 distributed computing
  • 1 dynamic graph algorithms
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2022

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