半道産値計画選考鋼魔潤

一・− − −−・i三、…喜一症∵ ・・−1＝＝−∴一二■￣モl・−−￣￣∴‥浅野 孝夫．． ・．・：・∴．沃●∴・、

ルーをもたらした斬新で画期的な手法として今日認

今回はこの講座の最後で「半正定借計画を用いた近似アルゴリズム」について述べる。主として最大化問題を扱うが，最小化問題も同様に扱える。多項式時間
で最適解を求めるのが困難な最大化問題に対して，近似解を求めるアルゴリズムのうちで，いつも最通解のα倍以上の解を入力サイズの多項式時間で求めるよ
うなアルゴリズムをαⅦ近似アルゴリズムという∴最大化問題に対するα≦且を近似率あるいは精度保証という。近似率α を限りなく1に近づけることができるとき，そのようなα一近似アルゴリズムをP甘ÅSという。すなわち，任意の正数e≦且に対してα＝1−∈とできる入力サイズ犯の多項式時間アルゴリズムをPTASという。さらに，入力サイズmと主の多項式 ∈時間アルゴリズムを好評mSという。問題によってはPmSが存在しないものも存在するu そのような問題においては，αが，ある値且以下ならばα一近似アルゴ
リズムが存在するが，ある値Ⅳより大にするとNP一因
難になることもある。この場合は，且≦打であるが，理論的には且＝ぴとなるような値を求めたい。MAX
3SAT（後述）に関しては且＝ぴ＝0，875と解決しているが，多くは未解決である。さらに，そのような定数
且ラぴが存在しない問題もある。

識されている。それまで，MAXCUTに対しては0ふ近似のアルゴリズム，MAX2SATに対しては0。75一近似アルゴリズムが最高性能のアルゴリズムであったがタ 彼らはSmP緩和法に基づいて，MAXCU甘およびMAX2SATに対して0．87856一近似アルゴリズムを得ているけ特に，MAXCUTに対しては多くの研究がなされたにもかかわらず，20数年近似率は0．5のままであったことを考えると，彼らのアルゴリズムが如何に画期的なことであったかがわかる．松井の本誌3月号の貴重な解説［20］からもこのあたりの状況が理解できるだろう。

これらのアルゴリズムが提案されて以来，SDP緩和法は近似アルゴリズムにおける極めて強力な道具として使われている．実際，グラフの最小点彩色［17］，最大独立集合［1］，［叫，スケジューリング［叫，VmSIの最大消費電力評価［4】などの問題に対する高性能近似アルゴリズムがSI〕P緩和に基づいて提案されている。なかでもMAXSATに関しては特別で，数多くの高性能近似アルゴリズムがSI）P緩和に基づいて提案されている9 そこで本稿では，MAXSATに関連する話題に焦点をあてて解説する。

∴ ；・∴ニ∴￣ ∴．こ・‥・そ「−し王

精度保証のある近似アルゴリズムの研究はGarey−♂ohmson［9］の本が出版される以前から研究されてきているが夕 景近近似アルゴリズムの理論の枠組みが統一化されるに従い，以前にもまして，急速に研究が進展している【礼 特に，GoemansuWilliamson【m］のMAXCU甘（最大カット問題）とMAX2SATに対する
半正志値計画（以下SりPと略記する）緩和に基づく
方法は，従来の近似アルゴリズムの設計解析手法の枠

組みを越えて，近似アルゴリズムにおけるブレークス

SAT（3SAT）は計算量の理論でNP完全性が示された最初の問題としても有名であり，多くのテキストで取りあげられている．．一方，MAXSAT（MAX3SAT）

は，最近の近似理論の枠組みで近似可能性に関して
MAXSNP…完全とかAPX一完全と呼ばれるクラスに属し，その意味でも頻繁に議論されている代表的問題である［2］。また，ⅢNAコンピュータなどの将来の計算機のモデルで，性能評価のベンチマーク問題としても取りあげられている。実用と関連しては，人工知能，

あさの たかお 中央大学理工学部情報工学科

VmSIの配線設計，線画解析等の論理システムにおい〒112−6551東京都文京区春日1−13−27てF各種の要求される条件をブール変数等からなる論

emai且：aSamO＠ise。ぬuo−Ⅶ．aC。」p

理式を用いてSATあるいはCSP（制約充足問題）で表

臨澄田（26）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ①リサーチ

現し，その解を求めてシステムを解析し評価すると

C5＝豆2V￡3，C6＝盃1V豆2V￡3，

いう手法がかなりの成功をおさめている．本節では，

ぴ（Cl）＝4，ぴ（C2）＝2，ぴ（C3）＝6，l〃（C4）＝8，

SATおよびMAX SATの定義を与え，それに対するぴ（C5）＝2，W（C6）＝6が入力として与えられたとする（ズ＝（￡1，∬2，諾3））．

従来の代表的手法を述べる．

そこで，霊＝（∬1，∬2，￡3）＝（0，1，0）と割り当てると，

2．1 SATの定義

C2，C3，C4，C6が満たされて重みの和は22になり，こP（諾い諾2，￡3）＝（∬1V￡2Vご3）∧（豆1V豆2V豆3）∧（∬1V

豆3）のような形の論理式が与えられたとき，ブール変れが最適解である．動＝1−ご壱であるのでq∈Cはq（諾）＝1一口（1−∬壱）H勘数（この例では諾1，∬2，ご3）に0，1（1＝真，0＝偽）を適当に割り当てて，充足可能である（1にできる）かどうかを判定する問題がSAT（satisfiabilityproblem，充足可能性問題）である．変数諾に対して盃はその否定で，￡＝1ならば豆＝0（諾＝0ならば虎＝1）であり，諾お

よび豆は総称してリテラルと呼ばれている．対象とす′・・ミ・＼、（1）■ ＼．

として諾＝（諾1，∬2，…，∬m）の関数と考えることができる・ここで耳はqに肯定形であらわれる変数の集合でズ㌻は否定形であらわれる変数の集合である・
こうして，任意の真偽割当諾∈（0，1）れに村しqはq（諾）＝0または1となり，真偽割当諾の借はる論理式は，諾VyV…Vzの形のいくつかの論理和が論理積でつながれたものとする．もちろん，論理和￡VyV…Vzは，リテラル∬，y，…，Zのどれか1つでも1のときに満たされて値1をとり，論理積∬∧y∧・・・∧z
は，リテラル諾，y，…，Zがすべて1のときのみ満たされて値1をとる．たとえば，

F（諾）＝∑ぴ（q）q（諾）

（2）

CJ∈C

と定義される．すなわち諾によって満たされるC内の論理和の重みの和が諾の値である．こうしてMAX
SATは値が最大となるようなごを見つける問題となる．なお，MAX SATの入力Cの各論理和がk個

P（諾1，ご2，￡3）＝（∬1Vご2V∬3）∧（勘∨豆2V豆3）∧（∬1V盃3）に対して，∬1＝1，∬2＝∬3＝0と割り当てると，∬1V諾2Vご3＝1，釣∨豆2V豆3＝1， 諾1V豆3＝1

以下のリテラルからなるときは，MAXSATはMAX
kSATと呼ばれている．MAX2SATも有名なNP一因
難（MAX−SNP困難）問題である【2］．

となるので，P（1，0，0）＝1である．

SATは最初に発見されたNP一完全問題である．上の例のように，論理和の形式で表現されたいくつかの式

2．3 MAX SATに対する確率的方法
SDPに基づく MAX SATの近似アルゴリズムをを論理積でつなげたものは，論理積標準形と呼ばれ，述べる前に，従来の近似アルゴリズムの代表的方法

特に，入力の各論理和がた個以下のリテラルで表現さ（確率的方法）を概観する．上の例で説明しよう．各変れるものをkSATと呼ぶ．SATは，3SATに限定して数諾意に対して釣を∬壱が真になる確率とする．する

もNP一完全であることが知られている．一方，2SATと，論理和Clが満たされる確率はplとなる．同様には0（m＋れ）の計算量のアルゴリズムで解けることがC2，C3，C4，C5，C6の満たされる確率はそれぞれ，知られている（mは論理和の数，mは変数の数）［5］．

2．2 MAX SATの定義

p2，1−p3，1−pl（1−p2），1−p2（1−p3）フ1−plp2（1−p3）となる．このように，各変数に真になる確率を割り当MAX SAT（maximumsatisfiabilityproblem，最大てた訂p＝（pl，p2，p3）をランダム真偽割当という．ラ

充足化問題）は，充足可能性問題の最適化版ともいえンダム真偽割当諾pによって論理和q∈Cが満たさるが，入力は論理和の集合Cと各論理和C∈Cに村れる確率はq（が）＝1−r㌦∈ギ（1−p五）m諾i∈町牒

する非負の重みぴ（C）の対（C，ぴ）で規定される．ズ＝となり，ランダム真偽割当諾pの期待値はダ（諾p）＝（￡1，ご2，…，諾れ）をCの論理和に現れる変数の集合と∑cブ∈Cて〟（q）q（諾p）となる・期待値は，ある意味です

する．すると，MAXSATは，各変数xi∈Xに対しべての割当の重み付き平均であるので，それ以上の値て，真偽割当をして満たされる（1となる）論理和の重をもつ割当が必ず存在する．そのような割当を見つけ

みの総和を最大にする問題である．たとえば，る方法として条件付き確率法が知られている．
上の例で簡単のため各p宣を0．5とおいて，条件付き

C＝（CいC2，C3，C4，C5，C6），
Cl＝∬1，C2＝￡2，C3＝豆3，C4＝豆1＞霊2，

2000年10月号

確率法を適用してみよう．するとランダム真偽割当は© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（27）521（0フ0フ0）∑ん≧1（1−0■5ん）耶≧仇5ダ（が）をみたすqただし，
Ⅳんはた個のリテラルからなる論理和全体Cんの給重み（0，0ヲ1）（0フ1，0）であり，昭はそのなかで最適解で満たされる論理和の総量みである（ダ（が）＝∑た＞1閃て）・Johnsonのア
ルゴリズムはリテラルを多く含む論理和に村して良（0フ1っ1）

い近似であることに注意されたい。実際，1個のリテ（170っ0）ラルからなる論理和が存在しなければ0。75−近似アル（1フ0，鼠）

ゴリズムになるし，論理和がすべて3個以上のリテラ
ルからなるときには0 875□近似アルゴリズムになる．

（1）1ヲ0）（1フ1，0）
図1：条件付き確率法の説明図

Johnsonが0ふ近似アルゴリズムを提案して以来，20年ほど近似率の改善は成功しなかったが，Yannakakis［23］がネットワークの手法を取り入れ改良し0−75−近似
アルゴリズムを提案するとGoemans−Williamson［叫諾p＝（0．5，0．5，0．5）となり，Cl，C2，C3，C4ブC5，C6の満も線形計画法に基づく方法で0．75−近似アルゴリズムたされる確率はそれぞれ，0．5っ0．5，0。5ル75，0．75，0。875を提案した小 これらについては原論文あるいほその解となり，期待値はダ（憲p）＝18。75となる。値が少な説［5］を参照されたい。

くとも ダ（が）であるような真偽割当が ∈・（0，1）れはぎ（班p）が各p宜の線形関数であることから，条件付

MAXSATMAXたSAT0■5

Johnson74［16】0・75Y92【23］っGW94［10］き確率法で以下のようにして求められる（固けpl以外のp宜を固定しタ plをpl＝ 0 とおいてみる。するとランダム真偽割当諾岩 ＝（0，0。570・5）で0．7584

Cl，C2，C3，C4，C57C6の満たされる確率はそれぞれ，
0ブ0。5，0。5，1，0，75，1となり，期待値は19．5になる．同様に，pl＝1とおくとランダム真偽割当ポ ＝（1，0。5，0，5）でCl，げ2フC3，抗，C57C6の満たされる確率はそれぞれ，170．5フ0．5鼎570．75，0．75となり，期待値はGW95［11］0．878（2）GW95［11］0．765 AOH96［6］ 0・931（2）『G95［8］0．770
A97［3］
0．801（3） TSSⅥ7【22】0．797‡ Z9 ［25］ 0．875（3） ⅨZ97［咽 0．83 1‡ AWO ［7］ 0・8721†（4） HZ9 ［12］18になる。したがって，期待値が大きくなる方に￡1の

図2：MAXSATに対する近似率．†は【咽での数値値を固定し，ランダム真偽割当端＝（0，0・5，0・5）を求実験で示された近似軋‡は［25］で予想された近似率める。次に，∬1＝0，諾3＝p3＝0＞5を固定しながらタに基づくもの。（）内の数字はMAXたSATの紋

p2＝0とおくと期待値は19となり，p2＝1とおくと期待値は20となるので，￡2＝1と固定し，ランダム
真偽割当三税＝（0，且フ0。5）を求めるn最後に，ご1＝0，3。SD㌘に基づく緩和法

諾2＝且を固定しながら，p3＝0とおくと期待値は

図2はMAX SATおよびMAXたSATに対する近22となり，p3＝1とおくと期待値は18となるので，

似アルゴリズムの性能比較である．0．75を超える近似￡3＝0と固定し，真偽割当粥1。＝（0，1誹）を求める。

率を実現したものはいずれもSDP緩和に基づいていこのように条件付き確率法に基づいて，常に前のる。特に，MAXたSATについては純粋にSDP緩和に

期待値以上の期待値をもつように，各変数に0，1を基づいているので以下ではMAXたSATを主に取り扱

割り当てていくことができる。したがってク ランダムう。MAX SATの結果はMAXたSATの結果と従来法

真偽割当の期待値の評価が重要になる。実際，John−を組み合わせたものが多い。なお，Hastad［13］によson の 0ふ近似アルゴリズムは上述のことを行ってりMAX3SATに対して（したがってMAXSATに対いる。各変数諾iが真になる確率p壱を0。5 としていしても）ア＝〟アでない限り0．875を超える近似率るので，た個のリテラルからなる論理和Cたの満たを達成する近似アルゴリズムが存在しないことが示される確率は1−0。5良となり，ランダム真偽割当￡p

されているので，Karlo駐Zwickの結果［18］はタイトの期待値ダ（が）ニ∑ん＞1（1−0・5ん）勒は∬（が）≧である。

52望（28）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ0リサーチ

以下，MAX2SATに村するGoemans−Williamson［11］，Fbige−Goemans［8］，Zwick［24】によるSDP緩最大にするような（−1，1）一割当封＝（yo，yl，…，封2れ）を求める問題となる（yo＝−1パん車＝【眺）．

和法およびMAX kSATに対するKarloff−Zwick［18］，半正定借計画問題に緩和するため，机に相応してHalperin−Zwick［12］によるSDP緩和法について説明

ノルム1でさらに宜≠0のときはu小言＝−1㌔ をする．いずれも満たす（2γl＋1）一次元のベクトルγ壱 ∈ 52m を導入（A）問題のSDP緩和による定式化を求める．

する（宜＝0，1，…，2γも）．こうして，各眺1机2をベクト（B

ルの内積γ壱1γ壱。に置き換え，弘彦2＝γ壱1町立2 とする（y ＝（弘豆2）は半正定借行列になる）．このように，多項式時間で求める．
（C）ランダムベクトルを用いて各ベクトルを

Goemans−Williamsonのアルゴリズムは絶対値1の変0，1に丸めて変数へのランダム真偽割当を求

数仇を月2れ＋1における単位球52乃上のベクトルγ壱

める（乱数使用ラウンデイングと呼ばれる）．

で緩和して2m＋1個のベクトルγ0，γ1，…，U2れを用い（D）ランダム真偽割当の期待値以上の値をもつるアルゴリズムである（γ0は∬0＝0を表現する参照

真偽割当を求める（デランダミゼーションとベクトル）．したがって，MAX2SATに対するベクト呼ばれる）．

ル計画緩和は，から成り立っている．以下では，（A）と（C）に注目する（実際最近のSDP緩和に基づく近似アルゴリズム
はこの部分の研究が主になっている）．（B）は前回までに取りあげられている．また（D）は文献［19】を参照されたい．簡単のため以下の表記を用いる．∬m＋壱＝豆壱（ご宜＝豆小豆，￡宜＋∬叫壱＝1）とおく．論理和ご壱∨∬JをC壱Jと表し，C五jの重みを勒と書く．1つのリテラルからなる論理和勘も諾。≡0を用いて便宜的に2つのリテラルからなる論理和∬。∨￡立と書けることになる．リ
テラルへの真偽割当諾＝（和ご1，…，∬2れ）∈（0，1）2叫1に村して論理和C壱ブ＝ごま∨∬Jの値z壱j（諾）および諾の値ダ（諾）は（1），（2），よりz壱ゴ（諾）＝1−（1−∬壱）（1−∬ゴ），（GW）max∑叫荊
Cり∈CS・t∴叛＝

3−γol′宣−γoIタブーγiγゴ（C壱J∈C）

γ宜∈52m（0≦宜≦2れ）γm＋壱γ壱＝−1（1≦乞≦れ）となる・ベクトルγ壱をγ0＝−1，γ壱∈（−1，りとすれ

ばMAX2SATと等価であることが確認できる，ベク
トル計画問題と半正走値計画問題が等価であること

は前回までの解説で紹介されているので，ここでは用語を互いに区別せずに用いる．

Goemans−Williamson のアルゴリズムはまずこの問題（GW）を多項式時間で解き最適解のベクトル

ダ（諾）＝∑cり∈C勒Z盲ゴ（諾）と書ける・

γ0，γ1，…，γ2れを求める．この解から（−1，1）一割当y＝

3．1 Goemans−Wi11iamsonの方法（yo，yl，…，y2れ）を求めることをラウンデイングという．

Goemans−WilliamsonのMAX2SATに対するアル
′ゴリズム［11］は最初に
帥＝−1，

ランダムな超平面で空間を2つの領域に分割し，γ宜がγ0と同じ領域に入るとき机＝−1（ご壱＝0）とし，反対

yO仇＝1−2諾壱の領域に入るとき眺＝1（￡壱＝1）とするものである．

とおいて，（0，け割当諾＝（和，￡1，・・・，∬2m）∈（0，1）2叶1から（−1，け割当y＝（yo，yl，…，y2m）∈（−1，1）2叫1に一対一対応させておく（諾叫壱＝1−∬壱より臥町H＝一肌）・したがって，諾壱は半となり（￡宜＝1と眺＝1，諾意＝0と肌＝−1がそれぞれ対応し），論理和C壱ブ＝￡壱∨エゴの値はy＝（恥訂1，・．‥，y2几）の関数として
Z壱ゴ（封）＝1−

Goemans−Williamsonのラウンデイングは，原点を通る

1＋yo机1＋訂0狛
2

2

二1−／′・・J′ ‥裾J／．−ノ′．町

このランダム真偽割当により論理和qJ＝諾意∨エゴの満たされる確率p立ブは以下のように計算できる．ベクトルγ0，γゎγJで決定される3次元の単位球面β2に射影して考える．原点を通りγ0（机上り）に直交する平面を九0（九わんj）とする．ん0を境界とする半空間

で，γ0を3次元の単位球面β2の点と見なしたとき，γ0を含む方（γ0を含まない方）を椋（毎）とする．同様に，吋，好，吋，ん㌃を定める・そして，単位球面
g2上の点pを，符号付きベクトルで表現する．たと4と書ける・さらに，yの値はダ（封）＝∑c孟，J。C勒Z壱ゴ（y）

えば点p＝（＋，十−）のときは，p∈椋∩好∩好を意となり，MAX2SATはF（y）＝∑ci，j∈CWijZij（y）を味する．すると原点を通るランダムな超平面は，それ2000年10月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（29）523

に直交するランダムな単位ベクトルγに相応し，γが平面上で，そのなす角鮎壱に基づいて回転し，得られ（【㍉＋，＋），（…㍉＋，州）フトラー，＋），（＋，¶，−））（＋rr＋），（＋√ト…）

た現（官≠0フ即ら＝即0）に対してGoemans−Williamson

3−即0即1一郎0即ゴー即i即JのときはziJ＝は1となる。したのラウンデイングを適用している。より具体的には，がってク 全球面の面積（触）に対する上記のような領2個のリテラルからなる論理和がなければ，原理的に域の面積が論理和Cb＝勘∨∬Jの満たされる確率pゎ・は，且個のリテラルからなる論理和Cも壱＝∬。∨ヱ豆のになる。これは満たされる確率聖の最適解に対する比が‖ニなるよ∂0壱＋恥J＋β五プに等しい（即0即′よ＝COSβ帥

27r

即0即j＝COS恥，即壱耶j＝COSβ壱j）．論理和抗仁＝勘∨∬J

うに，即。と朋五で定まる平面上で，回転後のベクトルが1個のリテラル∬宣からなるときほ，笹仁＝諾0，Zoj＝の角度軋が軋＝昔（乱…COSβ0壱）を満たすようにすと地 となり，単位円周上で2ればよい†しかしながら，2個のリテラルからなる論（一け）ぺ＋仁【）となる部分の割合告が論理和杭i＝

理和がある時にはこの回転でそのような論理和抗j＝諾。∨∬宣の満たされる確率p。宜になる。1個のリテラル￡iV∬Jの満たされる確率の最適解に対する比里止が減 ；り少してしまうこともある．そこで回転角を定める関数からなる論理和Cも壱＝ご0V諾言の満たされる確率poまと最適解における値袖＝』孝弘の比払は少なくともZoJ∫＝［0，¶・］→［0，汀］をパラメータ0≦Å≦且を用いて

2恥
α1≡ mlmqヂ（β）＝（1 Å）βり芸（且−CO5β）〉￣⊥叫

0三石訂≒打汀（1−COS触）である。最小値を実現する恥の値βム…）はT諾詔のβ に関する微分が1−COSβ−βsin∂（1川−COSβ）2であることから唯一に般）＝2．331122と定まり，α1＝0。878567となる。一方，2偶のリテラルからなる論理和吼＝諾壱∨￡ブの満たされる確率勒と最適解における値z宜J＝
3一即0即ヱ一郎0即ゴー即亀即Jの比聖上は少なくとも 二‥．7としている。こうして朋。，即iがなす平面上で即盲を回転して得られる即；は，即0と∂占壱＝′（恥）の角度をなすようにした。直観的には，なす角が90度から離れるようにして，ランダム性を排除しているといえる（どの2つのベクトルも直交するときランダムということになるので）。また，プは∫（打−β）ニ7T【プ（β）
を満たしていることに注意されたい。この関数による

2（恥＋恥＋β壱j）
α2

1：11エ1 0≦β。勅，βiJ≦打打（3仙COS恥州C岩s恥−COSβ壱ゴ）

即壱，即Jのなす角β五jと椋可のなす角鞍は，即0と即壱がなす平面とプ即0と即ノがなす平面の角度をαとおとなる。右辺のminの中身の部分は即五＝即J7触＝β且‡）（β宜J＝0ヲβ。壱＝恥＝艦））のときはα1に等しくなる

標形で即0＝（0フ0，1），即宣＝（sinβ0宜，0，COS‰），即ゴ＝ので，α2≦α1でありタ ー方，α2を実現する恥，恥（cosαSin＠oj，SinαSinOoj，COSOoj）と仮定できるので，

くと，一一般性を失うことなく，3次元正規直交鞘Z座

β宜Jをそれぞれ般）磯）β5言）とおくと，α1の定義より，
各化般）磯）磯）に対して，2♂≧町（1−COSβ）が得られ，α2≧α1であるt．すなわち，α2＝α1である。
このことから，論理和全体の期待値の最適解の値にCOSβ；メ＝COSβ昌彦COS‰＋cosαSinβム宜Sin‰
COSβ壱J＝COS触cos恥＋cosαSin軋sin恥をみたすことがいえる．彼らは入＝0．806765としてGoemans−Williamsomのラウンデイングをすると，得ら対する比は0。87856以上となり夕 期待値以上の割当はれる真偽割当は2個のリテラルからなる論理和￡宜∨諾メ

必ず存在し，そのようなものを見つける（従来のランにおいて満たされる確率p豆Jと最適解における値の比

ダム割当に対する確率的手法に対応する）方法［19］もpり u

存在するので，Goemans−Williamsonのアルゴリズム

ラルからなる論理和に対してこの比は0．976）以上には0．87856一近似アルゴリズムである．

なることを数値的に示し，0．93且09−近似アルゴリズム

3。認 許e五節円弧のemamSの回転が実現できることを示した．

FeigerGoemans［8jはタGoemans−Williamsonのラウンデイングで，最小の性能0．87856を実現するベクト2（鯨＋βム㌻‡＝＝刀（3【COS∂。l−CO；鋸ノーCOSβり） エリ

は0．93川9（1個のリテ

3巾3 Zw立地の回転
Zwick［24］は，∫（β）＝0（β＜昔），昔（∂＝昔）っ打

ルの組に注目し，そのようか状況を避けるようにでき（♂＞昔）を用いてベクトルを回転しその後Goemans−

れば，近似率の改善につながるはずと確信し，以下のⅥJilliamson のラウンデイングをすると，充足可能な手法を考案した。彼らはク ランダムな超平面でベクトMAX2SATのインスタンスに対してはどの論理和もルを分割する前に∋各即壱（ま≠0）を即0と即iで定まる

満たされることを示し，それに基づいて，回転関数を52僅（30）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ

4

5 0
5 0

3

5

3

−O﹂00q∈⊃u聖±4

5 0 5 02
2

0．8 0．82 0．84 0．86 0．88 0．9 0．92 0．94 0．96 0．98 1
relaxedvalue

0．21

図3：Z壱ゴに対する各関数の性能

0．4
0．6
relaxed value

0．8

1

・1

図6‥450個の論理和の緩和値z壱ゴの頻度

1

論理和C壱Jの値z宣Jと回転した彼の乱数使用ラウンデ

0．99
0．98

イングの論理和Cijの満たされる確率拘の比空吐を こり表したものである．図4と5はさらにFbige−Goemans

．

0．97

⊆
空0．96

と Zwick の詳細である．これからもわかるように，
Zwickの方法では精度保証は得られない．

0．95

岩臥浅野［15］はこれらのアルゴリズムの実際的性

0．94

能評価をするための計算機実験を行なっている．詳

0．93
0

0．1 0．2 0．3 0．4 0．5 0．6 0．7 0．8 0．9 1「elaxedva山e

図4＝Zijに対するFeige−Goemansの関数の性能

細はそちらを参照されたいが，ほぼすべての入力に対して同様の傾向が観察された．より具体的例を挙げ
よう．50変数，450個の論理和からなる入力で亡 ＝

10・12348のとき各論理和C壱Jの最適解における値z壱jを

0．9
0．8

0≦z壱メ≦0・01，0・01＜z五メ≦0・02，…，0・99＜z壱J≦10．7となるように0．01きざみで分類して，その個数をヒ

0．6

⊂〉
葛0．5

ストグラムとして表したグラフが図6である．最も多0．4

かったのは0・99＜z豆J≦1を満たす論理和であり，450

0．3個の論理和中186個の論理和が存在した・また，2宥

0．2
0．1

の値が1に近いz盲J＞1−亡＝0．87652となる論理和00

0．1 0．2 0．3 0．4 0．5 0．6 0フ 0．8 0．9 1
relaxed value

図5＝Z宜Jに対するZwickの関数の性能〇′亡1／3（β）＝＋恭（β一昔）〈箋 昔

2三2＜β＜喜一亡1／3，

三＋亡1／3＜β＜打は全論理和の72％程度であった．
このように，SDP緩和によって得られた各z壱jの値の分布を図6より観察すると，大半のz壱Jは1に近い値をとっている・図5よりZwickの関数はz宜ゴが大きくて1に近いときに良い性能を示すのに対して，托ige−
Goemansの関数は，図4より，Z宜ゴが1に近いときは，として定義した・なお，Ⅳ ＝ ∑ciJ。Cて旬，Z ＝最悪に近いときであり，Z壱ゴが小さいときに（すなわち∑cり∈C勒Z盲J・亡＝1−∴Z／Ⅳで，∈は小さいものと無視しても全体の値に与える影響は小さいものに対している・この関数J亡1／3（β）はほぼ充足可能なMAX

して）良い性能を示すことから，実験した全てのイン

2SATのインスタンス，すなわち，∈＝1−Z／Ⅳの十スタンスについて，近似解，期待値の双方に対して最分小さなインスタンスに対して良い性能を示す．

も性能の良かったアルゴリズムは，Zwickのアルゴリズムであった・Zwickによるアルゴリズムは，Feige−

3．4 実験結果

Goemansのアルゴリズムに比べて，eの値が小さいイ

図3はこれまで説明してきたGoemansqWilliamson，
Feige−Goemans，ZwickのSDP緩和問題の最適解の各2000年10月号

ンスタンスに優れているという理論的性能を持っている・しかし，実験の結果では，一般のインスタンスに村© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（31）525

しても良い性能を示すことが観察できた．

率とSDP緩和の定式化の最適解におけるC五jたゼの値

SDP緩和に基づく近似アルゴリズムの性能改善にの比は0．845173以上となることを示している。さらは，図6のような最適解のziJの分布を観察して，乱に，ランダム超平面に基づくラウンデイングを適用す

数使用ラウンデイングの期待値ができるだけ大きくなる前にベクトルを回転することで，上記の比が0．8721

るように最適緩和解のベクトルの回転を定めるとい以上になることを数値実験で示して，MAX4SATにうヒュいリスティツクスが有効であろう。

対して0 8721一近似アルゴリズムを与えている。

凱5 MÅⅩたSÅ甘アルヨ一肌ズム、ごこ こ；、‥つ・：∴MÅⅩたSATに対するSDP緩和は，MAX2SATに対するSI）P緩和に比べて複雑になっているu Karlo駐Zwick［咽は3個以下のリテラルからなる論理和に必要ならば∬0≡0を付加してC壱ブた＝ご五∨諾JV諾たとし，
relax（C壱Jん）＝mim

4−（即0＋即j）（即i2＋即宣

MAX2SATとMAXたSATを通して，SⅢPを用いた近似アルゴリズムの研究を概説した．昨年，MAXSATに対して，Zwick［25］はベクトルの外向き回転を提案して，純粋にSI）Pのみに基づくMAXSATのOu7977一近似アルゴリズムを与えている。解析的な証〈（minは（恒埴）の順列（わ，宜2，ね）すべてを対象とする）

明は与えられていないが，数値実験的にはそれが正を用いてタ MAX3SATに対する以下のSDP緩和

当化されている。この外向き回転はこれまで眺めてきたMAX2SA甘で提案された回転とは異なり，ある（KZ）max∑ぴ（C宣jた）z壱ブん

意味で直交（ランダム）に近くなるようにベクトルをC恒∈C，S。七・min‡relax（C壱jん），1）≧z五Jん（CiJん∈C）

回転するものである。Asano−Williamson［7］はMAX

即宜∈ぶ2れ（0≦宜≦271）

SATに対してGoemans−WilliamsonのLP緩和［叫で即れ＋壱即壱＝−1（1≦仁≦れ）得られる解の別の使用法を提案し，それをZwickのを提案し，それに基づいて7／8一近似アルゴリズムを得ている拝外 なお，豆≠0，j≠0，た＝0ならば，C宜Jた＝
C壱jでrelax（Cijん）＝

3一郎0即i一郎0即ゴー即i即Jであり，宜≠

0∴才＝ゐ＝0ならば，C宜JたニCo壱でrelax（Cijん）＝

主二響亀であることに注意されたいd この定式化は単純であるが，性能解析は極めて複雑である。ランダム
超平面を用いるラウンデイングで，論理和Cゎたが満

たされる確率は1個または2個のリテラルからなる
ときはこれまでと同じであるが，3個のリテラルから0。7977一近似アルゴリズム［25］と組み合わせて0．833−
近似アルゴリズムを得ている。

重複になるが，実際の応用と関連してSDP緩和に基づく近似アルゴリズムを設計するには，性能改善のため，SI）P緩和の定式化とともに，乱数使用ラウン
デイングの工夫が重要で，図6のような最適解のz壱Jの分布を積極的に利用して，乱数使用ラウンデイングの期待値ができるだけ大きくなるように最適緩和解のベクトルの回転を定めるというヒューリスティック
スも実用的には有効であろう。

なる論理和C宜ゴん＝￡宜∨∬JV￡たが満たされる確率は
1−prOb（即0，耶五フ即j∋閻た）となり，Zまゴゐに対する比は
α3＝

rnPn
即0，即i，即プ，即た∈g3

1…prOb（耶0，即五，即jフ射た）

参考文献
囲AlonN・andKahaleK・：

Approximatingthein−z宜ゴん

以上となる。ここで，prOb（即07即i7即ゴ，即ん）はランダム超平面で領域を2分割したとき即07即五フ即Jっ即んが同一の領域に存在する確率である疇 Karlo仔−Zwickは球面
幾何学および数値実験に基づいてこの比α3は7／8にdependence number via the♂function，Math・

ダroタrαmm甘mタフ80，pp・253】264，1998・［2］AroraS・

TheapproximabilityofNP−hardprob−

1ems ，Proc．封沼仁AC朋￣gympoβ豆祝m抑アんeory oJ
仇叩卯加堀pp．337−3∠皇8，1998．

なることを示している世軒

Halperin−ZwickはMAX4SATに対してSDP緩和の［3］Asar10T∴ ApproximationalgorithmsforMAX

定式化とその解のラウンデイングを提案しているが，

SATご Y瓦nnakakis vs． Goeヱnaヱ1S−Ⅵ7illiamso王1 フ

どちらも極めて複雑なものになっている［叫．これま什り（▲．〃／仁flnけ／斗／〃り）りバナ州＝川 r／〜川丹り．／（1（川卜でと同じランダム超平面に基づくラウンデイングで，p祝加タα乃d勒5fe7調βフpp・24−37，1997・

4個のリテラルからなる論理和杭州の満たされる確

526（32）［4］AsanoT・フHallddrssonM・M・，IwamaK・andMat−© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ

SudaT．：【15］岩間健一郎，浅野孝夫‥

Approximationalgorithmsfbrthemax−

MAX2SATに対する

imumpowerconsumptionproblemoncombinato−

近似アルゴリズムの実際的性能評価 ，情報処理

rialcircuits

学会研究報告，アルゴリズムAL−72−7，pp．49…54，，Proc．11thhLternationalSyrTWOSium2000．

onA190rithmsandComputation，tOapPear．

［16］Johnson D・S・：［5］浅野孝夫，今井浩＝ 計算とアルゴリズム ，オーCOmbinatorialproblems

ム社，2000．
【6］AsanoT・，OnoT・andHirataT・＝［17］KargerD・，MotwaniR・andSudanM・＝，NordicJ．Computin9，3，pP・388−404，1996．

［7］AsanoT．andWilliamsonD・P・：，JournalqFComput．and鞄β．ぶc窟リ9，pp．256−278フ1974．

Approximation

algorithms br the maximum satisfiability prob−lem

Approximation algorithms forimate graph coloring by semi−definite program−

ming

Improvedap−

Approx−，JournalofACA445，PP．246−265，1998．

［18］KarloffH・andZwickU．：J

A7／8−aPprOXimation＝／J′．＝1U−．トー／．11J．ヾJ／Jり仙、ノ〟〃＝川♪∴ヾ川イ・＿1／J／り−algorithm br MAX3SAT？

，Proc．38thlEEEr肋mβ，pp．96−105，2000．

・、■J／′り一り・、ノ〃〃‥川八川…／・′†／り〃、−イ「■・川′J川ト′・．トーー・ん＝・・．

proximation algorithmsfor MAX SAT門，Proc・［8］Feige U・and Goemans M，X・：

pp．406−415，1997．

Approximating

thevalueoftwoproverproofsystems，Withappli− ［19］Mahajan S・and Ramesh H・：
CationstoMAX2SATandMAXDICUT，Proc．

Derandomizlng

Semidefinite programmlng based approximation

バーハ／ム／…イ・ヾ〃〃′ノノ…ノ…′‥り／ソ7′川叩′ゾ／ ′り／／ノ川′ノJ′ご／

algorithms

αmd勒βfeγ乃β，pp・182−189，1995．

釣祝mdα如乃β OJCo汀岬祝fer∫c豆e†lCe，pp．162−169，［9］GareyM・R・andJohnsonD・S・＝

1995，

CorTWuterSand［20］松井知己： 半正定借計画を用いた最大カット問／／′／J…・／り／一／／／／′／．．1（−一丁J／′／′／り／／′・丁了′…川 イ．＼■J一−

題の．878近似解法 ，オペレーションズ・リサーチ，

CorTtPleteness ，Fteeman，1979．
［10］GoemansM・Ⅹ．andWilliamsonD．P．＝45，pp．140−145，2000．

New3／4−［21］SkutellaM．：

approximationalgorithmsforthemaximumsatis−
fiabilityproblem，アroc．錐娩〟姐打鞄明肌血m 即

Semidefinterelaxationsforparal−，SIAMJournalqfDisc．Math，， 1elmachine scheduling匹β窟祝m Om凡祝m血如mβ扉Co〝岬視ねrgc戎eγ乙Ce，pp．

7，pp．656−666，1994．

472−481，1998．

［11］Goe読anSM．X，andWilliamsonD．P．： Improved［22］Trevisan L．，Sorkin G．B．，Sudan M．an

approximationalgorithmsfor the maximum cut

andsatis茹abilityproblemsuslngSemidefinitepro−

WilliamsonDP・：

gramming

linear programmlng，JournalofACM42，Pp．1115−1145，

Gadgets，aPPrOXimation，and，Proc．37thlEEE SyrTq）Od、／′川‥り′八川…／〃／／り／′−、りノー（■‖Jり川／け・ヾ・・ん・JJ什、l，1，．

1995．
［12］HalperinE・andZwickU．＝Approximationalgo−brsemide負niteprograms ，Proc．7th Cor舵rence

imumsatisfiability

Ontheapproximationofmax−，J・A190rithms，17，PP，475−

502，1994．

＝＝／′′／リ／け／一′り〃J…′川′｛／−川・／（−‖J〃／一／J川／り／・ん′／りノト［24］Zwick U∴ Finding almost−Satisfying assign−

王宮m戎zα如れク エec抽reⅣ0亡eβ壱乃 Co汀岬祝￡er gc宜e†lCe

1610，Springer，PP．202L217，1999．

ments，Proc・29thACMSymposium on meory

O／Comp祝わmタ，pp．551−560，1998．

Someoptimalinapproximabilityre一［25］ZwickU．： Outwardrotations：atOOlた）rrOund−、・由、い・／ ′・川∴N／′・l（■、l／・、■J／川ノ仙、／州‥川●／ソ′川り／りノー

1ngSOlutionsofsemidefiniteprogrammlngrelax−

Co汀岬祝如タ，pp．1−10，1997．
［14］Hal1d6rssonM・M・＝

617−626，1996．
［23JYannakakisM．＝rithmsforMAX4SAT androundingprocedures［13］HastadJ・：，Proc．39thlEEESym一ations，WithapplicationstoMAXCUTandotherApproximationsofweighted

independentsetandhereditarysubsetproblems
J…り・′…／りノー「・一川／イ′．1／J／り／州JJいりJJ・／．・りり′／／川／／り／J．、．l、，

problems，Proc．31stACMSyrTu）OSium on me一

明川日加坤血相pp．679−687，1999．

pp．ト16，2000．

2000年10月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（33）527