◆解説

離散最適化とその応用

第4回 離散最適化と協力ゲーム（2）毛利 裕昭，岡本 吉央…州…‖‖‖‖‖‖川…lll……‖m111…l…‖＝州…llll川111‖ll…＝＝‖州1111111111……l‖l…＝＝＝‖＝＝‖＝＝‖‖＝‖………………11……llll…l……＝…州Illl…‖州側＝ll…‖附‖……lllllllllltllllllll州Il…llllllttlllllllllll…llllttlll…tllt…

難な場合には，短時間で最適解を求めることが絶望視

1． はじめにされている．さらに，プレイヤーが邦人の場合には「離散最適化とその応用」の連載も今回で4回目と提携が2乃−1通り存在するため，協力ゲームの解を単なるが，今回は前回に引き続き「離散最適化問題から純なやり方で求めるには元の離散最適化問題を指数回生じる協力ゲーム」の解説を行う．前回は，多項式時解く必要が生じる．したがって，たとえ元の離散最適間で解ける離散最適化問題から生じる協力ゲームにつ化問題が．〝タ困難でなかったとしても，全体としていて取り上げたが，今回は〟．戸困難である離散最適多大な計算量が必要となる．このように，協力ゲーム化問題から生じる協力ゲームを扱う．特に，本稿ではの解を求める際には計算の困難さが二重に伴うことを応用を念豆引こおいて以下の協力ゲームを紹介したい

念頭において，以下の解説を読んで項きたい．

（．〝タ困難性など，計算量に関する用語については渡

2．〝タ困難な離散最適化問題から生じる

辺［22］などを参照されたい）．

協力ゲーム（1）巡回セールスマンゲーム

本節では，．〝．タ困難な離散最適化問題から生じる（2）施設配置ゲーム（3）箱詰めゲーム（これのみProfit Gameで，その他はCost Game）

いくつかの協力ゲームについて紹介するとともに，それらのゲームのプレイヤー集合と特性関数を明確にす（4）ネットワークデザインゲーム

る．

これらの協力ゲームの応用については，そのゲームの2．1巡回セールスマンゲーム名前からすぐに想像できるであろう．紙面上の制約にご存じのように，巡回セールスマン問題は，セール

より，多くの読者に馴染み深いと思われる（1）についてスマンがいくつかの都市を巡回する際の経路の長さを詳しく説明し，他の協力ゲームについては簡単な説明最小にしようという問題である．ここでセールスマンにとどめる．

を政治家，芸能人などの著名人に置き換えて，各都市個々のゲームの解説に移る前に，離散最適化問題かごとに講演をするような場合を考えてみよう．この場ら生じる協力ゲームの解を求める際の，計算量の観点

合，その講演者は各都市から依頼されて講演に行くのから見た困難さについて再確認したい．コア，仁，で，その移動費用は訪問先の都市が負担するのが当然

Shapley値などに代表される協力ゲpムの解を直接計である．このとき，講演者の総移動費用を各都市がど算するためには，一般にすべての提携情報が必要であのように分担するが適当か，ということを考えるのがる．これは元の離散最適化問題の最適解をすべての提巡回セールスマンゲームである．このゲームにおいて携に関して求めることに対応する．しかし，今回扱うは，プレイヤー集合Ⅳは訪問先の都市全体となり，協力ゲームのように，元の離散最適化問題が．〝タ困

Ⅳの部分集合Sに対する特性関数び（S）の値は，Sもうり ひろあきに含まれる都市のみを巡回する際の経路の最小距離に早稲田大学商学部

よって定められる．このゲームについては，節3にて〒169−8050新宿区西早稲田1−6−4
おかもと よしお
スイス連邦工科大学

より詳しく説明を行う．このゲームにおける費用分担の発想は，「巡回セールスマンゲーム」という名前がInstitutfQrTheoretischeInformatik，ETHZtLrich，CH−論文に登場する以前に存在しており，Fishburn and8092，Z凸rich，Switzerland
Pollak［10］の論文に見受けられる．なお，この論文
l14（42）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

の著者の一人であるPollakは，上記で説明した巡回める方法を考えるのが，箱詰め（ビンパッキング）問セールスマンゲームにおける著名人の立場に立って飛題である．この箱詰め問題から様々な協力ゲームを考行機でいろんな都市を回って講演することがあったらえることができるが，ここではFaigleand Kern［8］しく，このゲームのことを「エアプレーン問題」と呼において扱われている箱詰めゲームを紹介する．このんでいたとのエピソードがAlbersandAlexanderson

箱詰めゲームでは，プレイヤー集合Ⅳは荷物の集合［1］に紹介されている．と箱の集合の和集合として与えられる．また，．Ⅳの

2．2 施設配置ゲーム

部分集合Sに対する特性関数値び（5）は，5に含まれパソコンなどの同一種類の商品を生産しているいく

る箱のみを使ってSに含まれる荷物のみを詰め込んつかの企業が，その商品を生産するための原料を工場だときの最大の収納可能畳により与えられる．これをに配送する際の費用を削減するために，共同で複数箇顧客からの収納収益と読み替えることができる．実務所に配送センターを建設する計画をもっているとする．

的な問題への応用として，複数の倉棒金社が各々の倉ここで，配送センターの建設候補地と各企業の工場と庫を共同運用する際への通用が考えられる．倉庫全社の間の1日当たりの輸送費用や配送センターの建設費がそれぞれの所有する倉庫を供出し，各会社の各々の用が前もって分かっているものとする．さらに，配送荷物を倉庫へ収納する際の収益配分方法を考えるといセンターの1日当たりに配送可能な原料の畳や，各工うものである．ただし，現在の箱詰めゲームに関する場が1日当たりに必要とする庶料の量についても既知研究は一次元箱詰めの場合が中心で，また応用を意識であると仮定する．このような状況の下で，建設したした研究はこれまでのところほとんど存在しない．ま

配送センターからすべてのエ場に必要な分量の原料をた，この協力ゲームの理論的な研究はあまり進んでお配送することが可能という条件を満たしながら，配送らず，特定の場合におけるコアの存在条件が知られてセンターの建設費用と原料の輸送費用との総和を最小いる程度である．にするように配送センターの建設場所を定めるのが施

2．4 ネットワークデザインゲーム

設配置問題である．一方，配送センターの建設に関連通信ネットワークの構築を例にとって，ネットワーする諸費用を各企業間でどのように分担するかを考えクデザイン問題を説明しよう．通信ネットワークは，るのが，施設配置ゲームである．このゲームでは，プ端末群とそれらの端末間を結ぶ通信線群により構成さレイヤーの集合〟は企業の集合により与えられる．

れる．通信ネットワークの構築をするとき，端末間のまた，〃の部分集合5に対する特性関数値び（S）は，通信線を敷設するために費用がかかる．また，通信ネSに含まれる企業だけを考えて施設配置問題を解いたットワークを運用する際には端末間に通信のフローが際の最適値により与えられる．Goemansand Skutel−

流れ，フロー畳に比例した費用がかかる．各端末間の1a［11］は，特定の条件をもつ施設配置問題から生じる通信需要が前もって分かっているという仮定のもとで，ゲームのコアが非空であることと，元の施設配置問題

通信線の敷設費用とフロー費用の総和を最小にするネの線形計画緩和に整数ギャップが存在しないことが同ットワークを決定する問題が，ネットワークデザイン値であることを示すとともに，この結果を踏まえてコ問題である．このネットワークデザイン問題から様々アが非空な場合にその一点を多項式時間で求めるアルな協力ゲームを考えることができる．例えば，各端末ゴリズムを提案している．

をプレイヤーと見なす場合や，端末のペアをプレイヤ

施設配置問題は♪−Center問題や♪−median問題なーと見なす場合などが考えられるが，ここでは，プレどの多種多様なバリエーションをもっているので，そイヤー集合．Ⅳが端末集合で与えられている場合にっれに対応して施設配置ゲームも様々なバリエーションいて説明する．この場合，端末の部分集合Sに対しが存在する．これらの施設配置ゲームについては，てその特性関数の値〃（S）は，Sに含まれる端末のみ

Curiel［4］において Location Game の名で一つのを考慮した場合のネットワークデザイン問題の最適値章を割いて詳細に記述されている．

により与えられる．このゲームに対しては，Kubo

2．3 箱詰めゲーム

and Kasugai［12］がコアの一点を近似的に多項式時間様々な大きさの荷物と，それを収納するための様々で求める研究をしている．また，Mohri［15］は，全体な容箪をもついくつかの箱が与えられているとき．各合理性（パレート最適性）を満たすためにネットワー

箱の容量を満たしつつ，なるべく多くの荷物を箱に話

クデザイン問題を1回解くだけで求められる費用配分

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

（43）115解を示した．

3．巡回セールスマンゲーム
この節では，巡回セールスマンゲームに焦点を置いて，その理論的な側面の話を展開していく．

図l巡回セールスマンゲームの例

3．1巡回セールスマンゲームの定義
巡回セールスマンゲームをしっかり定義するところから始めよう．そのためにまず，巡回セールスマン問ン問題の最適値と定義する．ここで，Cl5冊1は費用関題を導入する．巡回セールスマン問題は最適化問題で数cの（SU（0））2への制限で，すべての（才，ノ）∈（SUある．巡回セールスマン問題の入力は，非空な有限集（0））2に対して，Cl5∪（。｝（才，ノ）＝C（g，力である．また，合Ⅳと，〃の直積Ⅳ2上の非負の費用関数c：空集合に対しては〃（郎＝0としておく．5としてⅣ〃2→R十の二つで与えられる（費用関数cは，l〃l次自身を選んでくると，む（〃）は集合Ⅳ∪（0）と費用関の非負正方行列であると思ってもらってよい）．この数cを入力とする巡回セールスマン問題の最適値で入力に対して，巡回セールスマン問題の許容解（実行ある．プレイヤー集合Ⅳと，上のように定義された可能解ともいう）は，．Ⅳの順列で，サイクルの数が特性関数〃：2〃→R＋のペア（Ⅳ，〃）を一つだけのものである．これは，Ⅳを頂点集合とし，ンゲームと呼ぶ．特性関数びは費用関数cに依存しすべての項点の間に有向辺が南向きについている有向ているので，それを陽に表すためにぴではなく ぴ。とグラフの上で，すべての項点をちょうど1回ずつ回っ書くこともある．節2での記述と対応させると，講演てきて再びスタートの頂点に戻ってくるような閉路者の住んでいる場所が0であり，訪問先の都市の集（ハミルトン閉路と呼ばれる）を考えることと同じで合がプレイヤー集合〃になる．

ある．巡回セールスマン問題の目的関数は，この閉路

巡回セールスマ例を挙げよう．図1ではⅣ＝1，2として，無向グラに現れる辺eに付随する費用c（e）の和である．そしフが描いてある．それぞれの辺のそばに書いてある数て，この目的関数を最小にするような許容解を見つけ字が，辺で結ばれている二つの頂点の間の費用を表しる問題が巡回セールスマン問題である．ている．つまり，C（0，1）＝C（1，0）＝3，C（0，2）＝C（2，0）

この定義より，費用関数cに対して，「すべてのオ∈Ⅳに対してc（オ，才）＝0である」と仮定しても，許容＝2，C（1，2）＝C（2，1）＝2であり，C（0，0）＝C（1，1）＝c（2，2）＝0である．

解全体の集合と目的関数値が変わらないので，今後，このときに，ぴ（（1））は■0からスタートして1に到達

一般性を失わずにこれを仮定していく．なお，巡回セし，そして0に戻ってくるときの費用の和になる．

ールスマン問題そのものに関する情報がCookによりよって，〃（（1））＝6である．同様に，〃（（2））＝4になる．

集められていて，プリンストン大学にあるWEBサーぴ（（1，2））は0からスタートして1，2の両方をちょうバを通じて公開されている［21］．このページはすこぶ

ど1回ずつ回って0に戻ってくることを考えたときる興味探いので，ぜひ訪ねてみていただきたい．の費用の和の最小値である．この例では，0から初め巡回セールスマン問題の定義が終わったので，引きに1へ行って次に2に行き0に戻る場合と，0から続いて，巡回セールスマンゲームを定義する．巡回セ

初めに2へ行って次に1に行き0に戻る場合で費用

ールスマンゲームは特性関数形の協力ゲームである．の和が変わらず，ぴ（（1，2））＝7になる．また，〃（卵＝0プレイヤーの集合をⅣと して，特性関数を〃：である．

2〃→R十とする（ここで，2〃はⅣの部分集合全体の一つ注意しておきたいのは，巡回セールスマンゲー集合で，Ⅳのペき集合と呼ばれるものである）．巡回

ムにおいては，特性関数が表すのは提携が負担する費

セールスマンゲームでは，まず，．Ⅳの要素でない0用になっていることである．ゲーム理論の標準的な教を用意して，〃∪（0）を考える．そして，巡回セール

科書に表れる特性関数形ゲームでは特性関数が表すのスマン問題のときと同様に，費用関数c：（〃∪は提携が得る利益であるのに対し，ここでは逆の意味（0））乙→R十が与えられている．このときに，提携5⊆付けがなされていることになっている．

Ⅳの特性関数値〃（5）を，集合SU（0）と費用関数
cLs。I。i：（SU（0））し＞R＋を入力とする巡回セpルスマ
116（44）

巡回セールスマンゲームは，費用関数c：（Ⅳ∪（0））乙→R．によって次のような分類ができる．まず，© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

cが「すべてのオ，ノ∈Ⅳ∪（0）に対してc（f，ノ）＝C（ノ，f）る」ということを証明し，このような分類が事実上不である」という条件を満たすときは，（Ⅳ，ぴ。）は対称可能であることを示した．証明自体はそれ程難しいも巡回セールスマンゲームと呼ばれる．そうでない場合のではないが，このような基本的な事項が見捨てられは，非対称巡回セールスマンゲームと呼ばれる．次に，てきていたということ自体も興味深い．

cに対して「すべての才，ノ，々∈〃∪（0）に対してc（f，ここで，上のOkamoto［18］による定理に関して少々）≦c（才，ノ）＋c（ノ，鳥）である」という条件を三角不等式し補足をする．この定理は「与えられた巡回セールスという．費用関数cが三角不等式を満たしていてもマンゲームのコアが非空であるかどうかを判定する問

対称ではない場合もあることに注意する．

題」という判定問題に関するものであるが，「巡回セ3．2 コアの非空性ールスマンゲーム」を与えるとはどういうことなのだ

ここからは，巡回セールスマンゲームのコアの非空ろうか．つまり，コンピュータへの入力として何を与性を考察する．実は，巡回セールスマンゲームというえるのだろうか．このときにすべての提携5⊆Ⅳに対象に関して，コアの非空性以外の研究はほとんどな対する特性関数値び（S）を与えてしまうと，それだけされていないのが現状である．なお，以下では，歴史で，プレイヤーの数l州に対して指数関数サイズ，つ的な順番に結果を並べることはせずに，ストーリーのまり2刷−1個の値を入力することになってしまう．

展開がより自然になるようにそれらを並べることにす

ここでは，巡回セールスマンゲームの与え方として，るので，その点について了承していただきたい．

ただ，すべてのペア才，ノ∈Ⅳ∪（0）に対する賀用関数

巡回セールスマンゲーム（〃，〃）のコアC（〃，〃）との値c（オ，ノ）を入力として与えることにするのである．

は，次のようなベクトルの集合である．C（〃，〃）＝（zこの場合は，（lⅣけ1）2個の値を入力すれば済むこと∈R〃：8≠S⊆〃を満たすすべてのSに対して∑滝ざZになる（もっとも，C（オ，ブ）＝0という条件を使えばも≦ぴ（S），かつ∑f∈ルむ＝〃（〃））．巡回セールスマンゲ

う少し減るが，0（l州2）個には変わりない）．これで，ームでは特性関数が費用を表しているので，通常の特計算理論的に意味のある入力の与え方ができたことに性関数形ゲームにおけるコアの定義とここでの定義で，なるわけである．

不等号の向きが違っていることに注意する．図1にあ完全な分類は難しいことが分かったので，次の要求る例に対して，その巡回セールスマンゲームのコアはとしては，どのような場合にコアが空になって，どの図2の太線で表されている線分になっている．

ような場合にコアが非空になるのか，という条件をいコアに所属するベクトルをそれぞれのプレイヤーがろいろ知りたい，ということになる．

納得できる費用配分の仕方を表すものだと考えると，はじめに単純なケースから観察することにしよう．

どんな場合にコアが非空になり，どんな場合に空になプレイヤーの数が1の場合は，コアが常に非空であるるのか，というのを分類して，さらに，できることなことが走去よりすぐに分かる．プレイヤーの数が2のらば，与えられた巡回セールスマンゲームを見て，コ場合はどうだろうか．この場合は，「対称巡回セール

アが非空なのか空なのかを簡単に判定したい，というスマンゲームでプレイヤー集合をⅣ＝（1，2）とすると要求が生まれる．この要求に対して，Okamoto［18］き，コアが非空になる必要十分条件はc（0，1）＋c（0，は「与えられた対称巡回セールスマンゲームのコアが2）≧c（1，2）が成立することである」ことが次のような非空であるかどうかを判定する問題は〟タ困難であ計算から分かる．図3も参考にしていただきたい．
まず，今の状況から，〃（（1））＝2c（0，1），ぴ（（2））＝
2c（0，2），〃（（1，2））＝C（0，1）＋c（1，2）＋c（0，2）と，特性関数値が明快な形で書き表せる．コアが非空である

図2 コアの例

2003年2月号

図3 プレイヤーの数が2の場合© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（45）11丁∬む∈（0，1）∀才，ノ∈5∪（0）．と仮定すると，コアに所属するあるベクトル（zl，為）が存在することになる．このとき，コアの定義から，この整数計画問題の最後の制約「ことび∈（0，1）」を「0≦Zl≦州1））＝2c（0・1），Z2≦ぴ（（2））＝2c（0・2），Zl＋z2∬心≦1」に置き換えたものを考えよう．これは，最適〃（（1，2））＝C（0，1）＋c（1，2）十c（0，2）が成立していない化の理論において「0／1制約を緩和する」と呼ばれてといけない．この三つの式を組み合わせると，C（0，1）

いる操作で，整数計画法，離散最適化において，重要＋c（0，2）≧c（1，2）とし．−う望んでいた式が浮かび上がな役割を担っているものである．実は，この度和がコってくる．逆に，C（0，1）＋c（0，2）≧c（1，2）が成立するアの非空性と関係しているのである．命題の形で言明と仮定すると，ベクトル（2c（0，1），−C（0，1）＋c（1，2）

を述べると，「巡回セールスマンゲーム（Ⅳ，〃）にお＋c（0，2））がコアに所属することが分かる．

いて，値〃（〃）が上の整数計画問題の緩和問題で5＝（5）特に，三角不等式を満たす対称巡回セールスマンゲ．Ⅳとしたものの最適値と等しいとき，この巡回セーームでプレイヤーの数が2なら，先の不等式c（0，1）

ルスマンゲームのコアは非空である」となる．これは＋c（0，2）≧c（1，2）は自動的に満たされるので，コア

Tamir［20］で言及されているが，証明は載っていないは非空になる．実は，三角不等式を満たす対称巡回セ（この命題はFaigle and Kern［8］でも言及されていールスマンゲームでプレイヤーの数が4以下ならば，る）．証明自身は線形計画ゲームのコアの非空性を適そのコアは非空になる（Tamir［20］）．Kuipers［14］用することになる．この条件と似たものは他の離散最は，同じ仮定のもとでプレイヤーの数を5にした場合適化問題から得られる協力ゲームに対する文献でも見でもコアが非空であることを証明している．そうするることができ，例えば，Denget al．［5］，Faigle andと，同じ仮定のもとでプレイヤーの数が6の場合はどKern［9］，Goemans and Skutella［11］にこれと類似うなのか，と気になるが，これについて，Tamir［20］した（ある意味でより強い）結果があり，離散最適化はコアが空になる例を挙げている．また，非対称巡回問題から得られる協力ゲームの理論における，美しいセールスマンゲームにおいて，Curiel［4］は，三角不定理群を成している．

もう少し具体的な条件を見ることにしよう．Curiel

等式を満たしていてプレイヤーの数が3以下であるならば，そのコアが非空になることを示しており，また，［4］では，費用関数が三角不等式を満たして，「0が〃Pottersetal．［17］は，三角不等式を満たしていてもプから遠く離れている」ときには，コアが非空になるこ

レイヤーの数が4だと，そのコアが空になるようなもとが示されている（ここで，「0がⅣから遠く離れてのが存在することを示している．

いる」というのを形式的に記述する必要があるが，それについてはCuriel［4］を見ていただきたい）．これ

実はこのような「プレイヤーの数がどのように影響するか」ということは，ゲーム≡哩論においてよく調べは，例えていうと，講演者が名古屋を出発点として，られる事柄である．しかし，これだけでは大規模な問訪問先がすべてチューリッヒにあるような場合には，題に対する知見は得られないので，プレイヤーの数かコアが非空になるら離れた事柄も見ていく必要がある．

，ということを意味している．

また，三角不等式を満たしていて，かつ，Ⅳ∪（0）

そのようなものとして，まず，線形計画緩和に基づの二つの部分への分割でその二つの部分が互いに大きく条件を見てみることにする．巡回セールスマン問題

く離れているような状況でも，コアが非空になることが次の形の整数計画問題として定式化できることはよが知られている［16］（こちらも，形式的な記述についく知られている．つまり，巡回セールスマンゲームては，Pottersによる元の論文［16］を見ていただきた（〃，〃）に対して，特性関数値〃（∫）は次の整数計画

い．Curielの本［4］にも記述がある）．

問題の最適値である．

他にもコアが非空になるための条件がいくつか知ら

mln． ∑ c（才，ノ）ェ烏（1）f．J∈5U†oI

れているが［4，16，17，20］，もう少し系統的に調べる手立てとして，Okamoto［18］は巡回セールスマン問題

subject toが多項式時間で解けるような費用関数のクラスに注目

Jむ＝1∀オ∈5∪（0），

都，、｛f，した．例えば，Monge行列という行列のクラスがあ∑ Jむ＝1∀ノ∈SU（0），る．正方行列AがMonge行列であるとは，i＜j，ノ∈（gU（0））＼（fI∑Jむ≦lrト1∀β≠r⊆SU（0）， fJ∈r

＜Jを満たす任意のど，ノ，々，Jに対して，α（オ，々）＋α（ノ，ハ≦α（f，J）＋α（ノ，々）が成立することと定義され118（46）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ発されたものである）．

た亀ロ

3．3 その他の解○その他の解について，一言触れておく．巡回セールj○

スマンゲームの仁，Shapley値など全体合理性を満た□

す解を計算することが．〝タ困難であることは直ちに左辺＝□の和
右辺＝○の和分かる（仁やShapley値の走去は標準的なゲーム理論の教科書に出ているので，そちらを参照していただ

国4 Monge行列きたい）．というのは，もしそのような計算が多項式る．図4がMonge行列の様子を表している．
費用関数がMonge行列であるような巡回セールス時間で出来てしまうと，解の全体合理性から，元の巡回セールスマン問題の最適値を多項式時間で得ることマン問題は多項式時間で解けることが知られているができてしまうが，しかし，巡回セールスマン問題は［6］．この結果を利用することで，費用関数がMonge一般に〟タ困難なので，これはタ＝〟タを導いてし行列であるような対称巡回セールスマンゲームのコアまうからである．の非空性を証明できる（実は，Supnick［19］の結果をただし，先に挙げたような巡回セールスマン問題が使うと，証明がより簡単になる）．また，Kalmanson

多項式時間で解けるようなクラスに限定したときに，行列という行列のクラスも巡回セールスマン問題が多仁やShapley値の計算が（計算理論的に）どれ程難項式時間で解ける場合になることが知られていて［13］，しい問題なのか，ということはよく分かっていない．

この場合にも対応する巡回セールスマン問題のコアが非空になる［18］（実は，より強く，Submodularにな4．おわりにることまで証明できる）．費用関数がKalmanson行．〝ア困難な離散最適化問題から生じる協力ゲーム

列になる場合の例として，Ⅳ∪（0）が平面上のある凸の研究状況はまず，コアの非空性に関する議論が現在多角形の項点集合になっていて，二つの頂点び，紺∈の研究の中心である．このゲームについての解を具体Ⅳ∪（0）の間の費用がそのユークリッド距離であるよ的に求めるアルゴリズム，および，新しい解の提案にうな場合が挙げられる．

ついては試行錯誤的に行われているといった発展途上

ただ，巡回セールスマン問題が多項式時間で解けるの段階であるというのが著者の見解である．ただ，ような費用関数のクラスが常に対応する巡回セールス様々な応用分野が広がっており，今後，研究の進展がマンゲームのコアの非空性を導くわけではないことも社会的に期待される．

Okamoto［18］は指摘している．また，巡回セールスマン問題が多項式時間で解けるような費用関数のクラ謝辞 執筆に当たり船木由喜彦氏（早稲田大学），塩スでOkamoto［18］で考察されていないようなものも浦昭弟氏（東北大学）に憤稿をお読みいただき，ミスあるので，それらのクラスに対してどのような状況がの指摘および有益なコメントを頂いたことに感謝しま生まれるのかということは，今後の展開となるだろう．

す．なお，本稿に関する票任はすべて著者にあること

巡回セールスマン問題が多項式時間で解けるような場をお断りしておきます．なお，本稿は早稲田大学特定合のサーベイは文献［3，6］にあるので参考にしていた

課題研究助成費2002A−063の成果の一部であり，まだきたい．

た，the Berlin−ZurichJoint Graduate Program

Okamoto［18］が巡回セールスマン問題の多項式時間で解けるようなクラスと巡回セールスマンゲームのCombinatorics，Geometry，and Computation（CGC）による研究助成に感謝します．

コアの非空性の関係を考察したのと同様に，
Goemans and Skutella［11］は施設配置問題の多項式

お詫び 前回連載原稿「1．3．3 仁」の解説において，時間で解けるようなクラスと施設配置ゲームのコアの最初の文章を除く細かい部分で筆者の校正ミスによる非空性の関係を議論している．さらに系統立った取り誤りがありましたことをお詫びいたします．

扱いに関してはDengetal．［5］を参照していただきた
参考文献

い（歴史的な観点から言うと，Okamoto［18］の研究
はDengetal．［5］とGoemansand Skute11a［11］に触
2003年2月号【1】D．J．Albers and G．L．Alexanerson，MdthemaEica© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（47）119hpt，le：PrqGles andlnh2Views Birkhause Boston
Inc．，1985．

［12］M．KuboandH．Kasugai，DesignGame［2］J．M．Bilbao，Coqi，eltltive Gam60n Combina10rial
StnLCiuns，KluwerAcademicPublishers，2000．
［3］R．E．Burkardetal．，

Well−SOlvableSpecialCases

Of the Traveling Salesman Problem：A Survey，

OntheCoreofNetwork，Jour7Wl〆㊥emtionsReseaYChSbcie妙力砂α乃，35（1992），250−255．

［13］K．Kalmanson，

Edgeconvex circuits and thetraveling salesman problems，CbnadidnJoumald〟α′如∽αfオα，27（1975），1000−1010．

［14］J．Kuipers，A Note on the5−perSOn TravelingS〟1朋㌧熱紺ね叫40（1998），496−546．

［4］Ⅰ．Curiel，Co呼e和tiueGame771eOWandApplications，KluwerAcademic Publishers，1997．
［5］Ⅹ．Deng，T．IbarakiandH．Nagamochi，SalesmanGame，ZO凡21（1993），339−351．
［15］H．Mohri，Algorith−

Design GameOn Solutions of a Type of Network，771e PnceedinBS 〆1ntemational

micAspects ofthe Core ofCombinatorialOptimiza−

Cの旦々柁乃Cβ0乃∧わ乃Jわ2βαγA乃β如ねα乃dCo乃〝αA乃αか−tionGames

Sii2001，tO appear．

，Mathematics q／物eYations Resea7rh，24（1999），751−766．

［16］J・A・M・Potters，［6］P，C．Gilmore，E．L．LawlerandD．B．Shmoys，Well−Gamessolvedspecialcases，in［7］，87−143．
lem，Wiley andSons，1985．

［17］J．A．M．Potters，I．J．CurielandS．H．Tijs，
ingSalesmanGamesOn some approximatelybalancedcombinatorialcooperativegames

MongeProperty［9］U．Faigle and W．Kern，Submodular Cost GamesOn the Core of Ordered，Mathematical乃1曙ram−∽オ囁87（2000），483−499．

［19］F．Supnick，Extreme Hami1tonian Lines［11］M．X．Goemans and M．Skutella，

Cooperative，ACM−SmM SOa42000

PYVCeediタ郡，（2000），76−85，tO appearinJoumal

A朋肋めq〆〟加転職妨ね66（1957），179−201．
OntheCoreofaT；avelingSalesman，（わeYationsResearchLetters，8（1988），31−34．

WWW．math．princeton．edu／tsp／［22］渡辺治，『計算可能性・計算の複雑さ入門』，近代科学社，1992．

Aなロわ助∽S．

（6）p．39 右カラム 3．2より下から2行目

く前号印刷訂正〉（1）p．36 左カラム1．1，12行目
経済学からの → 経済学の乃種類 → カ種類（7）p．40（11）式（2）p．38 左カラム 2．3，3行目
単純な連結 → 完全♪ → 〝2（8）p．40（lカ式を以下にさしかえJ乃（3）p．38 右カラム 下から6行目∑恥y ≧eノ ブ＝1

f＝1

費用は 一→ 限界費用は，…，β（9）p．40（14）式（4）p．39 左カラム 2．5直前の二つの場合 → などの複数の場合

ダー → yi＊（lq）人名訂正（全般）（5）p．39 左カラム 下から7行目
最小全域木ゲームが → 最小全域木がEdomonds 一→ Edmonds
Zelmel一→ Zemel
渡辺浩 → 渡辺治

120（48），［21］TravelingSalesmanProblemHomePage，http：／／（1983），366−378．

Facility LocationGames

TravelingSalesmanGameswiththe

FixedRouteCost
CostAllocationGame，Ame7ican MathematicalMonth玩 90，MdthematicalPYtqYamming153，Submitted．

［20］A．Tamir，［10］P．C．FishburnandH．0．Pollak，Trav（1992），199−211．

，ZOR，38 ［18］Y．OkarnOtO，（1993），14ト152．

Allocation，Methods〆CbeYZltions ReseaYrh，59（1989），

263−276．

［7］E．L．Lawleret al．，771e7ねびelわ堵Sblesman PYOb−［8］U．Faigle andW．Kern，AClassofTravelingSales望an© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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