論文の概要: 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のオンラインアルゴリズムを提案する。
その結果, 予測位置と最適施設位置の合計距離の誤差がゼロに減少するため, 要求数を一定にすることで, 競争比が亜対数から一定までスムーズに減少することが判明した。
我々は、アルゴリズムの競合比の誤差に対する依存性が一定因子まで最適であることを示す、一致する下限値で解析を補完する。
最後に,本アルゴリズムを実世界データ上で評価し,学習拡張手法と現在の最良のオンラインアルゴリズムを比較した。
関連論文リスト
- Handling Delayed Feedback in Distributed Online Optimization : A
Projection-Free Approach [1.9797215742507548]
大量のデータが局所的に連続的に生成されるように、エッジでの学習はますます重要になっている。
本稿では,B が遅延の和である O(sqrtB) の後悔境界を達成するために慎重に設計された,集中的および分散的設定のための2つのプロジェクションフリーアルゴリズムを提案する。
本研究では,実世界の問題において,既存の問題と比較することにより,アルゴリズムの性能を実験的に検証する。
論文 参考訳(メタデータ) (2024-02-03T10:43:22Z) - SpatialRank: Urban Event Ranking with NDCG Optimization on
Spatiotemporal Data [55.609946936979036]
本研究ではSpatialRankという新しい空間イベントランキング手法を提案する。
本研究では,SpatialRankが犯罪や交通事故の最も危険性の高い場所を効果的に特定できることを示す。
論文 参考訳(メタデータ) (2023-09-30T06:20:21Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。
FedBiOの複雑性は$O(epsilon-1.5)$である。
本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
論文 参考訳(メタデータ) (2022-05-03T16:40:22Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2022-02-09T19:22:34Z) - Learning-Augmented Dynamic Power Management with Multiple States via New
Ski Rental Bounds [38.80523710193321]
複数の省電力状態を持つシステムにおける電力消費を最小化するオンライン問題について検討する。
アルゴリズムは、異なるエネルギー消費と覚醒コストの省電力状態を選択する必要がある。
アイドル期間の予測長に基づいて(潜在的に不正確な)決定を行う学習強化オンラインアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-10-25T17:14:20Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳(メタデータ) (2021-03-02T11:04:33Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳(メタデータ) (2020-10-22T04:51:01Z) - Online Learning of Facility Locations [21.451413948517228]
施設立地問題のオンライン学習版に関する厳密な理論的調査を行う。
私たちの定式化では、一連のサイトとオンラインのユーザリクエストが与えられます。
各試行において、学習者は、サイトのサブセットを選択し、選択したサイトのコストと、選択したサブセット内の最も近いサイトへのユーザの接続の価格である追加コストとを発生させる。
論文 参考訳(メタデータ) (2020-07-06T15:04:53Z) - FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity
to Non-IID Data [59.50904660420082]
フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。
クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
論文 参考訳(メタデータ) (2020-05-22T23:07:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。