Metraipolis › archive › dc_60701651b7cd
A Group-Based Resource Allocation Model for the Fractional Knapsack Problem — arXiv:2609.06470
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.06470
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T12:50:15.542Z
- SHA-256 of the archived text
785cbcf984ca7de1483f0c66f26d02a4f4e14829a32c81560296d096821e9806- Stable URL of this page
https://metraipolis.com/documento/dc_60701651b7cd
How to cite
A Group-Based Resource Allocation Model for the Fractional Knapsack Problem — arXiv:2609.06470 — arXiv (en), https://arxiv.org/abs/2609.06470 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_60701651b7cd (Metraipolis archive dc_60701651b7cd, sha256 785cbcf984ca7de1483f0c66f26d02a4f4e14829a32c81560296d096821e9806)
BibTeX
@misc{dc60701651b7cd,
title = {A Group-Based Resource Allocation Model for the Fractional Knapsack Problem — arXiv:2609.06470},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.06470},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_60701651b7cd; sha256 785cbcf984ca7de1483f0c66f26d02a4f4e14829a32c81560296d096821e9806},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06470. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
To solve the fractional knapsack problem, Dantzig's greedy rule orders items according to their value-to-cost ratio. This ordering introduces priority issues. An arbitrarily small perturbation to the input can change the allocation if the budget is exhausted between two items with very similar ratios. To mitigate that problem, we introduce a two-stage rule. We group items sharing attributes within a radius $\delta$. We then evaluate these groups in descending order of ratio and divide their group's budget share without further ranking. Consider a group featuring an aggregate capacity $U_G$, unit costs contained in $[w^-,w^+]$, and a representative value $\widehat{v}$. The group's loss relative to the exact optimum is bounded by $\widehat{v}\, U_G\frac{w^+-w^-}{w^++w^-}+\varepsilon_v U_G$, where $\varepsilon_v$ limits the group's internal value variation. Moreover, this harmonic factor remains tight for any group size. The overall loss becomes restricted to the single budget-binding group whenever the grouping remains order-compatible; thus, groups containing at most $K$ items suffer a per-item loss of $\mathcal{O}(\frac{K}{n})$. Should group ratio intervals exhibit an overlap of at most $\omega$, an additive term $\omega C$ degrades this bound. Within the separation margin between adjacent groups, the grouped allocation remains Lipschitz continuous with respect to cost data, exhibiting a modulus of $\frac{K}{w_{\min}}$. Computing this allocation takes $\mathcal{O}(n+m\log m+|\Gamma|\log|\Gamma|)$ time given $m$ groups and a boundary group $\Gamma$. Alternatively, the time complexity drops to $\mathcal{O}(n+m\log m)$ if a linear-time selection method identifies the boundary group's allocation.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-09 in cs.CL).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computation and Language (cs.CL).
Pagina del lavoro: https://arxiv.org/abs/2609.06470 — 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-16T12:30:25.267Z dalla pagina https://arxiv.org/catchup/cs.CL/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).