論文の概要: Scheduling with Speed Predictions
- arxiv url: http://arxiv.org/abs/2205.01247v1
- Date: Mon, 2 May 2022 23:39:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-04 14:51:24.828592
- Title: Scheduling with Speed Predictions
- Title（参考訳）: 速度予測によるスケジューリング
- Authors: Eric Balkanski, Tingting Ou, Clifford Stein, Hao-Ting Wei
- Abstract要約: 本稿では,ジョブの処理時間ではなく,マシンの速度が不明な速度ロスのスケジューリング問題について検討する。
我々の主な結果は、$mineta2 (1+epsilon)2 (1+epsilon)(2+2/alpha)$近似を達成するアルゴリズムである。
予測が正確であれば、この近似は以前最もよく知られた2-1/m$の近似よりも改善される。
- 参考スコア（独自算出の注目度）: 10.217102227210669
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Algorithms with predictions is a recent framework that has been used to
overcome pessimistic worst-case bounds in incomplete information settings. In
the context of scheduling, very recent work has leveraged machine-learned
predictions to design algorithms that achieve improved approximation ratios in
settings where the processing times of the jobs are initially unknown. In this
paper, we study the speed-robust scheduling problem where the speeds of the
machines, instead of the processing times of the jobs, are unknown and augment
this problem with predictions.
Our main result is an algorithm that achieves a
$\min\{\eta^2(1+\epsilon)^2(1+\alpha), (1+\epsilon)(2 + 2/\alpha)\}$
approximation, for any constants $\alpha, \epsilon \in (0,1)$, where $\eta \geq
1$ is the prediction error. When the predictions are accurate, this
approximation improves over the previously best known approximation of $2-1/m$
for speed-robust scheduling, where $m$ is the number of machines, while
simultaneously maintaining a worst-case approximation of $(1+\epsilon)(2 +
2/\alpha)$ even when the predictions are wrong. In addition, we obtain improved
approximations for the special cases of equal and infinitesimal job sizes, and
we complement our algorithmic results with lower bounds. Finally, we
empirically evaluate our algorithm against existing algorithms for speed-robust
scheduling.
- Abstract（参考訳）: 予測を伴うアルゴリズムは、不完全な情報設定における悲観的な最悪のケース境界を克服するために最近使われたフレームワークである。
スケジューリングの文脈では、最近の研究は機械学習による予測を利用して、ジョブの処理時間が最初に不明な設定で近似比を改善するアルゴリズムを設計している。
本稿では,ジョブの処理時間ではなく,マシンの速度が未知である高速化スケジューリング問題について検討し,この問題を予測を用いて拡張する。
我々の主な結果は、任意の定数に対して$\alpha, \epsilon \in (0,1)$に対して$\min\{\eta^2(1+\epsilon)^2(1+\alpha), (1+\epsilon)(2+2/\alpha)\}$の近似を達成するアルゴリズムである。
予測が正確であれば、この近似は、予測が間違っても最悪の場合でも$(1+\epsilon)(2 + 2/\alpha)$の近似を維持しながら、マシン数を$m$とする速度ロバストスケジューリングに対して、これまで最もよく知られていた2-1/m$の近似よりも改善される。
さらに, 等小および無限小のジョブサイズを持つ特殊な場合に対する近似精度が向上し, アルゴリズムの結果を下限で補完する。
最後に,本アルゴリズムを既存の速度ロバストスケジューリングアルゴリズムに対して実証的に評価する。
関連論文リスト
- Binary Search with Distributional Predictions [26.193119064206304]
本研究では,予測自体が分布である分布予測を用いたアルゴリズムについて検討する。
従来の予測に基づくアルゴリズムを1つの予測で使用すると、予測が不十分な単純な分布が存在することを示す。
これはまた、二分探索木を最適に計算する古典的な問題に対する最初の分散ロバストアルゴリズムをもたらす。
論文 参考訳（メタデータ） (2024-11-25T01:15:31Z) - Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。
この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。
我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
論文 参考訳（メタデータ） (2024-05-06T17:38:20Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
本研究では,不確実性下でのソートとハイパーグラフ配向のための学習強化アルゴリズムについて検討する。
我々のアルゴリズムは、予測なしで最良となる最悪の保証を維持しつつ、精度の高い予測性能を保証する。
論文 参考訳（メタデータ） (2023-05-16T07:52:08Z) - Mixing predictions for online metric algorithms [34.849039387367455]
我々は予測を組み合わせるアルゴリズムを設計し、このような動的組み合わせと競合する。
我々のアルゴリズムは、バンディットのような方法で予測者にアクセスするように適応することができ、一度に1つの予測者しかクエリできない。
我々の下界の1つが予想外の意味を持つのは、$k$-server問題に対する定式化のカバーに関する新しい構造的洞察である。
論文 参考訳（メタデータ） (2023-04-04T13:18:00Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Learning-Augmented Maximum Flow [3.0712335337791288]
本稿では,予測を用いて最大流れ計算を高速化するフレームワークを提案する。
我々は,$m$のエッジフローネットワークと予測フローが与えられた場合,最大フローを$O(meta)$時間で計算するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-26T14:02:41Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。