{"ID":2890651,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.19649","arxiv_id":"2507.19649","title":"Online Rounding Schemes for $ k $-Rental Problems","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2507.19649","url_pdf":"https://arxiv.org/pdf/2507.19649v2","authors":"[\"Hossein Nekouyan\",\"Bo Sun\",\"Raouf Boutaba\",\"Xiaoqi Tan\"]","published":"2025-07-25T19:52:03Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}