論文の概要: Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints

• arxiv url: http://arxiv.org/abs/2408.07831v2
• Date: Wed, 12 Mar 2025 22:56:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-14 15:48:58.649811
• Title: Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints
• Title（参考訳）: デッドライン制約付き時空間オンラインアロケーションのための学習強化競合アルゴリズム
• Authors: Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, Prashant Shenoy,
• Abstract要約: 我々は,サステナビリティとエネルギの新たな課題によって動機付けられた,新たなオンライン問題を紹介し,研究する。 オンラインプレーヤーは$mathsfSOADで、ポイント当たりのメートル法空間$(, d) にアロケートしてスケジューリングすることで、ワークロードを完了します。 各時点において、各時点における作業負荷のコストを表すサービスコスト関数が明らかにされ、プレーヤは、現在の作業のポイントへの割り当てを不当に決定しなければならない。
• 参考スコア（独自算出の注目度）: 11.029788598491077
• License:
• Abstract: We introduce and study spatiotemporal online allocation with deadline constraints ($\mathsf{SOAD}$), a new online problem motivated by emerging challenges in sustainability and energy. In $\mathsf{SOAD}$, an online player completes a workload by allocating and scheduling it on the points of a metric space $(X, d)$ while subject to a deadline $T$. At each time step, a service cost function is revealed that represents the cost of servicing the workload at each point, and the player must irrevocably decide the current allocation of work to points. Whenever the player moves this allocation, they incur a movement cost defined by the distance metric $d(\cdot, \ \cdot)$ that captures, e.g., an overhead cost. $\mathsf{SOAD}$ formalizes the open problem of combining general metrics and deadline constraints in the online algorithms literature, unifying problems such as metrical task systems and online search. We propose a competitive algorithm for $\mathsf{SOAD}$ along with a matching lower bound establishing its optimality. Our main algorithm, \textsc{ST-CLIP}, is a learning-augmented algorithm that takes advantage of predictions (e.g., forecasts of relevant costs) and achieves an optimal consistency-robustness trade-off. We evaluate our proposed algorithms in a simulated case study of carbon-aware spatiotemporal workload management, an application in sustainable computing that schedules a delay-tolerant batch compute job on a distributed network of data centers. In these experiments, we show that \textsc{ST-CLIP} substantially improves on heuristic baseline methods.
• Abstract（参考訳）: 本稿では,持続可能性とエネルギーの新たな課題に起因した新たなオンライン問題である期限制約付き時空間オンラインアロケーション(\mathsf{SOAD}$)を紹介し,研究する。 オンラインプレーヤーは、$\mathsf{SOAD}$で、納期$T$を条件として、計量空間$(X, d)$のポイントにアロケートしてスケジューリングすることで、ワークロードを完了する。 各タイムステップにおいて、各ポイントでの作業負荷を処理するコストを表すサービスコスト関数が明らかにされ、プレーヤは、現在の作業のポイントへの割り当てを不当に決定しなければならない。 プレイヤーがこのアロケーションを移動したときには、移動コストが$d(\cdot, \ \cdot)$で定義される。 $\mathsf{SOAD}$は、オンラインアルゴリズムの文献における一般的なメトリクスと期限制約を組み合わせたオープンな問題を公式化し、メトリックタスクシステムやオンライン検索のような問題を統一する。 我々は,$\mathsf{SOAD}$に対する競争的アルゴリズムと,その最適性を確立するための一致した下界を提案する。 我々の主アルゴリズムである‘textsc{ST-CLIP} は、予測(例えば、関連するコストの予測)を活かし、最適整合性-損益性トレードオフを実現する学習強化アルゴリズムである。 提案アルゴリズムは, 分散データセンターネットワーク上での遅延耐性バッチ計算ジョブをスケジューリングする, 持続可能なコンピューティングアプリケーションである, 炭素対応時空間負荷管理のシミュレーションケーススタディで評価する。 これらの実験では, ヒューリスティックベースライン法において, <textsc{ST-CLIP} が大幅に改善されることが示されている。

関連論文リスト

• Carbon- and Precedence-Aware Scheduling for Data Processing Clusters [10.676357280358886]
  データ処理のための炭素対応スケジューリングは、時間的変化のある炭素と優先順位の制約の両方の知識から恩恵を受けることを示す。 このスケジューラは, 炭素削減時間と仕事完了時間の間に優先順位を付与し, 両者のトレードオフを特徴付ける分析結果を与える。 100ノードクラスタ上のSparkプロトタイプは、$texttPCAPS$の適度な設定によって、クラスタ全体の効率に大きな影響を与えることなく、炭素フットプリントを最大32.9%削減できることを示している。
  論文  参考訳（メタデータ） (2025-02-13T19:06:10Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• Optimal Decentralized Smoothed Online Convex Optimization [9.449153668916098]
  マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。 そこで本研究では,マルチエージェントSOCOのための,真に分散化されたアルゴリズムACORDを提案する。 通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
  論文  参考訳（メタデータ） (2024-11-13T05:59:04Z)
• LACS: Learning-Augmented Algorithms for Carbon-Aware Resource Scaling with Uncertain Demand [1.423958951481749]
  本稿では,未知の作業時間(OCSU)を用いたオンラインCO_2-Awareリソーススケーリング問題について検討する。 我々は,論理的に堅牢な学習拡張アルゴリズムであるLACSを提案し,OCSUを解く。 LACSは、納期を意識した炭素に依存しない作業と比較して、炭素フットプリントの32%の削減を実現している。
  論文  参考訳（メタデータ） (2024-03-29T04:54:22Z)
• A Schedule of Duties in the Cloud Space Using a Modified Salp Swarm Algorithm [0.0]
  クラウド領域で最も重要なNPハード問題のひとつはスケジューリングです。 Salp Swarm Algorithm (SSA)と呼ばれる集団知能アルゴリズムの1つが拡張され、改良され、適用された。 その結果,本アルゴリズムは一般に他のアルゴリズムよりも高い性能を示した。
  論文  参考訳（メタデータ） (2023-09-18T02:48:41Z)
• Efficient Methods for Non-stationary Online Learning [61.63338724659592]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 また、さらに強化された測度、すなわち「インターバル・ダイナミック・リピート」を研究し、ラウンド当たりの射影数を$mathcalO(log2 T)$から$$$$に減らした。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Movement Penalized Bayesian Optimization with Application to Wind Energy Systems [84.7485307269572]
  文脈ベイズ最適化(CBO)は、与えられた側情報を逐次決定する強力なフレームワークである。 この設定では、学習者は各ラウンドでコンテキスト(天気条件など)を受け取り、アクション(タービンパラメータなど)を選択する必要がある。 標準的なアルゴリズムは、すべてのラウンドで意思決定を切り替えるコストを前提としませんが、多くの実用的なアプリケーションでは、このような変更に関連するコストが最小化されるべきです。
  論文  参考訳（メタデータ） (2022-10-14T20:19:32Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
  条件勾配法(CGM)は現代の機械学習で広く使われている。 ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。 本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-11-30T05:40:14Z)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)

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

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