Fugu-MT 論文翻訳(概要): Online Primal-Dual Algorithms with Predictions for Packing Problems

論文の概要: Online Primal-Dual Algorithms with Predictions for Packing Problems

arxiv url: http://arxiv.org/abs/2110.00391v1
Date: Fri, 1 Oct 2021 13:19:18 GMT
ステータス: 処理完了
システム内更新日: 2021-10-04 19:57:46.933023
Title: Online Primal-Dual Algorithms with Predictions for Packing Problems
Title（参考訳）: パッキング問題に対する予測を伴うオンライン原始アルゴリズム
Authors: Nguyen Kim Thang and Christoph Durr
Abstract要約: 非線形パッキング問題の予測を行うアルゴリズムにフレームワークを提案する。最適境界が与えられる部分モジュラー設計、特にアドオークションにおいて、我々の枠組みを説明する。
参考スコア（独自算出の注目度）: 1.713291434132985
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The domain of online algorithms with predictions has been extensively studied for different applications such as scheduling, caching (paging), clustering, ski rental, etc. Recently, Bamas et al., aiming for an unified method, have provided a primal-dual framework for linear covering problems. They extended the online primal-dual method by incorporating predictions in order to achieve a performance beyond the worst-case case analysis. In this paper, we consider this research line and present a framework to design algorithms with predictions for non-linear packing problems. We illustrate the applicability of our framework in submodular maximization and in particular ad-auction maximization in which the optimal bound is given and supporting experiments are provided.
Abstract（参考訳）: 予測を伴うオンラインアルゴリズムのドメインは、スケジューリング、キャッシュ(ページング)、クラスタリング、スキーレンタルなど、さまざまなアプリケーションで広く研究されている。近年,統一手法をめざすBamasらは,線形被覆問題に対する原始双対の枠組みを提供している。彼らは、最悪のケース分析以上のパフォーマンスを達成するために、予測を組み込むことで、オンライン原始的手法を拡張した。本稿では,この研究ラインを考察し,非線形パッキング問題に対する予測を伴うアルゴリズム設計フレームワークを提案する。準モジュラー最大化における我々のフレームワークの適用性、特に最適境界が与えられ、支援実験が提供される吸着最大化について説明する。

関連論文リスト

Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
論文参考訳（メタデータ） (2024-03-12T08:40:21Z)
Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。本手法は, 精度の高い問題に特に適している。提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
論文参考訳（メタデータ） (2023-11-08T00:10:21Z)
Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文参考訳（メタデータ） (2023-01-30T13:17:15Z)
Rollout Algorithms and Approximate Dynamic Programming for Bayesian Optimization and Sequential Estimation [0.0]
逐次推定を含む様々な問題に適用可能な、統一された近似的動的プログラミングフレームワークを提供する。まず,最適化を目的とした代理コスト関数の構築を検討し,ベイズ最適化の特別な場合に着目した。次に、最適測定選択を用いた確率ベクトルの逐次推定のより一般的な場合とその適応制御問題への応用について述べる。
論文参考訳（メタデータ） (2022-12-15T17:50:23Z)
Learning-Augmented Algorithms for Online Linear and Semidefinite Programming [9.849604820019394]
Semidefinite Programming (SDP) は線形および二次的に制約されたプログラミングを一般化する統一フレームワークである。 SDPをカバーするための制約がオンラインに届くと、最適解を近似するためには、既知の不可能な結果が存在する。予測器が正確であれば、これらの不可能な結果を効率よく回避し、最適解に対する定数係数近似を達成できることが示される。
論文参考訳（メタデータ） (2022-09-21T19:16:29Z)
Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文参考訳（メタデータ） (2022-02-21T13:18:11Z)
Parsimonious Learning-Augmented Caching [29.975391787684966]
本稿では,学習補助アルゴリズムが同時に予測を利用できるような設定を導入し,研究する。定量的に類似した結果が得られるが、予測のサブ線形数のみを用いることを示す。
論文参考訳（メタデータ） (2022-02-09T03:40:11Z)
Model-Based Domain Generalization [96.84818110323518]
本稿では,モデルベースドメイン一般化問題に対する新しいアプローチを提案する。我々のアルゴリズムは、最新のwildsベンチマークの最先端手法を最大20ポイント上回った。
論文参考訳（メタデータ） (2021-02-23T00:59:02Z)
The Primal-Dual method for Learning Augmented Algorithms [10.2730668356857]
我々は、オンラインアルゴリズムの原始二重法を拡張し、次のアクションについてオンラインアルゴリズムにアドバイスする予測を組み込む。我々のアルゴリズムは、予測が正確である場合にも、予測が誤解を招くとき、適切な保証を維持しながら、どのオンラインアルゴリズムよりも優れていることを示す。
論文参考訳（メタデータ） (2020-10-22T11:58:47Z)
Bandit Data-Driven Optimization [62.01362535014316]
機械学習パイプラインが設定で有用になるためには、克服しなければならない大きな問題点が4つある。これらの問題点に対処する最初の反復予測記述フレームワークであるBanditデータ駆動最適化を導入する。本稿では,このフレームワークの新しいアルゴリズム PROOF を提案する。
論文参考訳（メタデータ） (2020-08-26T17:50:49Z)
Extrapolation-based Prediction-Correction Methods for Time-varying Convex Optimization [5.768816587293478]
本稿では,予測補正パラダイムに基づくオンライン最適化のアルゴリズムについて論じる。本稿では,外挿に基づく新しい予測手法を提案する。本稿では,信号処理や機械学習,ロボット工学といった問題に適用したアルゴリズムの経験的性能について論じる。
論文参考訳（メタデータ） (2020-04-24T12:48:13Z)

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