論文の概要: 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$の近似よりも改善される。
さらに, 等小および無限小のジョブサイズを持つ特殊な場合に対する近似精度が向上し, アルゴリズムの結果を下限で補完する。
最後に,本アルゴリズムを既存の速度ロバストスケジューリングアルゴリズムに対して実証的に評価する。
関連論文リスト
- Constrained Online Two-stage Stochastic Optimization: Algorithm with
(and without) Predictions [19.537289123577022]
有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。
対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
論文 参考訳(メタデータ) (2024-01-02T07:46:33Z) - Learning the Positions in CountSketch [56.22648269865784]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-06-11T07:28: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) - Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。
そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。
我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
論文 参考訳(メタデータ) (2023-01-23T19:13:25Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。