論文の概要: Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items

• arxiv url: http://arxiv.org/abs/2610.40290v2
• Date: Sat, 31 Oct 2026 19:34:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-04 23:36:30.371381
• Title: Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items
• Title（参考訳）: 取り外し可能なアイテムを用いたオンラインKnapsackのリコースとサイズ境界の活用
• Abstract要約: オンライン・アンウェイト・クナプサック問題では、アイテムは順次到着し、バウンド・キャパシティ・クナプサックに対して受け入れられ、即時に拒否されなければならない。 この不可避性を回避している本質的な緩和は、以前は受け入れられていたアイテムをクナップサックから取り除くことである。 項目サイズ上の上限があまり制限されない場合、最もよく知られた競合比の大幅な改善が可能であることを示す。
• 参考スコア（独自算出の注目度）: 12.379819330585159
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the online unweighted knapsack problem, items arrive sequentially and must be accepted or rejected immediately for a bounded-capacity knapsack, aiming to maximize the total size of accepted items. When decisions are irrevocable, no algorithm achieves a non-trivial competitive ratio. An essential relaxation that circumvents this impossibility is to allow previously accepted items to be removed from the knapsack (a.k.a. removal). In this work, we investigate possible further improvements on the competitive ratio with removal by bringing together two other previously proposed model extensions: knowledge of an upper bound on the item sizes (a.k.a. bound awareness) and ability to reinsert previously rejected items(a.k.a.recourse). Our contributions are twofold. First, we establish close upper and lower bounds on the competitive ratio under bound awareness, removal and recourse. We show that significant improvements on the best known competitive ratio are possible when the upper bound on the item sizes is not too restrictive and only few uses of recourse are available. Second, we introduce the notion of adaptive online algorithms which do not require to know any upper bound on the item sizes but still achieve performance guarantees comparable to the ones obtained under the bound awareness model.
• Abstract（参考訳）: オンライン・アンウェイト・クナプサック問題では、アイテムは順次到着し、許容されるアイテムの総サイズを最大化するために、バウンド・キャパシティ・クナプサックに対して直ちに受理または拒絶されなければならない。 決定が無効であれば、アルゴリズムが非自明な競合比を達成することはない。 この不可避性を回避している本質的な緩和は、以前は受け入れられていたアイテムをクナプサックから取り除くことである(つまり取り除く)。 本研究では,従来提案されていた2つのモデル拡張 – アイテムサイズ(すなわち有界認識)上界の知識と,以前に拒否されたアイテム(a.k.a.recourse)を再試行する能力 – を組み込むことで,競合比のさらなる改善の可能性を検討する。 私たちの貢献は2倍です。 第一に、我々は、限定された認識、排除、リコースの下で、競争率の上下境界を確立する。 項目サイズ上の上限があまり制限的ではなく、リコースの利用がほとんどない場合に、最もよく知られた競争率の大幅な改善が可能であることを示す。 第二に,適応型オンラインアルゴリズムの概念は,アイテムサイズ上の上限を知る必要はなく,それでも有界認識モデルで得られた値に匹敵する性能保証を達成できる。

関連論文リスト

• Efficient Recommendation with Millions of Items by Dynamic Pruning of Sub-Item Embeddings [63.117573355917465]
  そこで本稿では,大規模項目カタログにおける最上位項目の探索を効率的に行う動的プルーニングアルゴリズムを提案する。 我々のRecJPQPruneアルゴリズムは、理論的には、上位K候補リストから潜在的に上位の項目が除外されないことを保証しているため、安全である。 本研究では,RecJPQPrune を用いた2つの大規模データセットと3つの推奨モデルによる評価実験を行った。
  論文  参考訳（メタデータ） (2025-05-01T14:36:33Z)
• Improved Regret Bounds for Online Fair Division with Bandit Learning [0.0]
  アイテムの種類が有限であればオンラインフェアディビジョンを学習し、そのアイテムのプレイヤー値は未知の方法で分布からランダムに描画される。 この設定では、分割不可能なアイテムの列がランダムなオンラインプロセスに従って到着し、各アイテムは1人のプレイヤーに割り当てられなければならない。 高い確率で比例制約満足度を保証し、$tildeO(sqrtT)$ regretを達成できることが示される。
  論文  参考訳（メタデータ） (2025-01-13T02:48:58Z)
• Information Capacity Regret Bounds for Bandits with Mediator Feedback [55.269551124587224]
  我々は,政策セットの複雑さに対する情報理論尺度として,政策セットの容量を導入する。 古典的なEXP4アルゴリズムを採用することで、ポリシーセットの容量に応じて、新たな後悔の限界を提供する。 ポリシーセットファミリの選択については、キャパシティと同じようなスケールで、ほぼ整合性の低い境界を証明します。
  論文  参考訳（メタデータ） (2024-02-15T19:18:47Z)
• Cascading Reinforcement Learning [21.267106043818792]
  カスケードバンディットモデルでは、各タイムステップにおいて、エージェントはアイテムのプールから注文されたアイテムのサブセットを推奨し、それぞれが未知のアトラクション確率に関連付けられている。 本稿では,ユーザ状態と状態遷移が意思決定に与える影響を考慮し,一般化されたカスケーディングRLフレームワークを提案する。 カスケード RL では、大きなアトラクション確率を持つだけでなく、優れた後継状態につながる項目を選択する必要がある。 そこで我々はCascadingVIとCascadingBPIの2つのアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-01-17T04:20:26Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。 本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T21:59:30Z)
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning [50.44564503645015]
  有限エピソードマルコフ決定過程における強化学習のための改良されたギャップ依存的後悔境界を提供する。 楽観的なアルゴリズムでは,より強い後悔境界を証明し,多数のMDPに対して新たな情報理論的下限を伴う。
  論文  参考訳（メタデータ） (2021-07-02T20:36:05Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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