5 Search Results for "Ashlagi, Itai"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.12
Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment

Authors: Tomer Ezra, Stefano Leonardi, Michał Pawłowski, Matteo Russo, and Seeun William Umboh

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

Abstract
The online joint replenishment problem (JRP) is a fundamental problem in the area of online problems with delay. Over the last decade, several works have studied generalizations of JRP with different cost functions for servicing requests. Most prior works on JRP and its generalizations have focused on the clairvoyant setting. Recently, Touitou [Noam Touitou, 2023] developed a non-clairvoyant framework that provided an O(√{n log n}) upper bound for a wide class of generalized JRP, where n is the number of request types. We advance the study of non-clairvoyant algorithms by providing a simpler, modular framework that matches the competitive ratio established by Touitou for the same class of generalized JRP. Our key insight is to leverage universal algorithms for Set Cover to approximate arbitrary monotone subadditive functions using a simple class of functions termed disjoint. This allows us to reduce the problem to several independent instances of the TCP Acknowledgement problem, for which a simple 2-competitive non-clairvoyant algorithm is known. The modularity of our framework is a major advantage as it allows us to tailor the reduction to specific problems and obtain better competitive ratios. In particular, we obtain tight O(√n)-competitive algorithms for two significant problems: Multi-Level Aggregation and Weighted Symmetric Subadditive Joint Replenishment. We also show that, in contrast, Touitou’s algorithm is Ω(√{n log n})-competitive for both of these problems.
Cite as

Tomer Ezra, Stefano Leonardi, Michał Pawłowski, Matteo Russo, and Seeun William Umboh. Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ezra_et_al:LIPIcs.APPROX/RANDOM.2024.12,
  author =	{Ezra, Tomer and Leonardi, Stefano and Paw{\l}owski, Micha{\l} and Russo, Matteo and Umboh, Seeun William},
  title =	{{Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{12:1--12:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.12},
  URN =		{urn:nbn:de:0030-drops-210050},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.12},
  annote =	{Keywords: Set Cover, Joint Replenishment, TCP-Acknowledgment, Subadditive Function Approximation, Multi-Level Aggregation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.15
List Update with Delays or Time Windows

Authors: Yossi Azar, Shahar Lewkowicz, and Danny Vainstein

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We address the problem of List Update, which is considered one of the fundamental problems in online algorithms and competitive analysis. In this context, we are presented with a list of elements and receive requests for these elements over time. Our objective is to fulfill these requests, incurring a cost proportional to their position in the list. Additionally, we can swap any two consecutive elements at a cost of 1. The renowned "Move to Front" algorithm, introduced by Sleator and Tarjan, immediately moves any requested element to the front of the list. They demonstrated that this algorithm achieves a competitive ratio of 2. While this bound is impressive, the actual cost of the algorithm’s solution can be excessively high. For example, if we request the last half of the list, the resulting solution cost becomes quadratic in the list’s length. To address this issue, we consider a more generalized problem called List Update with Time Windows. In this variant, each request arrives with a specific deadline by which it must be served, rather than being served immediately. Moreover, we allow the algorithm to process multiple requests simultaneously, accessing the corresponding elements in a single pass. The cost incurred in this case is determined by the position of the furthest element accessed, leading to a significant reduction in the total solution cost. We introduce this problem to explore lower solution costs, but it necessitates the development of new algorithms. For instance, Move-to-Front fails when handling the simple scenario of requesting the last half of the list with overlapping time windows. In our work, we present a natural O(1) competitive algorithm for this problem. While the algorithm itself is intuitive, its analysis is intricate, requiring the use of a novel potential function. Additionally, we delve into a more general problem called List Update with Delays, where the fixed deadlines are replaced with arbitrary delay functions. In this case, the cost includes not only the access and swapping costs, but also penalties for the delays incurred until the requests are served. This problem encompasses a special case known as the prize collecting version, where a request may go unserved up to a given deadline, resulting in a specified penalty. For this more comprehensive problem, we establish an O(1) competitive algorithm. However, the algorithm for the delay version is more complex, and its analysis involves significantly more intricate considerations.
Cite as

Yossi Azar, Shahar Lewkowicz, and Danny Vainstein. List Update with Delays or Time Windows. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ICALP.2024.15,
  author =	{Azar, Yossi and Lewkowicz, Shahar and Vainstein, Danny},
  title =	{{List Update with Delays or Time Windows}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{15:1--15:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.15},
  URN =		{urn:nbn:de:0030-drops-201583},
  doi =		{10.4230/LIPIcs.ICALP.2024.15},
  annote =	{Keywords: Online, List Update, Delay, Time Window, Deadline}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.46
Tiered Random Matching Markets: Rank Is Proportional to Popularity

Authors: Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, and Geng Zhao

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

Abstract
We study the stable marriage problem in two-sided markets with randomly generated preferences. Agents on each side of the market are divided into a constant number of "soft" tiers, which capture agents' qualities. Specifically, every agent within a tier has the same public score, and agents on each side have preferences independently generated proportionally to the public scores of the other side. We compute the expected average rank which agents in each tier have for their partners in the man-optimal stable matching, and prove concentration results for the average rank in asymptotically large markets. Furthermore, despite having a significant effect on ranks, public scores do not strongly influence the probability of an agent matching to a given tier of the other side. This generalizes the results by Pittel [Pittel, 1989], which analyzed markets with uniform preferences. The results quantitatively demonstrate the effect of competition due to the heterogeneous attractiveness of agents in the market.
Cite as

Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, and Geng Zhao. Tiered Random Matching Markets: Rank Is Proportional to Popularity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ashlagi_et_al:LIPIcs.ITCS.2021.46,
  author =	{Ashlagi, Itai and Braverman, Mark and Saberi, Amin and Thomas, Clayton and Zhao, Geng},
  title =	{{Tiered Random Matching Markets: Rank Is Proportional to Popularity}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{46:1--46:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.46},
  URN =		{urn:nbn:de:0030-drops-135851},
  doi =		{10.4230/LIPIcs.ITCS.2021.46},
  annote =	{Keywords: Stable matching, stable marriage problem, tiered random markets, deferred acceptance}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.1
Min-Cost Bipartite Perfect Matching with Delays

Authors: Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer

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

Abstract
In the min-cost bipartite perfect matching with delays (MBPMD) problem, requests arrive online at points of a finite metric space. Each request is either positive or negative and has to be matched to a request of opposite polarity. As opposed to traditional online matching problems, the algorithm does not have to serve requests as they arrive, and may choose to match them later at a cost. Our objective is to minimize the sum of the distances between matched pairs of requests (the connection cost) and the sum of the waiting times of the requests (the delay cost). This objective exhibits a natural tradeoff between minimizing the distances and the cost of waiting for better matches. This tradeoff appears in many real-life scenarios, notably, ride-sharing platforms. MBPMD is related to its non-bipartite variant, min-cost perfect matching with delays (MPMD), in which each request can be matched to any other request. MPMD was introduced by Emek et al. (STOC'16), who showed an O(log^2(n)+log(Delta))-competitive randomized algorithm on n-point metric spaces with aspect ratio Delta. Our contribution is threefold. First, we present a new lower bound construction for MPMD and MBPMD. We get a lower bound of Omega(sqrt(log(n)/log(log(n)))) on the competitive ratio of any randomized algorithm for MBPMD. For MPMD, we improve the lower bound from Omega(sqrt(log(n))) (shown by Azar et al., SODA'17) to Omega(log(n)/log(log(n))), thus, almost matching their upper bound of O(log(n)). Second, we adapt the algorithm of Emek et al. to the bipartite case, and provide a simplified analysis that improves the competitive ratio to O(log(n)). The key ingredient of the algorithm is an O(h)-competitive randomized algorithm for MBPMD on weighted trees of height h. Third, we provide an O(h)-competitive deterministic algorithm for MBPMD on weighted trees of height h. This algorithm is obtained by adapting the algorithm for MPMD by Azar et al. to the apparently more complicated bipartite setting.
Cite as

Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer. Min-Cost Bipartite Perfect Matching with Delays. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ashlagi_et_al:LIPIcs.APPROX-RANDOM.2017.1,
  author =	{Ashlagi, Itai and Azar, Yossi and Charikar, Moses and Chiplunkar, Ashish and Geri, Ofir and Kaplan, Haim and Makhijani, Rahul and Wang, Yuyi and Wattenhofer, Roger},
  title =	{{Min-Cost Bipartite Perfect Matching with Delays}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.1},
  URN =		{urn:nbn:de:0030-drops-75509},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.1},
  annote =	{Keywords: online algorithms with delayed service, bipartite matching, competitive analysis}
}
Document
DOI: 10.4230/DagSemProc.05011.20
The Value of Correlation in Strategic Form Games

Authors: Itai Ashlagi, Dov Monderer, and Moshe Tennenholtz

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
Every game in strategic form can be extended by adding a correlation device. Any Equilibrium in such an extended game is called a correlated equilibrium (Aumann 1974). Aumann showed that there exist games, where the agents surplus in a correlated equilibrium is greater than their surplus in every equilibrium. This suggests the study of two major measures for the value of correlation: 1. The ratio between the maximal surplus obtained in an correlated equilibrium to the maximal surplus obtained in equilibrium. We refer to this ratio as the mediation value. 2. The ratio between the optimal surplus to the maximal surplus obtained in correlated equilibrium. We refer to this ratio as the enforcement value. In this work we initiate the study of the mediation value and of the enforcement value, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games, a class of games that received a lot attention in the recent computer science and e-commerce communities. Indeed, while much work in computer science has been devoted to the study of the ratio between the surplus in optimal strategies to the surplus in the worst Nash equilibrium (the so called "price of anarchy") for congestion games, our work presents and initiates the study of two other complementary measures.
Cite as

Itai Ashlagi, Dov Monderer, and Moshe Tennenholtz. The Value of Correlation in Strategic Form Games. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{ashlagi_et_al:DagSemProc.05011.20,
  author =	{Ashlagi, Itai and Monderer, Dov and Tennenholtz, Moshe},
  title =	{{The Value of Correlation in Strategic Form Games}},
  booktitle =	{Computing and Markets},
  pages =	{1--29},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.20},
  URN =		{urn:nbn:de:0030-drops-2317},
  doi =		{10.4230/DagSemProc.05011.20},
  annote =	{Keywords: Correlation, mediation, enforcement, equilibrium, mediator}
}
  • Refine by Author
  • 3 Ashlagi, Itai
  • 2 Azar, Yossi
  • 1 Braverman, Mark
  • 1 Charikar, Moses
  • 1 Chiplunkar, Ashish
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory and mechanism design
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 Correlation
  • 1 Deadline
  • 1 Delay
  • 1 Joint Replenishment
  • 1 List Update
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2024
  • 1 2005
  • 1 2017
  • 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