1 Search Results for "Machluf, Chay"

Track A: Algorithms, Complexity and Games
Competitive Vertex Recoloring

Authors: Yossi Azar, Chay Machluf, Boaz Patt-Shamir, and Noam Touitou

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of n weighted vertices and a k-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper k-coloring of the vertices. The cost of a recoloring is the sum of weights of vertices whose color changed. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm. We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an O(log n)-competitive deterministic algorithm and an Ω(log n) lower bound on the competitive ratio of randomized algorithms. For (Δ+1)-coloring, we present tight bounds of Θ(Δ) and Θ(logΔ) on the competitive ratios of deterministic and randomized algorithms, respectively (where Δ denotes the maximum degree). We also consider a dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are weighted and the cost of recoloring a vertex is its weight. All our lower bounds hold even in the unweighted case.

Cite as

Yossi Azar, Chay Machluf, Boaz Patt-Shamir, and Noam Touitou. Competitive Vertex Recoloring. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

  author =	{Azar, Yossi and Machluf, Chay and Patt-Shamir, Boaz and Touitou, Noam},
  title =	{{Competitive Vertex Recoloring}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.13},
  URN =		{urn:nbn:de:0030-drops-163542},
  doi =		{10.4230/LIPIcs.ICALP.2022.13},
  annote =	{Keywords: coloring with recourse, anti-affinity constraints}
  • Refine by Author
  • 1 Azar, Yossi
  • 1 Machluf, Chay
  • 1 Patt-Shamir, Boaz
  • 1 Touitou, Noam

  • Refine by Classification
  • 1 Computer systems organization → Cloud computing
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 anti-affinity constraints
  • 1 coloring with recourse

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail