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

技術要約：分数ナップサック問題におけるグループベースのリソース配分モデル

問題定義
本論文は、各アイテムが値 $v_i$、コスト $w_i$、および容量制限 $u_i \in [0, 1]$ を持ち、総予算 $C$ に制約される有界分数ナップサック問題を扱う。目的は、$\sum w_i z_i \le C$ および $0 \le z_i \le u_i$ の条件下で、総価値 $\sum v_i z_i$ を最大化することである。

標準的な解法であるダンツィグの貪欲法（Dantzig's greedy rule）は、効率性比 $\rho_i = v_i/w_i$ によってアイテムを順序付け、予算を降順に割り当てる。この手法は最適ではあるものの、以下の2つの重大な問題点を抱えている：

1. 不連続性： 最適解のマッピングはリプシッツ連続ではない。コスト・データの微小な摂動によって、予算がほぼ同等の比率を持つ2つのアイテムの間で使い果たされた場合、配分が実行可能集合の極端な頂点間を跳躍してしまう。
2. 偽りのランキング： 解は、測定ノイズと区別がつかないほど微細な比率の違いに対して非常に敏感であり、真のデータ変動を反映しない不安定な配分を招く。

手法
これらの不安定性を緩和するために、著者は2段階のグループベース配分アルゴリズムを提案している：

1. メトリック・グルーピング（属性によるグループ化）： アイテムを属性空間 $(A, d)$ に基づいてグループに分割する。属性距離 $d(a_i, a_j)$ が許容半径 $\delta$ 以内にある場合、アイテム $i$ と $j$ は同一グループとされる。各グループ $G_k$ 内のアイテムは、代表属性 $b_{a_k}$、代表値 $b_{v_k}$、代表コスト $b_{w_k}$、および代表比率 $b_{\rho_k}$ を共有する。
2. 第1段階（グループ間配分）： グループを代表比率 $b_{\rho_k}$ の降順でランク付けする。予算が尽きるまで、グループに対して順次予算シェアを割り当てる。予算が尽きるグループが「境界グループ（boundary group）」($\Gamma$) と指定される。それより前のグループは全額が資金提供され、それ以降のグループへの配分はゼロとなる。
3. 第2段階（グループ内配分）： 境界グループ $\Gamma$ に対して、割り当てられた予算シェアを、さらなるランキングを行わずに分配する。この分配は「グループ内ルール」（実現可能性、予算クリアランス、および等価な保護）に従い、数学的には「ウォーターフィリング（water-filling）」メカニズムに等しい。具体的には、$\sum_{i \in \Gamma} w_i \min(u_i, \zeta) = c^*$ を満たす配分レベル $\zeta$ を求める（ここで $c^*$ は残余予算）。すべてのアイテム $i \in \Gamma$ は $\min(u_i, \zeta)$ を受け取る。

主要な貢献と理論的保証

• 安定性（リプシッツ連続性）： 正確な貪欲解とは異なり、グループ化された配分は、摂動が隣接するグループ間の分離マージン内に留まる限り、コストの摂動に対してリプシッツ連続である。連続性の係数は $K/w_{\min}$ であり、ここで $K$ は最大グループサイズである。これにより、ノイズによる配分の劇的な変化が防止される。
• 損失界（Loss Bounds）：
  • グループ内損失： グループ内の損失は、グループの容量 $U_G$ と相対的なコスト変動 $(w_+ - w_-)/(w_+ + w_-)$ に比例する項、および値の変動に関する項によって抑えられる。この境界はタイトであることが示されている。
  1. グローバル損失： グルーピングが「順序適合的（order-compatible）」（グループの比率区間が互いに素であり、厳密に減少している状態）である場合、総損失 $E(C)$ は完全に境界グループ $\Gamma$ 内に限定される。相対損失は $O(K/n)$ でスケールし、グループサイズ $K$ が有界であれば、アイテム数 $n$ が増加するにつれて誤差は減少する。
  2. 非順序適合的な場合： グループの比率区間が最大量 $\omega$ だけ重なる場合、誤差界に加法項 $\omega C$ が導入される。
• 計算量： アルゴリズムは $O(n + m \log m + |\Gamma| \log |\Gamma|)$ 時間で配分を計算する（$m$ はグループ数）。境界グループが線形時間選択によって特定される場合、計算量は $O(n + m \log m)$ に低下する。代表比率があらかじめソートされている場合は $O(n)$ となる。

実験結果
著者は、ランダムに生成されたインスタンスを用いて、提案手法をダンツィグの貪欲法と比較評価している：

• 損失 vs インスタンスサイズ ($n$)： 固定された許容誤差 $\delta$ に対して、相対損失は $n$ が非常に小さい場合（グループが単一要素の場合）はゼロである。$n$ が増加するにつれて損失は上昇し、その後一定のプラトー（実験では約6%）で安定する。これは、損失が $\delta$ に依存するが、大規模なインスタンスにおいては $n$ に依存しないという理論的予測を裏付けている。
• 損失 vs 許容誤差 ($\delta$)： 損失は $\delta$ に対して多項式的に増加する。$\delta$ が非常に小さい場合、損失は無視できるほど小さく、実質的に厳密な最適解と一致する。$\delta$ が大きくなると、グループ化が単一のグループへと崩壊するまで損失が増加し、その後飽和する。
• 実行時間： グループ化された手法は、ダンツィグの法則と同様の経験的な成長率を示す。小規模なインスタンスでは、グルーピングとソートによる一定のオーバーヘッドが発生するが、$n$ が大きい場合（最大 $10^6$ まで）、実行時間はほぼ区別がつかず、グループ化された手法は最大でも2倍程度の遅さにとどまる。

意義と主張
本論文は、グループ化された配分モデルが、最適性と安定性の実用的なトレードオフを提供すると主張している。属性差が解像度の閾値 $\delta$ を下回るアイテムのランキングを拒否することで、本手法は正確な解が持つ測定ノイズに対する偽りの敏感さを排除する。著者は、このアプローチが以下を実現すると述べている：

1. 実効可能領域と目的関数を保持しつつ、グループ内の内部配分ルールのみを制限する。
2. 正確な解には存在しない、有界な摂動商（リプシッツ定数）を提供する。
3. 標準的な貪欲法と同等の計算効率を維持しており、データの精度が限定的な大規模アプリケーションへの適用が可能である。

本研究は、多面体感度分析と数学的プログラミングにおける集計技術との架け橋として、システム全体の安定性を得るために（わずかな最適性の損失という観点での）「公平性の代償（price of fairness）」を提示している。