論文の概要: Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem

• arxiv url: http://arxiv.org/abs/2105.12525v1
• Date: Wed, 26 May 2021 13:00:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-29 11:42:08.945521
• Title: Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem
• Title（参考訳）: 動的グラフ色問題に対するランダム化探索ヒューリスティックの時間複雑度解析
• Authors: Jakob Bossek, Frank Neumann, Pan Peng, Dirk Sudholt
• Abstract要約: エッジを現在のグラフに追加する動的設定について検討する。 次に、ランダム化された検索の予測時間を分析し、高品質な解を再計算する。
• 参考スコア（独自算出の注目度）: 15.45783225341009
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical vertex coloring problem on graphs and investigate the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized search heuristics to recompute high quality solutions. The (1+1)~Evolutionary Algorithm and RLS operate in a setting where the number of colors is bounded and we are minimizing the number of conflicts. Iterated local search algorithms use an unbounded color palette and aim to use the smallest colors and, consequently, the smallest number of colors. We identify classes of bipartite graphs where reoptimization is as hard as or even harder than optimization from scratch, i.e., starting with a random initialization. Even adding a single edge can lead to hard symmetry problems. However, graph classes that are hard for one algorithm turn out to be easy for others. In most cases our bounds show that reoptimization is faster than optimizing from scratch. We further show that tailoring mutation operators to parts of the graph where changes have occurred can significantly reduce the expected reoptimization time. In most settings the expected reoptimization time for such tailored algorithms is linear in the number of added edges. However, tailored algorithms cannot prevent exponential times in settings where the original algorithm is inefficient.
• Abstract（参考訳）: 動的問題に対するランダム化探索ヒューリスティックの理論的理解に寄与する。 グラフ上の古典的な頂点彩色問題を検討し、エッジを現在のグラフに追加する動的設定について検討する。 次に、ランダム化探索ヒューリスティックの期待時間を分析し、高品質な解を再計算する。 1+1)~Evolutionary Algorithm と RLS は,色数に制限のある環境で動作し,コンフリクトの数を最小限に抑えている。 反復局所探索アルゴリズムは、無境界色パレットを使用し、最小色を目的とし、その結果、最小色を目的とする。 再最適化がスクラッチから最適化するよりも難しい、すなわちランダムな初期化から始まる二部グラフのクラスを同定する。 一つのエッジを追加することさえも、ハード対称性の問題につながる。 しかし、あるアルゴリズムでは難しいグラフクラスは、他のアルゴリズムでは簡単であることが判明した。 ほとんどの場合、我々の限界は、再最適化はゼロから最適化するよりも速いことを示している。 さらに,変化が発生したグラフの一部に変異演算子を合わせることで,期待した再最適化時間を著しく短縮できることを示した。 ほとんどの設定において、このような調整されたアルゴリズムの期待再最適化時間は、追加されたエッジの数で線形である。 しかし、調整アルゴリズムは、元のアルゴリズムが非効率な設定において指数時間を防ぐことはできない。

関連論文リスト

• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs [3.707290781951909]
  観測データから因果効果を推定することは経験科学の基本的な課題である。 本論文は, 観測媒介者を用いて, 保存されていない共同設立者の存在下においても, 因果関係を識別できる古典的な手法である, 正面調整に焦点を当てたものである。
  論文  参考訳（メタデータ） (2022-11-29T18:44:03Z)
• Withdrawn: A Measurement-based Algorithm for Graph Colouring [0.5482532589225553]
  この文書の以前のバージョンでは、記述されたアルゴリズムの一部のランタイムを誤って解釈した。 グラフが存在すれば$d$カラーの適切な色付けを見つけるための新しいアルゴリズム的アプローチを提案する。
  論文  参考訳（メタデータ） (2021-11-29T09:17:34Z)
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization [111.24899593052851]
  条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。 ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。 1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
  論文  参考訳（メタデータ） (2021-09-18T07:08:11Z)
• A Grover search-based algorithm for the list coloring problem [1.332560004325655]
  本稿では,Grover 探索に基づく量子アルゴリズムを提案する。 我々のアルゴリズムは、制限された特定のケースでは古典的な場合に比べて複雑性が低いが、自然に考慮されたリストやグラフが任意である場合の徹底的な探索を改善する。
  論文  参考訳（メタデータ） (2021-08-20T08:41:22Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time [12.43303621344215]
  専門知識のないグラフ上での最適化問題を解くための新しいフレームワークを開発する。 本手法は,グラフのラベル付きトレーニングセット上で強化学習を用いてグラフニューラルネットワークを訓練する。 最適性ギャップが 1 に近い 2 つのNP-ハード問題に対して,本手法がよく一般化可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-06T01:35:45Z)
• More Effective Randomized Search Heuristics for Graph Coloring Through Dynamic Optimization [15.45783225341009]
  進化的アルゴリズムは、動的最適化を用いて、二部グラフのグラフ彩色問題をより効率的に解くことができることを示す。 3つの島を用いた島式は、すべての$m$-edge二部グラフ上で$Theta(m)$の最適時間で成功し、子孫より優れている。
  論文  参考訳（メタデータ） (2020-05-28T07:55:12Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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