論文の概要: Learning Augmented Online Facility Location

• arxiv url: http://arxiv.org/abs/2107.08277v1
• Date: Sat, 17 Jul 2021 16:44:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-20 14:40:08.945000
• Title: Learning Augmented Online Facility Location
• Title（参考訳）: オンライン施設立地の学習
• Authors: Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, Nikolas Patris
• Abstract要約: 最適施設の位置に関する不完全な予測を生かしたオンライン施設位置情報(OFL)のオンラインアルゴリズムを提案する。 競合比は, 要求数から一定までにおいて, 下位対数から円滑に減少することが証明された。 アルゴリズムの競合比の誤差への依存性が最適であることを示す。
• 参考スコア（独自算出の注目度）: 11.401250502020503
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Following the research agenda initiated by Munoz & Vassilvitskii [1] and Lykouris & Vassilvitskii [2] on learning-augmented online algorithms for classical online optimization problems, in this work, we consider the Online Facility Location problem under this framework. In Online Facility Location (OFL), demands arrive one-by-one in a metric space and must be (irrevocably) assigned to an open facility upon arrival, without any knowledge about future demands. We present an online algorithm for OFL that exploits potentially imperfect predictions on the locations of the optimal facilities. We prove that the competitive ratio decreases smoothly from sublogarithmic in the number of demands to constant, as the error, i.e., the total distance of the predicted locations to the optimal facility locations, decreases towards zero. We complement our analysis with a matching lower bound establishing that the dependence of the algorithm's competitive ratio on the error is optimal, up to constant factors. Finally, we evaluate our algorithm on real world data and compare our learning augmented approach with the current best online algorithm for the problem.
• Abstract（参考訳）: 従来のオンライン最適化問題に対する学習強化オンラインアルゴリズムについて,Munoz & Vassilvitskii [1] と Lykouris & Vassilvitskii [2] が提唱した研究課題に続き,本研究ではオンライン施設配置問題について考察する。 オンライン施設位置情報(OFL)では、要求はメートル法空間で1対1で到着し、到着時に(不可解に)将来の要求について何も知らないままオープンな施設に割り当てられなければならない。 最適施設の位置の予測に不完全な可能性を生かしたOFLのオンラインアルゴリズムを提案する。 その結果, 予測位置と最適施設位置の合計距離の誤差がゼロに減少するため, 要求数を一定にすることで, 競争比が亜対数から一定までスムーズに減少することが判明した。 我々は、アルゴリズムの競合比の誤差に対する依存性が一定因子まで最適であることを示す、一致する下限値で解析を補完する。 最後に,本アルゴリズムを実世界データ上で評価し,学習拡張手法と現在の最良のオンラインアルゴリズムを比較した。

関連論文リスト

• Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
  本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。 この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。 我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
  論文  参考訳（メタデータ） (2024-05-06T17:38:20Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [56.92236659731376]
  本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。 決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
  論文  参考訳（メタデータ） (2023-02-07T22:09:20Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Online Optimization with Untrusted Predictions [7.895232155155041]
  本稿では, オンライン最適化の課題について検討し, 意思決定者は, ラウンドごと, 非競争的打撃コスト, ラウンド間切替コストの合計に対して, 一般的な計量空間内の点を選択する必要がある。 本稿では,新しいアルゴリズムであるAdaptive Online Switching (AOS)を提案し,予測が完全であれば$tildecalO(alphadelta)$が不正確であっても$tildecalO(alphadelta)$であることを示す。
  論文  参考訳（メタデータ） (2022-02-07T21:08:02Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-01T14:10:38Z)
• Facility Reallocation on the Line [9.40406631624105]
  我々は,$n$エージェントによって報告された位置に基づいて,施設を時間間隔で移動させる実数線上の多段施設再配置問題を考える。 再配置アルゴリズムの目的は、社会コストを最小化することであり、すなわち、施設と全てのエージェントのあらゆる段階の合計距離の合計と、施設を移動させるコストを最小化することである。
  論文  参考訳（メタデータ） (2021-03-23T23:48:45Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)
• Metrical Task Systems with Online Machine Learned Advice [0.0]
  機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。 我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
  論文  参考訳（メタデータ） (2020-12-17T04:56:51Z)
• Online Page Migration with ML Advice [26.929268665630342]
  提案手法は,エムページマイグレーション問題に対するオンラインアルゴリズムで,予測が不完全である可能性があり,その性能向上を図っている。 アルゴリズムが入力シーケンスの予測を与えられると、競合比が1ドルになることを示す。 我々の成果は、機械学習を使って古典的なアルゴリズムの性能を向上させる、最近の仕事の本体に追加される。
  論文  参考訳（メタデータ） (2020-06-09T03:15:34Z)

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

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