A Group-Based Resource Allocation Model for the Fractional Knapsack Problem

arXiv:2609.06470v2 Announce Type: replace-cross 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 elta. 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_Gfrac{w^+-w^-}{w^++w^-}+arepsilon_v U_G, in which arepsilon_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 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 O(n+mlog m+|Gamma|log|Gamma|) time given m groups and a boundary group Gamma. Alternatively, the time complexity drops to O(n+mlog m) if a linear-time selection method identifies the boundary group's allocation.

Source: arXiv cs.CL | 2026-09-11