論文の概要: Solving Cyclic Antibandwidth Problem by SAT

• arxiv url: http://arxiv.org/abs/2601.04239v1
• Date: Mon, 05 Jan 2026 09:15:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-09 17:01:52.811967
• Title: Solving Cyclic Antibandwidth Problem by SAT
• Title（参考訳）: SATによる周期的反バンド幅問題の解法
• Authors: Hieu Truong Xuan, Khanh To Van,
• Abstract要約: Cyclic Antibandwidth Problem (CABP) は、NP-hardグラフラベル問題である。 本稿では SAT-CAB と呼ばれる SAT-CAB の解法に基づく一般グラフ上でのCABP の最初の正確なアプローチを示す。 SAT-CABは、最先端のアルゴリズムによって得られる最もよく知られた解に一貫して一致するか、超えるかを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Cyclic Antibandwidth Problem (CABP), a variant of the Antibandwidth Problem, is an NP-hard graph labeling problem with numerous applications. Despite significant research efforts, existing state-of-the-art approaches for CABP are exclusively heuristic or metaheuristic in nature, and exact methods have been limited to restricted graph classes. In this paper, we present the first exact approach for the CABP on general graphs, based on SAT solving, called SAT-CAB. The proposed method is able to systematically explore the solution space and guarantee global optimality, overcoming the limitations of previously reported heuristic algorithms. This approach relies on a novel and efficient SAT encoding of CABP, in which the problem is transformed into a sequence of At-Most-One constraints. In particular, we introduce a compact representation of the At-Most-One constraints inherent to CABP, which significantly reduces the size of the resulting formulas and enables modern SAT solvers to effectively explore the solution space and to certify global optimality. Extensive computational experiments on standard benchmark instances show that the proposed method efficiently solves CABP instances of practical relevance, while identifying several previously unknown optimal solutions. Moreover, global optimal cyclic antibandwidth values are proven for a number of benchmark instances for the first time. Comparative results indicate that SAT-CAB consistently matches or surpasses the best-known solutions obtained by state-of-the-art heuristic algorithms such as MS-GVNS, HABC-CAB, and MACAB, as well as strong commercial Constraint Programming and Mixed Integer Programming solvers like CPLEX and Gurobi, particularly on general graphs, while also providing optimality guarantees. These results advance the state of the art for CABP and provide a new baseline for exact and hybrid methods on general graphs.
• Abstract（参考訳）: サイクリック・アンティバンド幅問題(CABP)は、NPハードグラフラベリング問題である。 大きな研究努力にもかかわらず、CABPの既存の最先端のアプローチは本質的にはヒューリスティックまたはメタヒューリスティックであり、正確な手法は制限されたグラフクラスに限られている。 本稿では、SAT-CABと呼ばれるSAT解に基づく一般グラフ上でのCABPの最初の正確なアプローチを示す。 提案手法は,従来報告されていたヒューリスティックアルゴリズムの限界を克服し,解空間を体系的に探索し,大域的最適性を保証する。 このアプローチはCABPの新規かつ効率的なSAT符号化に依存しており、この問題はAt-Most-One制約の列に変換される。 特に、CABPに固有のAt-Most-One制約のコンパクトな表現を導入し、結果の式のサイズを大幅に削減し、現代的なSATソルバが解空間を効果的に探索し、大域的最適性を証明できるようにする。 標準ベンチマークインスタンスに対する大規模な計算実験により,提案手法は,これまで知られていなかったいくつかの最適解を同定しながら,実用的な妥当性のCABPインスタンスを効率的に解決することを示した。 さらに、多数のベンチマークインスタンスに対して初めて、大域的最適環状反バンド幅値が証明された。 比較結果から,SAT-CABはMS-GVNS, HABC-CAB, MACABなどの最先端ヒューリスティックアルゴリズムや,CPLEX や Gurobi などの強力な制約プログラミングと混合整数プログラミングの解法,特に一般グラフ上での最適性保証といった,最先端のヒューリスティックアルゴリズムによって得られる最もよく知られた解と一貫して一致または超えている。 これらの結果はCABPの最先端を推し進め、一般グラフ上での正確かつハイブリッドな手法のための新しいベースラインを提供する。

関連論文リスト

• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
  論文  参考訳（メタデータ） (2025-02-13T17:14:18Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• No-Regret Constrained Bayesian Optimization of Noisy and Expensive Hybrid Models using Differentiable Quantile Function Approximations [0.0]
  Constrained Upper Quantile Bound (CUQB) は、制約近似を避けるための概念的に単純で決定論的アプローチである。 CUQBは制約のある場合と制約のない場合の両方において従来のベイズ最適化よりも著しく優れることを示す。
  論文  参考訳（メタデータ） (2023-05-05T19:57:36Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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