論文の概要: A Group-Based Resource Allocation Model for the Fractional Knapsack Problem
- arxiv url: http://arxiv.org/abs/2609.06470v2
- Date: Thu, 10 Sep 2026 06:23:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 23:53:35.044845
- Title: A Group-Based Resource Allocation Model for the Fractional Knapsack Problem
- Title（参考訳）: フラクショナル・クナプサック問題に対する群に基づく資源配分モデル
- Abstract要約: Dantzigのgreedyルールはその価値とコストの比率に応じてアイテムを注文する。
属性を共有する項目を半径$$でグループ化する。
これらのグループを下位の順に評価し、そのグループの予算シェアをそれ以上のランク付けなしに分割する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- 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.
- Abstract（参考訳）: 分数的なknapsack問題を解決するために、ダンツィヒのグリーディ・ルールは、その価値とコストの比率に応じてアイテムを注文する。
この順序付けは優先課題を導入します。
入力に対する任意に小さな摂動は、非常に類似した比率の2つの項目間で予算が枯渇した場合、割り当てを変更することができる。
その問題を緩和するため、2段階ルールを導入します。
属性を共有する項目を半径$δ$でグループ化する。
これらのグループを下位の順に評価し、そのグループの予算シェアをそれ以上のランク付けなしに分割する。
合計容量$U_G$、$[w^-,w^+]$に含まれる単位コスト、および代表値$\widehat{v}$を特徴とするグループを考える。
正確な最適値に対するグループの損失は、$\widehat{v}\, U_G\frac{w^+-w^-}{w^++w^-}+\varepsilon_v U_G$で制限される。
さらに、任意の群サイズに対して、この調和係数は厳密なままである。
全体としての損失は、グループ化が順序互換なままであれば、単一の予算拘束群に制限されるので、少なくとも$K$アイテムを含むグループは、$\mathcal{O}(\frac{K}{n})$のイテム当たりの損失を被ることになる。
群比間隔が少なくとも$ω$の重複を示すならば、加法項$ωC$はこの境界を分解する。
隣接群間の分離限界内において、群配置はコストデータに関してリプシッツ連続であり、$\frac{K}{w_{\min}}$である。
この割当を計算するには$\mathcal{O}(n+m\log m+|\|\log|\|)$m$群と境界群$\$を与えられる。
あるいは、時間複雑性が$\mathcal{O}(n+m\log m)$に落ちる場合、線形時間選択法が境界群の割り当てを特定する。
関連論文リスト
- Robust Learning of a Group DRO Neuron [21.632698901872843]
任意のラベルノイズと群レベルの分布シフトの存在下で,標準2乗損失下で原始ニューロンを学習する問題について検討した。
我々のフレームワークは、任意のラベルの破損やグループ固有の分布シフトに直面して、堅牢な学習保証を提供する。
論文 参考訳（メタデータ） (2026-01-26T04:00:53Z) - Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文 参考訳（メタデータ） (2025-06-30T13:27:39Z) - Variance-Dependent Regret Lower Bounds for Contextual Bandits [65.93854043353328]
これは従来の$tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$で改善されている。
論文 参考訳（メタデータ） (2025-03-15T07:09:36Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering [10.587553615723122]
すべてのクラスタ$C$とすべてのグループ$i in [ell]$に対して、$C$ from group $i$のポイントの数は、整数$t$の他のグループ$j in [ell]$のポイントの最大$t$の倍でなければならない。
我々は,$ell=2$が一般の均一容量$k$-medianに匹敵する難易度である場合においても,その問題を示す。
論文 参考訳（メタデータ） (2024-05-16T18:17:44Z) - Differentially Private Worst-group Risk Minimization [17.81078463701913]
本稿では,超過最悪の集団集団リスクを$tildeO(fracpsqrtdKepsilon + sqrtfracpK)$とするアルゴリズムを提案する。
我々の速度は、各分布がK/p$の固定サイズのデータセットによって観測されるときにほぼ最適である。
論文 参考訳（メタデータ） (2024-02-29T18:38:20Z) - Differentially Private Clustering in Data Streams [56.26040303056582]
私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。
当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Approximation Algorithms for Fair Range Clustering [14.380145034918158]
本稿では、データポイントが異なる人口集団のものであるフェアレンジクラスタリング問題について検討する。
目標は、各グループが少なくともセンターセットで最小限に表現されるように、最小クラスタリングコストで$k$センターを選択することである。
特に、fair range $ell_p$-clusteringは、特別なケースとして$k$-center、$k$-median、$k$-meansをキャプチャする。
論文 参考訳（メタデータ） (2023-06-11T21:18:40Z) - Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor
Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。
テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。
さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文 参考訳（メタデータ） (2022-07-15T11:55:09Z) - Fair Representation Clustering with Several Protected Classes [13.53362222844008]
我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。
我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
論文 参考訳（メタデータ） (2022-02-03T03:45:45Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。