論文の概要: Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems

• arxiv url: http://arxiv.org/abs/2609.20091v1
• Date: Thu, 17 Sep 2026 11:54:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:54.250264
• Title: Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems
• Title（参考訳）: 最小スパン反バンド幅の解法と周期的反バンド幅ラベリング問題
• Abstract要約: 反バンド幅問題とサイクリック反バンド幅問題はNPハードグラフラベル問題である。 我々は、それらを解決するための統一されたBoolean Satisfiability (SAT) ベースのフレームワークを開発する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The Antibandwidth and Cyclic Antibandwidth problems are NP-hard graph labeling problems that aim to maximize the minimum (cyclic) distance between labels assigned to adjacent vertices. Extensive research on these problems has resulted in a variety of mathematical formulations and computational approaches. However, their minimum span perspective, in which a prescribed minimum (cyclic) distance is fixed and the objective is to minimize the label span, has received comparatively little attention. In this paper, we consider this complementary perspective by introducing the Minimum Span Antibandwidth/Cyclic Antibandwidth Labeling (MSABL/MSCABL) problems and developing a unified Boolean Satisfiability (SAT)-based framework for solving them. The SAT-based framework formulates MSABL/MSCABL as a sequence of decision problems and exploits their monotonicity to accelerate the search process. We also consider two SAT solving strategies, parallel and incremental SAT solving: the former examines multiple candidate spans concurrently, while the latter reuses a single SAT instance while progressively restricting the label domain. The proposed approaches are evaluated on benchmark instances from the Harwell-Boeing Sparse Matrix Collection and compared with CPLEXCP, CPLEXMIP, and Gurobi. The results show that SAT-based approaches are highly competitive in solution quality, with the parallel approach performing best overall for MSCABL and the incremental approach for MSABL. With the no-hole constraint, they remain competitive with CPLEXCP and significantly outperform CPLEXMIP and Gurobi, particularly for MSCABL. These results demonstrate the effectiveness of SAT solving as an exact approach for MSABL and MSCABL.
• Abstract（参考訳）: 反バンド幅問題とサイクリック反バンド幅問題(サイクリック反バンド幅問題)は、隣接する頂点に割り当てられたラベル間の最小(循環)距離を最大化することを目的としたNPハードグラフラベル問題である。 これらの問題に関する広範な研究は、様々な数学的定式化と計算手法をもたらした。 しかし、その最小スパン視点は、所定の最小(巡回)距離が固定され、ラベルスパンを最小化することを目的としており、比較的ほとんど注目されていない。 本稿では,MSABL/MSCABL(Minimum Span Antibandwidth/Cyclic Antibandwidth Labeling)問題を導入し,それらを解決するための統一されたBoolean Satisfiability(SAT)ベースのフレームワークを開発することにより,この相補的視点を考察する。 SATベースのフレームワークは、MSABL/MSCABLを決定問題の列として定式化し、そのモノトニック性を利用して探索プロセスを高速化する。 前者は複数の候補を同時に検討し、後者はラベルドメインを漸進的に制限しながら単一のSATインスタンスを再利用する。 提案手法は,Harwell-Boeing Sparse Matrix Collectionのベンチマークインスタンスを用いて評価し,CPLEXCP,CPLEXMIP,Gurobiと比較した。 その結果、SATベースのアプローチはソリューションの品質において非常に競争力があり、MSCABLには並列アプローチが、MSABLにはインクリメンタルアプローチが最適であることがわかった。 ホールのない制約により、彼らはCPLEXCPと競合し続け、特にMSCABLではCPLEXMIPとGurobiを著しく上回っている。 これらの結果は,MSABLとMSCABLの正確なアプローチとしてSAT法の有効性を示した。

関連論文リスト

• Solving Cyclic Antibandwidth Problem by SAT [0.0]
  Cyclic Antibandwidth Problem (CABP) は、NP-hardグラフラベル問題である。 本稿では SAT-CAB と呼ばれる SAT-CAB の解法に基づく一般グラフ上でのCABP の最初の正確なアプローチを示す。 SAT-CABは、最先端のアルゴリズムによって得られる最もよく知られた解に一貫して一致するか、超えるかを示す。
  論文  参考訳（メタデータ） (2026-01-05T09:15:29Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。 実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
  論文  参考訳（メタデータ） (2021-12-22T11:27:48Z)
• Incomplete MaxSAT Approaches for Combinatorial Testing [0.0]
  本稿では,最小長の制約付き混合被覆アレイを構築するためのSAT(Satifiability)に基づくアプローチを提案する。 この問題はシステム障害検出のためのコンビネータテストの中心である。
  論文  参考訳（メタデータ） (2021-05-26T14:00:56Z)
• Covariance-Free Sparse Bayesian Learning [62.24008859844098]
  共分散行列の明示的な反転を回避する新しいSBL推論アルゴリズムを導入する。 私たちの手法は、既存のベースラインよりも数千倍も高速です。 我々は,SBLが高次元信号回復問題に難なく対処できる新しいアルゴリズムについて紹介する。
  論文  参考訳（メタデータ） (2021-05-21T16:20:07Z)
• On Continuous Local BDD-Based Search for Hybrid SAT Solving [40.252804008544985]
  CLSに必要な勾配を効率的に計算するための新しいアルゴリズムを提案する。 多くのベンチマークインスタンスに適用することにより、多用途CLSソルバであるGradSATの機能と限界について検討する。 実験結果から,GradSATは既存のSATおよびMaxSATソルバのポートフォリオに追加され,ブール適合性および最適化問題の解決に有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-12-14T22:36:20Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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