Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources
Vineet Goyal, Garud Iyengar, Rajan Udwani
Abstract
Online Allocation of Reusable Resources: New Algorithms and Analytical Tools In the paper “Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources,” the authors develop novel algorithms and analysis techniques for online allocation of reusable resources. Their approach leads to an algorithm with the highest possible competitive ratio, a result that was previously out of reach with the algorithms and techniques that are used in classic settings in which resources are nonreusable. More generally, their LP-free analysis approach is useful for analyzing the performance of online algorithms for various other settings in which the standard primal-dual approach fails.
Topics & Concepts
Competitive analysisComputer scienceOnline algorithmAsymptotically optimal algorithmOptimal allocationMathematical optimizationResource allocationDual (grammatical number)Operations researchAlgorithmMathematicsUpper and lower boundsLiteratureComputer networkMathematical analysisArtOptimization and Search ProblemsAdvanced Bandit Algorithms ResearchAuction Theory and Applications