Search Results

Documents authored by Touitou, Noam

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.105
Frameworks for Nonclairvoyant Network Design with Deadlines or Delay

Authors: Noam Touitou

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Clairvoyant network design with deadlines or delay has been studied extensively, culminating in an O(log n)-competitive general framework, where n is the number of possible request types (Azar and Touitou, FOCS 2020). In the nonclairvoyant setting, the problem becomes much harder, as Ω(√n) lower bounds are known for certain problems (Azar et al., STOC 2017). However, no frameworks are known for the nonclairvoyant setting, and previous work focuses only on specific problems, e.g., multilevel aggregation (Le et al., SODA 2023). In this paper, we present the first nonclairvoyant frameworks for network design with deadlines or delay. These frameworks are nearly optimal: their competitive ratio is Õ(√n), which matches known lower bounds up to logarithmic factors.
Cite as

Noam Touitou. Frameworks for Nonclairvoyant Network Design with Deadlines or Delay. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 105:1-105:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{touitou:LIPIcs.ICALP.2023.105,
  author =	{Touitou, Noam},
  title =	{{Frameworks for Nonclairvoyant Network Design with Deadlines or Delay}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{105:1--105:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.105},
  URN =		{urn:nbn:de:0030-drops-181578},
  doi =		{10.4230/LIPIcs.ICALP.2023.105},
  annote =	{Keywords: Online, Deadlines, Delay, Network Design, Nonclairvoyant}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.16
Distortion-Oblivious Algorithms for Scheduling on Multiple Machines

Authors: Yossi Azar, Eldad Peretz, and Noam Touitou

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We consider the classic online problem of scheduling on multiple machines to minimize total flow time and total stretch where the input consists of estimates on the processing time provided for each job once released. The performance of such algorithms should depend on μ, the error in the estimates of the processing time for that instance (such an algorithm is called a distortion oblivious algorithm). Previously, a distortion oblivious algorithm to minimize flow time was provided only for a single machine. In this paper we extend the work to multiple machines and also consider the total stretch objective. In particular, we design a non-migrative distortion oblivious algorithm to minimize total flow time with a competitive ratio of O(μ log P), where P is the ratio between the maximum to minimum processing time. We show that with immediate-dispatching one cannot achieve a competitive ratio which is a function of μ and P; moreover, a competitive ratio which is sub-polynomial in the number of jobs is also impossible. We also present the first distortion-oblivious algorithm for minimizing the stretch time, both on a single and on multiple machines. The competitive ratio of these algorithms are O(μ²) which is optimal as we also prove a matching Ω(μ²) lower bound.
Cite as

Yossi Azar, Eldad Peretz, and Noam Touitou. Distortion-Oblivious Algorithms for Scheduling on Multiple Machines. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ISAAC.2022.16,
  author =	{Azar, Yossi and Peretz, Eldad and Touitou, Noam},
  title =	{{Distortion-Oblivious Algorithms for Scheduling on Multiple Machines}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.16},
  URN =		{urn:nbn:de:0030-drops-173010},
  doi =		{10.4230/LIPIcs.ISAAC.2022.16},
  annote =	{Keywords: Online, Scheduling, Predictions, Stretch, Flow Time}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.13
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)

Abstract
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

@InProceedings{azar_et_al:LIPIcs.ICALP.2022.13,
  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.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}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.53
Nearly-Tight Lower Bounds for Set Cover and Network Design with Deadlines/Delay

Authors: Noam Touitou

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
In network design problems with deadlines/delay, an algorithm must make transmissions over time to satisfy connectivity requests on a graph. To satisfy a request, a transmission must be made that provides the desired connectivity. In the deadline case, this transmission must occur inside a time window associated with the request. In the delay case, the transmission should be as soon as possible after the request’s release, to avoid delay cost. In FOCS 2020, frameworks were given which reduce a network design problem with deadlines/delay to its classic, offline variant, while incurring an additional competitiveness loss factor of O(log n), where n is the number of vertices in the graph. Trying to improve upon this loss factor is thus a natural research direction. The frameworks of FOCS 2020 also apply to set cover with deadlines/delay, in which requests arrive on the elements of a universe over time, and the algorithm must transmit sets to serve them. In this problem, a universe of sets and elements is given, requests arrive on elements over time, and the algorithm must transmit sets to serve them. In this paper, we give nearly tight lower bounds for set cover with deadlines/delay. These lower bounds imply nearly-tight lower bounds of Ω(log n / log log n) for a few network design problems, such as node-weighted Steiner forest and directed Steiner tree. Our results imply that the frameworks in FOCS 2020 are essentially optimal, and improve quadratically over the best previously-known lower bounds.
Cite as

Noam Touitou. Nearly-Tight Lower Bounds for Set Cover and Network Design with Deadlines/Delay. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{touitou:LIPIcs.ISAAC.2021.53,
  author =	{Touitou, Noam},
  title =	{{Nearly-Tight Lower Bounds for Set Cover and Network Design with Deadlines/Delay}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.53},
  URN =		{urn:nbn:de:0030-drops-154865},
  doi =		{10.4230/LIPIcs.ISAAC.2021.53},
  annote =	{Keywords: Network Design, Deadlines, Delay, Online, Set Cover}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.8
Set Cover with Delay - Clairvoyance Is Not Required

Authors: Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou

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

Abstract
In most online problems with delay, clairvoyance (i.e. knowing the future delay of a request upon its arrival) is required for polylogarithmic competitiveness. In this paper, we show that this is not the case for set cover with delay (SCD) - specifically, we present the first non-clairvoyant algorithm, which is O(log n log m)-competitive, where n is the number of elements and m is the number of sets. This matches the best known result for the classic online set cover (a special case of non-clairvoyant SCD). Moreover, clairvoyance does not allow for significant improvement - we present lower bounds of Ω(√{log n}) and Ω(√{log m}) for SCD which apply for the clairvoyant case. In addition, the competitiveness of our algorithm does not depend on the number of requests. Such a guarantee on the size of the universe alone was not previously known even for the clairvoyant case - the only previously-known algorithm (due to Carrasco et al.) is clairvoyant, with competitiveness that grows with the number of requests. For the special case of vertex cover with delay, we show a simpler, deterministic algorithm which is 3-competitive (and also non-clairvoyant).
Cite as

Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou. Set Cover with Delay - Clairvoyance Is Not Required. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ESA.2020.8,
  author =	{Azar, Yossi and Chiplunkar, Ashish and Kutten, Shay and Touitou, Noam},
  title =	{{Set Cover with Delay - Clairvoyance Is Not Required}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{8:1--8:21},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.8},
  URN =		{urn:nbn:de:0030-drops-128749},
  doi =		{10.4230/LIPIcs.ESA.2020.8},
  annote =	{Keywords: Set Cover, Delay, Clairvoyant}
}
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 About DROPS Imprint Privacy Contact