論文の概要: Exact Cut Complexity of Equal-Length Proportional Cake Cutting

• arxiv url: http://arxiv.org/abs/2610.19733v1
• Date: Wed, 14 Oct 2026 07:54:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:16.024894
• Title: Exact Cut Complexity of Equal-Length Proportional Cake Cutting
• Title（参考訳）: 等長比翼切断の特殊切断複雑さ
• Abstract要約: 等長制約下でのケーキカットについて検討した。 私たちの主な結果は、そのようなアロケーションを保証するのに必要な、最悪のカット数を決定します。
• 参考スコア（独自算出の注目度）: 3.217992121350522
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study proportional cake cutting under an equal-length constraint, where each of $n$ agents must receive a bundle of length exactly $1/n$ that is worth at least $1/n$ to that agent. Our main result determines the exact worst-case number of cuts needed to guarantee such an allocation, namely $2n-2$ for every $n$. This improves on the previously known quadratic upper bound. The proof combines the constrained necklace-splitting theorem with a recursive assignment argument based on Hall's theorem. The same bound extends to the stronger requirement of envy-freeness when $n$ is a prime power, and an $O(n^{1.525})$ upper bound holds for arbitrary $n$. We then ask whether such allocations can be computed. We first show that no deterministic protocol in the Robertson--Webb model terminates after finitely many queries on every instance and always returns an exact equal-length proportional allocation, even for two agents with identical valuations. For every $\varepsilon>0$, however, $O(n^2/\varepsilon)$ queries suffice to produce an allocation in which every agent receives a bundle of length exactly $1/n$ and value at least $1/n-\varepsilon$, again using at most $2n-2$ cuts. Finally, we augment the Robertson--Webb model with two-knife queries. We show that recursive balanced halving attains the optimal bound of $2n-2$ cuts when $n$ is a power of two. For arbitrary $n$, we give a procedure using $O(n\log n)$ cuts.
• Abstract（参考訳）: 我々は、同じ長さの制約の下で比例的なケーキカットを研究し、そこでは、各$n$エージェントが、そのエージェントに少なくとも1/n$のちょうど1/n$の長さの束を受けなければならない。 我々の主な成果は、そのような割り当てを保証するのに必要な最悪のカット数、すなわち$n$毎の$2n-2$を決定することです。 これにより、既知の二次上界が改善される。 この証明は、制約付きネックレス分割定理とホールの定理に基づく再帰的な代入論を組み合わせたものである。 同じ境界は、$n$ が素数であるときのエンビーフリーネスの強い要求にまで拡張され、$O(n^{1.525})$上界は任意の$n$に対して成り立つ。 次に、そのような割り当てを計算できるかどうかを問う。 まず、Robertson-Webbモデルにおける決定論的プロトコルは、全てのインスタンス上の有限個のクエリの後に終了せず、同じ評価を持つ2つのエージェントであっても、常に同じ長さの比例アロケーションを返すことを示す。 しかしすべての$\varepsilon>0$に対して、$O(n^2/\varepsilon)$クエリは、すべてのエージェントが正確に1/n$と少なくとも1/n-\varepsilon$のバンドルを受け取り、少なくとも2n-2$のカットを使用するようなアロケーションを生成するのに十分である。 最後に、2ナイフのクエリでRobertson-Webbモデルを拡張します。 再帰的均衡半減算は、$n$が2のパワーであるとき、最適な2n-2$カットの限界に達することを示す。 任意の$n$に対して、$O(n\log n)$ cutsを使用する手順を与える。

関連論文リスト

• Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization [55.29259818039367]
  支持領域がより均一な選択を許すにつれて、認証された近似係数がどのように改善されるかを示す。 明示的なパラメータの選択は、非遅延認証プロファイルに$underline_k()$を与える。 値保持丸めは、これらの保証をマトロイドとクナプサックの制約に転送する。
  論文  参考訳（メタデータ） (2026-10-02T20:52:38Z)
• 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)
• Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions [0.0]
  ソフトマックスアテンションのためのクエリ公開コアセット(英: query-oblivious coreset for a softmax-attention)は、ボール内の全てのクエリに対して、注意出力が$varepsilon$以内のキー値ペアのサブセットである。 カーネルインスタンスはボズザイ・ヴォス連鎖を適用でき、Chevetの不等式はキーを値次元から分割し、サイズ$O(e(sqrtd_vKleinsqrtd_klog(1+))$をランダム時間で与える。 クウェン全首の国勢調査
  論文  参考訳（メタデータ） (2026-09-06T01:23:58Z)
• Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
  我々は、シリアル量子アーキテクチャにおいて、$n$変換のみのユーザ間でバイナリユニニミティテストのための順序角符号化を導入する。 加法的代数にはベルの絡み合いは必要ないが、すべての正直な試行において、旅行者は局所的に極大に混合される。
  論文  参考訳（メタデータ） (2026-09-04T18:28:01Z)
• Sparse Quantum State Preparation with Sublinear T-Count [5.929956715430168]
  $$n$-qubit $s$-sparse状態は、$widetildeO(mins, n3/4sqrts+sqrtslog (1/)+log (1/)$ $T$ gatesを使ってエラーを発生させることができる。 0le$と2le sle 2n/2$に対して、スパース状態の準備には$(mins,sqrtns)$$Tが必要である。
  論文  参考訳（メタデータ） (2026-08-01T03:33:19Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
  論文  参考訳（メタデータ） (2026-07-22T17:27:20Z)
• $\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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)

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

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