[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3580507.3597803acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article

Online Resource Allocation with Buyback: Optimal Algorithms via Primal-Dual

Published: 07 July 2023 Publication History

Abstract

Motivated by applications in cloud computing spot markets and selling banner ads on popular websites, we study the online resource allocation problem with costly buyback. To model this problem, we consider the classic edge-weighted fractional online matching problem with a tweak, where the decision maker can recall (i.e., buyback) any fraction of an offline resource that is pre-allocated to an earlier online vertex; however, by doing so not only the decision maker loses the previously allocated reward (which equates the edge-weight), it also has to pay a non-negative constant factor f of this edge-weight as an extra penalty. Parameterizing the problem by the buyback factor f, our main result is obtaining optimal competitive algorithms for all possible values of f through a novel primal-dual family of algorithms. We establish the optimality of our results by obtaining separate lower-bounds for each of small and large buyback factor regimes, and showing how our primal-dual algorithm exactly matches this lower-bound by appropriately tuning a parameter as a function of f. The optimal competitive ratio Γgen(f) and the optimal competitive ratio Γdet-int(f) of deterministic integral algorithms are as follows,
[EQUATION]
where W−1 : [−1/e, 0) → (−∞, −1] is the non-principal branch of the Lambert W function.

Cited By

View all
  • (undefined)Online Assortment of Reusable Resources with Exogenous ReplenishmentSSRN Electronic Journal10.2139/ssrn.3795056

Index Terms

  1. Online Resource Allocation with Buyback: Optimal Algorithms via Primal-Dual

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      EC '23: Proceedings of the 24th ACM Conference on Economics and Computation
      July 2023
      1253 pages
      ISBN:9798400701047
      DOI:10.1145/3580507
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 07 July 2023

      Permissions

      Request permissions for this article.

      Check for updates

      Qualifiers

      • Research-article

      Conference

      EC '23
      Sponsor:
      EC '23: 24th ACM Conference on Economics and Computation
      July 9 - 12, 2023
      London, United Kingdom

      Acceptance Rates

      Overall Acceptance Rate 664 of 2,389 submissions, 28%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)30
      • Downloads (Last 6 weeks)2
      Reflects downloads up to 12 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (undefined)Online Assortment of Reusable Resources with Exogenous ReplenishmentSSRN Electronic Journal10.2139/ssrn.3795056

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media