arXiv preprint ·
A Group-Based Resource Allocation Model for the Fractional Knapsack Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $δ$. These groups are then evaluated 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 compared to the exact optimum is bounded by $\widehat{v}\, U_G\frac{w^+-w^-}{w^++w^-}+\varepsilon_v U_G$, in which $\varepsilon_v$ limits the group's internal value variation. Moreover, for any group size, this harmonic factor remains tight. 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 $ω$, an additive term $ω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+|Γ|\log|Γ|)$ time given $m$ groups and a boundary group $Γ$. Alternatively, the time complexity drops to $\mathcal{O}(n+m\log m)$ if a linear-time selection method identifies the boundary group's allocation.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
1.73-Optimal Echelon Stock (R,nQ) Policies in Two-Stage Stochastic Serial Systems
Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler
Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions
Smoothed Picard Hamiltonian Monte Carlo
Computation and Applications of Euclidean and Normed Representations of Massive Data
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.