4 Search Results for "Lavi, Ron"

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.2022.49
Optimal Deterministic Clock Auctions and Beyond

Authors: Giorgos Christodoulou, Vasilis Gkatzelis, and Daniel Schoepflin

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We design and analyze deterministic and randomized clock auctions for single-parameter domains with downward-closed feasibility constraints, aiming to maximize the social welfare. Clock auctions have been shown to satisfy a list of compelling incentive properties making them a very practical solution for real-world applications, partly because they require very little reasoning from the participating bidders. However, the first results regarding the worst-case performance of deterministic clock auctions from a welfare maximization perspective indicated that they face obstacles even for a seemingly very simple family of instances, leading to a logarithmic inapproximability result; this inapproximability result is information-theoretic and holds even if the auction has unbounded computational power. In this paper we propose a deterministic clock auction that achieves a logarithmic approximation for any downward-closed set system, using black box access to a solver for the underlying optimization problem. This proves that our clock auction is optimal and that the aforementioned family of instances exactly captures the information limitations of deterministic clock auctions. We then move beyond deterministic auctions and design randomized clock auctions that achieve improved approximation guarantees for a generalization of this family of instances, suggesting that the earlier indications regarding the performance of clock auctions may have been overly pessimistic.
Cite as

Giorgos Christodoulou, Vasilis Gkatzelis, and Daniel Schoepflin. Optimal Deterministic Clock Auctions and Beyond. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 49:1-49:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ITCS.2022.49,
  author =	{Christodoulou, Giorgos and Gkatzelis, Vasilis and Schoepflin, Daniel},
  title =	{{Optimal Deterministic Clock Auctions and Beyond}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{49:1--49:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.49},
  URN =		{urn:nbn:de:0030-drops-156453},
  doi =		{10.4230/LIPIcs.ITCS.2022.49},
  annote =	{Keywords: Auctions, Obvious Strategyproofness, Mechanism Design}
}
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}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.140
Deterministic Leader Election in Programmable Matter

Authors: Yuval Emek, Shay Kutten, Ron Lavi, and William K. Moses Jr.

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Addressing a fundamental problem in programmable matter, we present the first deterministic algorithm to elect a unique leader in a system of connected amoebots assuming only that amoebots are initially contracted. Previous algorithms either used randomization, made various assumptions (shapes with no holes, or known shared chirality), or elected several co-leaders in some cases. Some of the building blocks we introduce in constructing the algorithm are of interest by themselves, especially the procedure we present for reaching common chirality among the amoebots. Given the leader election and the chirality agreement building block, it is known that various tasks in programmable matter can be performed or improved. The main idea of the new algorithm is the usage of the ability of the amoebots to move, which previous leader election algorithms have not used.
Cite as

Yuval Emek, Shay Kutten, Ron Lavi, and William K. Moses Jr.. Deterministic Leader Election in Programmable Matter. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 140:1-140:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.ICALP.2019.140,
  author =	{Emek, Yuval and Kutten, Shay and Lavi, Ron and Moses Jr., William K.},
  title =	{{Deterministic Leader Election in Programmable Matter}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{140:1--140:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.140},
  URN =		{urn:nbn:de:0030-drops-107169},
  doi =		{10.4230/LIPIcs.ICALP.2019.140},
  annote =	{Keywords: programmable matter, geometric amoebot model, leader election}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022
  • 2 2019

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

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 1 Computing methodologies → Mobile agents
  • 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
  • Show More...

  • Refine by Keyword
  • 1 Algorithmic Game Theory
  • 1 Auctions
  • 1 Bayesian competitive ratio
  • 1 Bayesian ignorance
  • 1 Competitive Ratio
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact