論文の概要: Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations

• arxiv url: http://arxiv.org/abs/2008.05180v2
• Date: Thu, 13 Aug 2020 05:45:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-31 05:58:01.652629
• Title: Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations
• Title（参考訳）: 拡大変換を用いた最大重み独立集合問題に対するデータ削減の促進
• Authors: Alexander Gellner, Sebastian Lamm, Christian Schulz, Darren Strash, Bogd\'an Zav\'alnij
• Abstract要約: 最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
• 参考スコア（独自算出の注目度）: 59.84561168501493
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a vertex-weighted graph, the maximum weight independent set problem asks for a pair-wise non-adjacent set of vertices such that the sum of their weights is maximum. The branch-and-reduce paradigm is the de facto standard approach to solve the problem to optimality in practice. In this paradigm, data reduction rules are applied to decrease the problem size. These data reduction rules ensure that given an optimum solution on the new (smaller) input, one can quickly construct an optimum solution on the original input. We introduce new generalized data reduction and transformation rules for the problem. A key feature of our work is that some transformation rules can increase the size of the input. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later throughout the algorithm. In experiments, our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than heuristic solvers DynWVC and HILS on many instances. While the increasing transformations are only efficient enough for preprocessing at this time, we see this as a critical initial step towards a new branch-and-transform paradigm.
• Abstract（参考訳）: 頂点重み付きグラフが与えられたとき、最大重み独立集合問題は、その重みの和が最大となるような頂点のペアワイズ非隣接集合を求める。 branch-and-reduceパラダイムは、事実上の最適性問題を解くためのデファクトスタンダードアプローチである。 このパラダイムでは、データ削減ルールを適用し、問題のサイズを小さくする。 これらのデータ還元規則は、新しい(より小さい)入力に対する最適解が与えられた場合、元の入力に対する最適解を迅速に構築できる。 この問題に対して,新たな一般化データ削減および変換ルールを導入する。 私たちの仕事の重要な特徴は、いくつかの変換ルールが入力のサイズを増加させることです。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、アルゴリズムを通してさらに小さな既約グラフが得られるように縮小空間を開放する。 実験では, 1つのインスタンスを除くすべての非既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に処理し, ヒューリスティック解法であるDynWVCやHILSよりも高品質な解を求める。 トランスフォーメーションの増加は、現時点では事前処理に十分な効率しかありませんが、これは新しいブランチ・アンド・トランスフォーメーションパラダイムへの重要な最初のステップであると考えています。

関連論文リスト

• Fast Screening Rules for Optimal Design via Quadratic Lasso Reformulation [0.135975510645475]
  本研究は, 安全スクリーニングのルールを導出し, インテリジェンスサンプルを廃棄する。 新しいテストは、特に高次元のパラメータ空間に関わる問題に対して、より高速に計算できる。 本稿では,ラッソ法の正規化経路を計算するホモトピーアルゴリズムを,正方形 $ell_$-penalty に対して再パラメータ化する方法を示す。
  論文  参考訳（メタデータ） (2023-10-13T08:10:46Z)
• Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems [7.5573375809946395]
  定常的非平滑項の両方にフォーカスできるNCSCミニマックス問題を解くための最初の試みを行う。 提案アルゴリズムは,ミニマックス問題の新たな再構成に基づいて設計されている。
  論文  参考訳（メタデータ） (2023-04-05T13:54:43Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Smooth over-parameterized solvers for non-smooth structured optimization [3.756550107432323]
  非滑らか性 (non-smoothness) は、空間性、群空間性、低ランクエッジ、鋭いエッジなどの解の構造的制約を符号化する。 我々は、基礎となる非滑らかな最適化問題の非重み付きだが滑らかな過度パラメータ化を運用する。 我々の主な貢献は変数の一部を明示的に最小化することで新しい定式化を定義する変数射影(VarPro)を適用することです。
  論文  参考訳（メタデータ） (2022-05-03T09:23:07Z)
• A framework for bilevel optimization that enables stochastic and global variance reduction algorithms [17.12280360174073]
  双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。 本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。 我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
  論文  参考訳（メタデータ） (2022-01-31T18:17:25Z)
• Mean Field Approximation for solving QUBO problems [0.0]
  平均場焼鈍における統計物理学的アプローチと量子力学的アプローチが同じ結果をもたらすことを示す。 提案手法は連続変数を持つ単純な勾配に基づく最小化からなるため,シミュレーションが容易である。
  論文  参考訳（メタデータ） (2021-06-06T20:35:28Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  変換の値に関する事前情報がない点集合を整列するロバストな手法を提案する。 我々のアルゴリズムは変換の正規化を必要とせず、変換の値に関する事前情報がない状況に対処できる。 実験により,提案手法が最先端のアルゴリズムよりも高いロバスト性を示した。
  論文  参考訳（メタデータ） (2020-07-05T15:23:33Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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