3 Search Results for "Shi, Yangguang"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.9
Optimal Competitive Ratio for Optimization Problems with Congestion Effects

Authors: Miriam Fischer, Dario Paccagnan, and Cosimo Vinci

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

Abstract
In this work we study online optimization problems with congestion effects. These are problems where tasks arrive online and a decision maker is required to allocate them on the fly to available resources in order to minimize the cost suffered, which grows with the amount of resources used. This class of problems corresponds to the online counterpart of well-known studied problems, including optimization problems with diseconomies of scale [Konstantin Makarychev and Maxim Sviridenko, 2018], minimum cost in congestion games [Gairing and Paccagnan, 2023], and load balancing problems [Baruch Awerbuch et al., 1995]. Within this setting, our work settles the problem of designing online algorithms with optimal competitive ratio, i.e., algorithms whose incurred cost is as close as possible to that of an oracle with complete knowledge of the future instance ahead of time. We provide three contributions underpinning this result. First, we show that no online algorithm can achieve a competitive ratio below a given factor depending solely on the resource costs. Second, we show that, when guided by carefully modified cost functions, the greedy algorithm achieves a competitive ratio matching this lower bound and thus is optimal. Finally, we show how to compute such modified cost functions in polynomial time.
Cite as

Miriam Fischer, Dario Paccagnan, and Cosimo Vinci. Optimal Competitive Ratio for Optimization Problems with Congestion Effects. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.APPROX/RANDOM.2025.9,
  author =	{Fischer, Miriam and Paccagnan, Dario and Vinci, Cosimo},
  title =	{{Optimal Competitive Ratio for Optimization Problems with Congestion Effects}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{9:1--9:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.9},
  URN =		{urn:nbn:de:0030-drops-243754},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.9},
  annote =	{Keywords: Online Algorithms, Competitive Ratio, Algorithmic Game Theory, Greedy Algorithms, Congestion Games}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.67
Online Paging with a Vanishing Regret

Authors: Yuval Emek, Shay Kutten, and Yangguang Shi

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

Abstract
This paper considers a variant of the online paging problem, where the online algorithm has access to multiple predictors, each producing a sequence of predictions for the page arrival times. The predictors may have occasional prediction errors and it is assumed that at least one of them makes a sublinear number of prediction errors in total. Our main result states that this assumption suffices for the design of a randomized online algorithm whose time-average regret with respect to the optimal offline algorithm tends to zero as the time tends to infinity. This holds (with different regret bounds) for both the full information access model, where in each round, the online algorithm gets the predictions of all predictors, and the bandit access model, where in each round, the online algorithm queries a single predictor. While online algorithms that exploit inaccurate predictions have been a topic of growing interest in the last few years, to the best of our knowledge, this is the first paper that studies this topic in the context of multiple predictors for an online problem with unbounded request sequences. Moreover, to the best of our knowledge, this is also the first paper that aims for (and achieves) online algorithms with a vanishing regret for a classic online problem under reasonable assumptions.
Cite as

Yuval Emek, Shay Kutten, and Yangguang Shi. Online Paging with a Vanishing Regret. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 67:1-67:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.ITCS.2021.67,
  author =	{Emek, Yuval and Kutten, Shay and Shi, Yangguang},
  title =	{{Online Paging with a Vanishing Regret}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{67:1--67:20},
  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.67},
  URN =		{urn:nbn:de:0030-drops-136065},
  doi =		{10.4230/LIPIcs.ITCS.2021.67},
  annote =	{Keywords: online paging, inaccurate predictions, multiple predictors, vanishing regret, full information vs. bandit access}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.45
Bayesian Generalized Network Design

Authors: Yuval Emek, Shay Kutten, Ron Lavi, and Yangguang Shi

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We study network coordination problems, as captured by the setting of generalized network design (Emek et al., STOC 2018), in the face of uncertainty resulting from partial information that the network users hold regarding the actions of their peers. This uncertainty is formalized using Alon et al.’s Bayesian ignorance framework (TCS 2012). While the approach of Alon et al. is purely combinatorial, the current paper takes into account computational considerations: Our main technical contribution is the development of (strongly) polynomial time algorithms for local decision making in the face of Bayesian uncertainty.
Cite as

Yuval Emek, Shay Kutten, Ron Lavi, and Yangguang Shi. Bayesian Generalized Network Design. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.ESA.2019.45,
  author =	{Emek, Yuval and Kutten, Shay and Lavi, Ron and Shi, Yangguang},
  title =	{{Bayesian Generalized Network Design}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{45:1--45:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.45},
  URN =		{urn:nbn:de:0030-drops-111660},
  doi =		{10.4230/LIPIcs.ESA.2019.45},
  annote =	{Keywords: approximation algorithms, Bayesian competitive ratio, Bayesian ignorance, generalized network design, diseconomies of scale, energy consumption, smoothness, best response dynamics}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021
  • 1 2019

  • Refine by Author
  • 2 Emek, Yuval
  • 2 Kutten, Shay
  • 2 Shi, Yangguang
  • 1 Fischer, Miriam
  • 1 Lavi, Ron
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Mathematical optimization
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Caching and paging algorithms
  • Show More...

  • Refine by Keyword
  • 1 Algorithmic Game Theory
  • 1 Bayesian competitive ratio
  • 1 Bayesian ignorance
  • 1 Competitive Ratio
  • 1 Congestion Games
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact