論文の概要: A Reduction-Driven Local Search for the Generalized Independent Set Problem

• arxiv url: http://arxiv.org/abs/2505.21052v1
• Date: Tue, 27 May 2025 11:39:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 22:24:19.364679
• Title: A Reduction-Driven Local Search for the Generalized Independent Set Problem
• Title（参考訳）: 一般化独立集合問題に対する還元駆動型局所探索
• Authors: Yiping Liu, Yi Zhou, Zhenxiang Xu, Mingyu Xiao, Jin-Kao Hao,
• Abstract要約: 本稿では,これらのリダクションルールを前処理,初期解生成,局所探索コンポーネントに組み込むリダクション駆動ローカルサーチ(RLS)アルゴリズムを提案する。 RLSは、異なるアプリケーションシナリオから生じる278のグラフで実証的に評価される。 他の既知の解法に比べてはるかに優れた解を実現し、2億6000万を超えるグラフに対する解を効果的に提供する。
• 参考スコア（独自算出の注目度）: 29.094247069747073
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Generalized Independent Set (GIS) problem extends the classical maximum independent set problem by incorporating profits for vertices and penalties for edges. This generalized problem has been identified in diverse applications in fields such as forest harvest planning, competitive facility location, social network analysis, and even machine learning. However, solving the GIS problem in large-scale, real-world networks remains computationally challenging. In this paper, we explore data reduction techniques to address this challenge. We first propose 14 reduction rules that can reduce the input graph with rigorous optimality guarantees. We then present a reduction-driven local search (RLS) algorithm that integrates these reduction rules into the pre-processing, the initial solution generation, and the local search components in a computationally efficient way. The RLS is empirically evaluated on 278 graphs arising from different application scenarios. The results indicates that the RLS is highly competitive -- For most graphs, it achieves significantly superior solutions compared to other known solvers, and it effectively provides solutions for graphs exceeding 260 million edges, a task at which every other known method fails. Analysis also reveals that the data reduction plays a key role in achieving such a competitive performance.
• Abstract（参考訳）: 一般化独立集合問題(GIS)は、頂点に対する利益とエッジに対する罰則を組み込むことで、古典的な最大独立集合問題を拡張する。 この一般化された問題は、森林収穫計画、競争施設の立地、ソーシャルネットワークの分析、さらには機械学習といった分野の様々な応用において特定されている。 しかし、大規模で現実的なネットワークにおけるGIS問題の解決は、依然として計算的に困難である。 本稿では,この課題に対処するためのデータ削減手法について検討する。 まず、厳密な最適性保証で入力グラフを削減できる14の削減ルールを提案する。 そこで我々は,これらのリダクションルールを前処理,初期解生成,局所探索コンポーネントに組み込んだリダクション駆動型局所探索(RLS)アルゴリズムを提案する。 RLSは、異なるアプリケーションシナリオから生じる278のグラフで実証的に評価される。 その結果、RSSは競争力が高いことが示され、ほとんどのグラフでは、他の既知の解法よりもはるかに優れた解を達成し、2億6000万のエッジを超えるグラフの解を効果的に提供します。 分析により、このような競争力のあるパフォーマンスを達成する上で、データ削減が重要な役割を担っていることが明らかになった。

関連論文リスト

• MA-GTS: A Multi-Agent Framework for Solving Complex Graph Problems in Real-World Applications [22.705728671135834]
  グラフ理論上の問題は、ロジスティクス、通信ネットワーク、トラフィック最適化といった現実世界のアプリケーションで発生する。 大きな言語モデル(LLM)は潜在的な解決策を提供するが、精度や入力長の制約を含む課題に直面している。 エージェント協調による複雑な問題を分解するマルチエージェントフレームワークMA-GTSを提案する。
  論文  参考訳（メタデータ） (2025-02-25T08:34:00Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
  論文  参考訳（メタデータ） (2023-10-24T06:22:20Z)
• ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set [48.57120672468062]
  本稿では、2つの革新的な手法を取り入れたMIS問題に対する効率的なアルゴリズムを提案する。 提案アルゴリズムは、解の質、計算効率、安定性の点で最先端のアルゴリズムより優れている。
  論文  参考訳（メタデータ） (2022-08-16T14:39:38Z)
• Support Vector Machines with the Hard-Margin Loss: Optimal Training via Combinatorial Benders' Cuts [8.281391209717105]
  我々は、グローバルな最適性のために、ハードマージンのSVMモデルをトレーニングする方法を示す。 本稿では,この問題を解くための反復サンプリングと部分分解アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-15T18:21:51Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• Graph Neural Network-based Resource Allocation Strategies for Multi-Object Spectroscopy [6.98188921994299]
  トレーニング可能な資源割り当て戦略のための二部グラフニューラルネットワークアーキテクチャを提案する。 値と制約の項目は、可能なアロケーションに対応するエッジによって接続される2つのグラフノードのセットを形成する。 本研究では,高多重化Subaru Prime Focus Spectrographの天体目標選択戦略を最適化するために,本手法を適用した。
  論文  参考訳（メタデータ） (2021-09-27T21:54:06Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Learning What to Defer for Maximum Independent Sets [84.00112106334655]
  本稿では,各段階における解の要素的決定を学習することにより,エージェントが適応的に段階数を縮小あるいは拡張する,新たなDRL方式を提案する。 提案手法を最大独立集合(MIS)問題に適用し、現状のDRL方式よりも大幅に改善したことを示す。
  論文  参考訳（メタデータ） (2020-06-17T02:19:31Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。 異種車両ルーティング問題に対するMineReduceの適用について述べる。
  論文  参考訳（メタデータ） (2020-05-15T08:49:50Z)

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

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