論文の概要: Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

• arxiv url: http://arxiv.org/abs/2610.05237v1
• Date: Sun, 04 Oct 2026 14:04:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 22:26:28.930928
• Title: Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations
• Title（参考訳）: 3次評価を用いた最大極小割当の計算複雑性の定式化
• Abstract要約: 我々は、平等主義的福祉を最大化する不可分な項目の割り当てを計算することの課題について検討する。 本結果は,3次評価を伴う最大最小割当の計算複雑性の完全な図式を提供する。
• 参考スコア（独自算出の注目度）: 5.242861402876323
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong to a small set. For additive valuations with values in $\{p,q\}$, where $q>p>0$ and $\gcd(p,q)=1$, we give a polynomial-time algorithm when $p=2$ and prove constant-gap hardness when $p\geq3$, already with exactly three high-valued goods per agent. We also give an $\sqrt{3/2}$-approximation for common positive bi-valued additive valuations. For mixed additive valuations in $\{-p,0,c\}$, where $p\in\{1,2\}$ and $c$ is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of $\{-2,0,c\}$-valuations. For submodular valuations with marginals in $\{-2,0,c\}$, where $c$ is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for $\{-1,0,1\}$-submodular valuations, we prove that no finite multiplicative approximation exists unless $\p=\np$. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations.
• Abstract（参考訳）: 我々は,エージェントの項目値や限界値が小さな集合に属する場合,平等福祉,すなわち最悪のエージェントの効用を最大化する不可分な項目の割り当てを計算することの課題について検討する。 ここで$q>p>0$ と $\gcd(p,q)=1$ の値を持つ加法評価について、$p=2$ のとき多項式時間アルゴリズムを与え、$p\geq3$ のとき定数ギャップ硬さを証明する。 また、共通の正の2値加法評価に対して$\sqrt{3/2}$-approximationを与える。 for mixed additive valuations in $\{-p,0,c\}$, where $p\in\{1,2\}$ and $c$ is a positive integer, a reduction to maximum-weight perfect matching is resolved tractability of $\{-2,0,c\}$-valuations。 ここでは、$c$が奇数であるような${-2,0,c\}$の辺値を持つ部分モジュラー評価に対して、単ギャップの厳密な硬度結果と指数的な値列の低い境界を、たとえ1つのエージェントを除くすべてが加法的であるとしても確立する。 最後に、$\{-1,0,1\}$-部分モジュラー評価に対して、$\p=\np$でない限り有限乗法近似は存在しないことを証明する。 その結果,3次評価を伴う最大最小割当の計算複雑性の完全な図式が得られた。

関連論文リスト

• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Generic Characteristic-Zero Equivalence Between Derivative Bézout Inversion and Multipoint Evaluation [0.0]
  固有正規化された Bezout 対 $s,t$ を $sZ+tZ'=1$ で満たし、$tm$ と $sm-1$ で計算する。 古典的積木アプローチでは、$O(M_K(m)log m)$フィールド演算が必要であり、$M_K(m)$は、$K$に対して次数-$m$sを乗算するコストを表す。 標数 0 の無限体上において、一般有理直線計画モデルにおいて、正準のすべての係数を計算することが証明される。
  論文  参考訳（メタデータ） (2026-08-28T03:42:18Z)
• Effective eigenvalue approximation from moments for self-adjoint trace-class operators [0.0]
  自己随伴のトレースクラス演算子 $O$ に対して、集合 $Lambda_nsubset mathbbR$ を定義する。 弱条件下ではハウスドルフ計量の$O$のスペクトルに収束することを示す。 結果は、量子情報、統計力学、量子熱力学などの問題に直接適用することができる。
  論文  参考訳（メタデータ） (2024-07-05T12:56:20Z)
• Estimating the Mixing Coefficients of Geometrically Ergodic Markov Processes [5.00389879175348]
  実数値の幾何学的エルゴード的マルコフ過程の個々の$beta$-mixing係数を1つのサンプルパスから推定する。 予想される誤差率は$mathcal O(log(n) n-1/2)$である。
  論文  参考訳（メタデータ） (2024-02-11T20:17:10Z)
• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
  論文  参考訳（メタデータ） (2023-10-13T14:52:46Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。 局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
  論文  参考訳（メタデータ） (2021-05-31T14:41:40Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。