Metraipolis › archive › dc_dee91c75254d
Efficient Algorithms for Online Subadditive Combinatorial Allocations — arXiv:2610.09050
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.09050
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:49:41.208Z
- SHA-256 of the archived text
7947538a323340b4b8abb5ec8c79fd4c67631a2ff784bcb589ab1bd41eeea5f5- Stable URL of this page
https://metraipolis.com/documento/dc_dee91c75254d
How to cite
Efficient Algorithms for Online Subadditive Combinatorial Allocations — arXiv:2610.09050 — arXiv (en), https://arxiv.org/abs/2610.09050 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dee91c75254d (Metraipolis archive dc_dee91c75254d, sha256 7947538a323340b4b8abb5ec8c79fd4c67631a2ff784bcb589ab1bd41eeea5f5)
BibTeX
@misc{dcdee91c75254d,
title = {Efficient Algorithms for Online Subadditive Combinatorial Allocations — arXiv:2610.09050},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.09050},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dee91c75254d; sha256 7947538a323340b4b8abb5ec8c79fd4c67631a2ff784bcb589ab1bd41eeea5f5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09050. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For the online combinatorial allocation problem with subadditive valuations, Correa and Cristi (STOC 2023) proved the existence of a $6$-competitive online algorithm, improving on the previous best $O(\log\!\log m)$-competitive online algorithm due to Dütting, Kesselheim, and Lucier (FOCS 2020), where $m$ is the number of items. However, Correa and Cristi's result is existential, and it was left open whether a constant competitive ratio is attainable via an efficient online algorithm that uses a polynomial number of demand oracle queries. In this work, we answer this affirmatively, giving an expected-polynomial-time $(6 + \epsilon)$-competitive online algorithm for any constant $\epsilon > 0$. Our techniques also recover, in the offline setting, the $(2 + \epsilon)$-approximation result of Feige (STOC, 2006). Finally, when the buyers' valuations are drawn from identical distributions, we exploit symmetry to obtain an improved $(60/11+\epsilon)$-competitive algorithm. Starting with the natural configuration LP relaxation for the problem, our main technical contribution is a recursive Bundle Score Generator (BSG) that resolves item conflicts by assigning correlated scores to the items requested by each buyer. Unlike the Random Score Generator whose existence is shown by Correa and Cristi, our BSG is efficiently computable in expected polynomial time. Moreover, it satisfies a stochastic dominance property that is sufficient to recover both Feige's offline result and Correa and Cristi's online result. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2610.09050 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-08T12:19:30.197Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).