4 Search Results for "Cohen, Ilan Reuven"

Document
DOI: 10.4230/LIPIcs.ESA.2023.35
Primal-Dual Schemes for Online Matching in Bounded Degree Graphs

Authors: Ilan Reuven Cohen and Binghui Peng

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We explore various generalizations of the online matching problem in a bipartite graph G as the b-matching problem [Kalyanasundaram and Pruhs, 2000], the allocation problem [Buchbinder et al., 2007], and the AdWords problem [Mehta et al., 2007] in a beyond-worst-case setting. Specifically, we assume that G is a (k, d)-bounded degree graph, introduced by Naor and Wajc [Naor and Wajc, 2018]. Such graphs model natural properties on the degrees of advertisers and queries in the allocation and AdWords problems. While previous work only considers the scenario where k ≥ d, we consider the interesting intermediate regime of k ≤ d and prove a tight competitive ratio as a function of k,d (under the small-bid assumption) of τ(k,d) = 1 - (1-k/d)⋅(1-1/d)^{d - k} for the b-matching and allocation problems. We exploit primal-dual schemes [Buchbinder et al., 2009; Azar et al., 2017] to design and analyze the corresponding tight upper and lower bounds. Finally, we show a separation between the allocation and AdWords problems. We demonstrate that τ(k,d) competitiveness is impossible for the AdWords problem even in (k,d)-bounded degree graphs.
Cite as

Ilan Reuven Cohen and Binghui Peng. Primal-Dual Schemes for Online Matching in Bounded Degree Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ESA.2023.35,
  author =	{Cohen, Ilan Reuven and Peng, Binghui},
  title =	{{Primal-Dual Schemes for Online Matching in Bounded Degree Graphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.35},
  URN =		{urn:nbn:de:0030-drops-186884},
  doi =		{10.4230/LIPIcs.ESA.2023.35},
  annote =	{Keywords: Online Matching, Primal-dual analysis, bounded-degree graph, the AdWords problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.43
A General Framework for Learning-Augmented Online Allocation

Authors: Ilan Reuven Cohen and Debmalya Panigrahi

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

Abstract
Online allocation is a broad class of problems where items arriving online have to be allocated to agents who have a fixed utility/cost for each assigned item so to maximize/minimize some objective. This framework captures a broad range of fundamental problems such as the Santa Claus problem (maximizing minimum utility), Nash welfare maximization (maximizing geometric mean of utilities), makespan minimization (minimizing maximum cost), minimization of 𝓁_p-norms, and so on. We focus on divisible items (i.e., fractional allocations) in this paper. Even for divisible items, these problems are characterized by strong super-constant lower bounds in the classical worst-case online model. In this paper, we study online allocations in the learning-augmented setting, i.e., where the algorithm has access to some additional (machine-learned) information about the problem instance. We introduce a general algorithmic framework for learning-augmented online allocation that produces nearly optimal solutions for this broad range of maximization and minimization objectives using only a single learned parameter for every agent. As corollaries of our general framework, we improve prior results of Lattanzi et al. (SODA 2020) and Li and Xian (ICML 2021) for learning-augmented makespan minimization, and obtain the first learning-augmented nearly-optimal algorithms for the other objectives such as Santa Claus, Nash welfare, 𝓁_p-minimization, etc. We also give tight bounds on the resilience of our algorithms to errors in the learned parameters, and study the learnability of these parameters.
Cite as

Ilan Reuven Cohen and Debmalya Panigrahi. A General Framework for Learning-Augmented Online Allocation. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 43:1-43:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ICALP.2023.43,
  author =	{Cohen, Ilan Reuven and Panigrahi, Debmalya},
  title =	{{A General Framework for Learning-Augmented Online Allocation}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{43:1--43:21},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.43},
  URN =		{urn:nbn:de:0030-drops-180952},
  doi =		{10.4230/LIPIcs.ICALP.2023.43},
  annote =	{Keywords: Algorithms with predictions, Scheduling algorithms, Online algorithms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.8
Truly Asymptotic Lower Bounds for Online Vector Bin Packing

Authors: János Balogh, Ilan Reuven Cohen, Leah Epstein, and Asaf Levin

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

Abstract
In this work, we consider online d-dimensional vector bin packing. It is known that no algorithm can have a competitive ratio of o(d/log² d) in the absolute sense, although upper bounds for this problem have always been presented in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure, and since the two measures are different, we focus on the asymptotic measure and prove new lower bounds of the asymptotic competitive ratio. The existing lower bounds prior to this work were known to be smaller than 3, even for very large d. Here, we significantly improved on the best known lower bounds of the asymptotic competitive ratio (and as a byproduct, on the absolute competitive ratio) for online vector packing of vectors with d ≥ 3 dimensions, for every dimension d. To obtain these results, we use several different constructions, one of which is an adaptive construction with a lower bound of Ω(√d). Our main result is that the lower bound of Ω(d/log² d) on the competitive ratio holds also in the asymptotic sense. This result holds also against randomized algorithms, and requires a careful adaptation of constructions for online coloring, rather than simple black-box reductions.
Cite as

János Balogh, Ilan Reuven Cohen, Leah Epstein, and Asaf Levin. Truly Asymptotic Lower Bounds for Online Vector Bin Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{balogh_et_al:LIPIcs.APPROX/RANDOM.2021.8,
  author =	{Balogh, J\'{a}nos and Cohen, Ilan Reuven and Epstein, Leah and Levin, Asaf},
  title =	{{Truly Asymptotic Lower Bounds for Online Vector Bin Packing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{8:1--8:18},
  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.8},
  URN =		{urn:nbn:de:0030-drops-147013},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.8},
  annote =	{Keywords: Bin packing, online algorithms, approximation algorithms, vector packing}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.10
Dynamic Pricing of Servers on Trees

Authors: Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Łukasz Jeż

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

Abstract
In this paper we consider the k-server problem where events are generated by selfish agents, known as the selfish k-server problem. In this setting, there is a set of k servers located in some metric space. Selfish agents arrive in an online fashion, each has a request located on some point in the metric space, and seeks to serve his request with the server of minimum distance to the request. If agents choose to serve their request with the nearest server, this mimics the greedy algorithm which has an unbounded competitive ratio. We propose an algorithm that associates a surcharge with each server independently of the agent to arrive (and therefore, yields a truthful online mechanism). An agent chooses to serve his request with the server that minimizes the distance to the request plus the associated surcharge to the server. This paper extends [Ilan Reuven Cohen et al., 2015], which gave an optimal k-competitive dynamic pricing scheme for the selfish k-server problem on the line. We give a k-competitive dynamic pricing algorithm for the selfish k-server problem on tree metric spaces, which matches the optimal online (non truthful) algorithm. We show that an alpha-competitive dynamic pricing scheme exists on the tree if and only if there exists alpha-competitive online algorithm on the tree that is lazy and monotone. Given this characterization, the main technical difficulty is coming up with such an online algorithm.
Cite as

Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Łukasz Jeż. Dynamic Pricing of Servers on Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.APPROX-RANDOM.2019.10,
  author =	{Cohen, Ilan Reuven and Eden, Alon and Fiat, Amos and Je\.{z}, {\L}ukasz},
  title =	{{Dynamic Pricing of Servers on Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{10:1--10:22},
  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.10},
  URN =		{urn:nbn:de:0030-drops-112252},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.10},
  annote =	{Keywords: Online algorithms, Online mechanisms, k-server problem, Online pricing}
}
  • Refine by Author
  • 4 Cohen, Ilan Reuven
  • 1 Balogh, János
  • 1 Eden, Alon
  • 1 Epstein, Leah
  • 1 Fiat, Amos
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Online algorithms
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Theory of computation → Algorithmic mechanism design
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 2 Online algorithms
  • 1 Algorithms with predictions
  • 1 Bin packing
  • 1 Online Matching
  • 1 Online mechanisms
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2023
  • 1 2019
  • 1 2021

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