論文の概要: Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling

• arxiv url: http://arxiv.org/abs/2606.13133v1
• Date: Thu, 11 Jun 2026 09:55:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-12 15:55:27.71443
• Title: Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling
• Title（参考訳）: 非関連マシーンのスケジューリングのための学習強化近似
• Authors: Kaito Baba, Evripidis Bampis, Giorgos Mitropoulos,
• Abstract要約: 我々は,無関係マシン上でのmespan最小化問題に対する学習強化アルゴリズムを開発した。 重労働割当の予測を用いて、エラーが増加するにつれて最悪の2-近似に滑らかに低下する正確な予測に対して、ailon-time $(vareps)$-approximationを達成する。
• 参考スコア（独自算出の注目度）: 1.6185544531149159
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, Antoniadis et al. (ICLR 2025) proposed a framework for incorporating predictions to approximate NP-hard selection problems. Despite its simplicity, this approach tightly matches theoretical lower bounds, making its generalization highly compelling. We address an open question raised in the work of Antoniadis et al., concerning the extension of this approach to other important problems outside the class of selection problems, such as scheduling. We develop a learning-augmented algorithm for the makespan minimization problem on unrelated machines, denoted by $R\|C_{\max}$. By using predictions of heavy job assignments, we achieve a polynomial-time $(1+\varepsilon)$-approximation for accurate predictions that smoothly degrades to a worst-case 2-approximation as the error increases. We conclude our work with an empirical analysis of our method.
• Abstract（参考訳）: 最近、Antoniadis et al (ICLR 2025) はNP-hard選択問題を近似するために予測を組み込むフレームワークを提案した。 その単純さにもかかわらず、このアプローチは理論上の下界と密接に一致し、一般化は非常に魅力的である。 我々は、Antoniadis et al の著作で提起されたオープンな疑問に対処し、スケジューリングのような選択問題以外の重要な問題へのこのアプローチの拡張について論じる。 R\|C_{\max}$で表される無関係マシン上でのmespan最小化問題に対する学習強化アルゴリズムを開発した。 重労働割り当ての予測を用いて、誤差が増加するにつれて最悪の2-近似に滑らかに低下する正確な予測に対して、多項式時間$(1+\varepsilon)$-approximationを達成する。 我々はこの方法の実証的な分析で研究を締めくくった。

関連論文リスト

• Makespan Minimization in Split Learning: From Theory to Practice [19.128619079473413]
  分割学習は、異種IoTデバイスを用いた分散機械学習のソリューションである。 支援者によるクライアント・ヘルパーの割り当てとタスクのスケジュールを共同で設計することで、トレーニング時間を最小化する方法を示す。
  論文  参考訳（メタデータ） (2026-02-06T13:22:44Z)
• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
  オンラインスパース線形回帰(OSLR)では,予測のために1インスタンスあたり$d$あたり$k$しかアクセスできない。 提案手法では, 過去の後悔点を大幅に改善する拡張時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-10-31T05:02:33Z)
• Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
  従来のアルゴリズムの近似保証よりも高い精度で予測を行う。 我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。 この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
  論文  参考訳（メタデータ） (2024-11-25T17:31:34Z)
• Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms [0.7499722271664147]
  我々は最近の意思決定中心の予測、すなわち予測モデルの構築への取り組みに貢献する。 NP のメンバシップを含む問題の計算結果を示す。 次に,経験的トラクタビリティを実現するために,様々な計算手法を定式化する。
  論文  参考訳（メタデータ） (2023-12-29T15:05:00Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Can Q-Learning be Improved with Advice? [27.24260290748049]
  本稿では,マルコフ決定過程(MDP)のオンライン学習において,後悔に対する最悪の下限を回避できるかどうかを論じる。 最適$Q$-値関数の予測が蒸留と呼ばれる合理的に弱い条件を満たす場合、状態-作用対の集合を、その予測が極端に不正確な状態-作用対の集合に置き換えることで、後悔境界を改善することができることを示す。 私たちの研究は、キャッシュやスケジューリングといった単純なオンライン問題に重点を置いていた予測を伴うアルゴリズムに関する最近の研究を、強化学習のより複雑で一般的な問題へと拡張しています。
  論文  参考訳（メタデータ） (2021-10-25T15:44:20Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)

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

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