論文の概要: Dominating Set Reconfiguration with Answer Set Programming
- arxiv url: http://arxiv.org/abs/2408.07510v1
- Date: Wed, 14 Aug 2024 12:38:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-15 13:24:15.171712
- Title: Dominating Set Reconfiguration with Answer Set Programming
- Title（参考訳）: 解集合プログラミングによる集合再構成の優位性
- Authors: Masato Kato, Torsten Schaub, Takehide Soh, Naoyuki Tamura, Mutsunori Banbara,
- Abstract要約: 我々は Answer Set Programming (ASP) に基づく支配的集合再構成問題の解法を開発する。
このアプローチは、高レベルのASPエンコーディングに依存しており、基礎と解決のタスクは、ASPベースの解決器に委譲されます。
- 参考スコア（独自算出の注目度）: 0.5242869847419832
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The dominating set reconfiguration problem is defined as determining, for a given dominating set problem and two among its feasible solutions, whether one is reachable from the other via a sequence of feasible solutions subject to a certain adjacency relation. This problem is PSPACE-complete in general. The concept of the dominating set is known to be quite useful for analyzing wireless networks, social networks, and sensor networks. We develop an approach to solve the dominating set reconfiguration problem based on Answer Set Programming (ASP). Our declarative approach relies on a high-level ASP encoding, and both the grounding and solving tasks are delegated to an ASP-based combinatorial reconfiguration solver. To evaluate the effectiveness of our approach, we conduct experiments on a newly created benchmark set.
- Abstract（参考訳）: 支配集合再構成問題は、与えられた支配集合問題と、その実現可能な解のうち2に対して、ある隣接関係に従属する実現可能な解の列を介して他方から到達可能であるか否かを決定するものとして定義される。
この問題は一般にPSPACE完全である。
支配集合の概念は、無線ネットワーク、ソーシャルネットワーク、センサーネットワークを分析するのに非常に有用であることが知られている。
本稿では, Answer Set Programming (ASP) に基づく支配的集合再構成問題の解法を開発する。
我々の宣言的アプローチは、高レベルのASPエンコーディングに依存しており、基礎と解決のタスクは、ASPベースの組合せ再構成ソルバに委譲されます。
提案手法の有効性を評価するため,新たに作成したベンチマークセットを用いて実験を行った。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - Design Optimization of NOMA Aided Multi-STAR-RIS for Indoor Environments: A Convex Approximation Imitated Reinforcement Learning Approach [51.63921041249406]
非直交多重アクセス(Noma)により、複数のユーザが同じ周波数帯域を共有でき、同時に再構成可能なインテリジェントサーフェス(STAR-RIS)を送信および反射することができる。
STAR-RISを屋内に展開することは、干渉緩和、電力消費、リアルタイム設定における課題を提示する。
複数のアクセスポイント(AP)、STAR-RIS、NOMAを利用した新しいネットワークアーキテクチャが屋内通信のために提案されている。
論文 参考訳（メタデータ） (2024-06-19T07:17:04Z) - Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming [3.759879849096294]
ASP(Answer Set Programming)における最適化問題に対するLNPS(Large Neighborhood Prioritized Search)を提案する。
LNPSはメタヒューリスティックであり、初期解から始まり、次に現在の解の探索を交互に破壊し優先順位付けすることでより良い解を見つけようとする。
本稿では,ASP に基づく LNPS の実装について述べる。その結果,LNPS が ASP の最適化性能を大幅に向上させることができることを示す。
論文 参考訳（メタデータ） (2024-05-18T14:37:43Z) - Bounded Combinatorial Reconfiguration with Answer Set Programming [6.40603461305679]
我々は、Answer Set Programming(ASP)に基づく再構成問題の解法として、境界再構成と呼ばれるアプローチを開発する。
コンフィグレーションに関する最新の国際コンペ(CoRe Challenge 2022)におけるコンフィグレーショントラックのすべての指標をカバーしたコンフィグレーションソルバ(CoRe Challenge 2022)
本稿では、有界再構成の設計と実装について述べるとともに、最も研究されている再構成問題の一つである独立セット再構成問題のASPエンコーディングについて述べる。
論文 参考訳（メタデータ） (2023-07-20T08:30:56Z) - Conjunctive Query Based Constraint Solving For Feature Model
Configuration [79.14348940034351]
本稿では、制約満足度問題を解決するために共役クエリーを適用する方法を示す。
このアプローチは、構成タスクを解決するために、広範囲のデータベース技術の応用を可能にする。
論文 参考訳（メタデータ） (2023-04-26T10:08:07Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
絡み合いルーティングは、2つの任意のノード間のリモート絡み合い接続を確立する。
量子ネットワークにおける複数のソース・デスティネーション(SD)ペアの忠実性を保証するために、精製可能な絡み合わせルーティング設計を提案する。
論文 参考訳（メタデータ） (2021-11-15T14:07:22Z) - Neural Learning of One-of-Many Solutions for Combinatorial Problems in
Structured Output Spaces [20.101005623256626]
複数のソリューションの存在に消極的であることは、トレーニング能力を著しく損なう可能性がある、と私たちは主張する。
本稿では、既存の予測ネットワークをRL問題に適用し、解乗法を扱う汎用学習フレームワークを提案する。
論文 参考訳（メタデータ） (2020-08-27T08:37:01Z) - SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep
Reinforcement Learning [102.78958681141577]
SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。
SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
論文 参考訳（メタデータ） (2020-07-09T17:08:44Z) - Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。
我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。
その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
論文 参考訳（メタデータ） (2020-06-22T03:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。