R-MaxSAT : 敵対者が存在する MaxSAT

DOI

書誌事項

タイトル別名
  • R-MaxSAT : MaxSAT with adversary

説明

<p>本論文では，Robust MaxSAT (R-MaxSAT) の一般化である，Robust weighted Partial MaxSAT (R-PMaxSAT) を提案する． R-PMaxSAT における意思決定者は，充足する節の重みの和を最大化する割当を探索することを目的とする． 一方で，R-PMaxSAT における敵対者は，意思決定者が決定した割当に対して，定数個以下のブール変数の割当を変更可能である． そのため，意思決定者が決定した割当は，敵対者による攻撃に対して頑健な必要がある． この問題の決定問題版は Sigma2P 完全であると証明されている． また，R-PMaxSAT は，敵対者が存在する場合の Clique Partitioning Problem (CPP) である robust CPP を表現できるため，多くの現実的なモデルに応用可能である． 本論文では，SAT ソルバー，QBF ソルバーをサブルーチンとして利用し，R-PMaxSAT の最適解を与える 2 種類のアルゴリズムを提案する． 計算機実験において，提案したアルゴリズムを利用することで，現実的な時間の下で最適解を導出可能であることを示した．</p>

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ