# Online Rounding Schemes for  k -Rental Problems

arXiv: https://arxiv.org/abs/2507.19649 · HTML: https://mlsanity.com/paper/2507.19649/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Online Multi-Class Selection with Group Fairness Guarantee](https://mlsanity.com/paper/2510.21055/) (2025)

## Abstract (arXiv)

We study two online resource allocation problems with reusability in an adversarial setting, namely kRental-Fixed and kRental-Variable. In both problems, a decision-maker manages k identical reusable units and faces a sequence of rental requests over time. We develop theoretically grounded relax-and-round algorithms with provable competitive ratio guarantees for both settings. For kRental-Fixed, we present an optimal randomized algorithm that achieves the best possible competitive ratio. The algorithm first computes an optimal fractional allocation using a price-based approach, and then applies a novel lossless online rounding scheme to obtain an integral solution. For kRental-Variable, we first establish the impossibility of achieving lossless online rounding. We then introduce a limited-correlation rounding technique that treats each unit independently while introducing controlled dependencies across allocation decisions involving the same unit. Combined with a carefully-crafted price-based method for computing the fractional allocation, this approach yields an order-optimal competitive ratio for the variable-duration setting.