論文の概要: Improved Bounds for Online Facility Location with Predictions
- arxiv url: http://arxiv.org/abs/2107.08277v4
- Date: Sun, 18 Aug 2024 07:30:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-21 06:51:56.066706
- Title: Improved Bounds for Online Facility Location with Predictions
- Title（参考訳）: 予測機能付きオンライン施設立地のバウンド改善
- Authors: Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, Nikolas Patris, Thanos Tolias,
- Abstract要約: 学習強化オンラインアルゴリズムの枠組みとして,オンライン施設配置を考える。
OFLでは、要求はメートル法空間で1つずつ到着し、到着時にオープンな施設に割り当てられなければならない。
最適施設の位置の予測に不完全な可能性を生かしたOFLのオンラインアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 14.973636284231047
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider Online Facility Location in the framework of learning-augmented online algorithms. 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 focus on uniform facility opening costs and 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 from sublogarithmic in the number of demands $n$ to constant as the so-called $\eta_1$ error, i.e., the sum of distances of the predicted locations to the optimal facility locations, decreases. E.g., our analysis implies that if for some $\varepsilon > 0$, $\eta_1 = \mathrm{OPT} / n^\varepsilon$, where $\mathrm{OPT}$ is the cost of the optimal solution, the competitive ratio becomes $O(1/\varepsilon)$. We complement our analysis with a matching lower bound establishing that the dependence of the algorithm's competitive ratio on the $\eta_1$ error is optimal, up to constant factors. Finally, we evaluate our algorithm on real world data and compare the performance of our learning-augmented approach against the performance of the best known algorithm for OFL without predictions.
- Abstract（参考訳）: 学習強化オンラインアルゴリズムの枠組みとして,オンライン施設配置を考える。
オンライン施設位置情報(OFL)では、要求はメートル法空間で1対1で到着し、到着時に(不可解に)将来の要求について何も知らないままオープンな施設に割り当てられなければならない。
本稿では, 施設のオープンコストの均一化に着目し, 最適施設の位置に関する不完全な予測を生かしたOFLのオンラインアルゴリズムを提案する。
競合比は、要求数$n$から定数に減少し、いわゆる$\eta_1$エラー、すなわち予測位置から最適な施設位置までの距離の和が減少することを示す。
例えば、ある$\varepsilon > 0$, $\eta_1 = \mathrm{OPT} / n^\varepsilon$に対して、$\mathrm{OPT}$が最適解のコストであれば、競合比は$O(1/\varepsilon)$となる。
我々は、アルゴリズムの競合比の$\eta_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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。