著者

柳澤 弘揮 宮崎 修一 岩間 一雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.107, no.537, pp.1-8, 2008-03-03

---

安定結婚問題は,GaleとShapleyによって提案されたマッチングの問題である.任意の例題について,解が存在し,それを見つける多項式時間が存在することが知られている.しかし,このアルゴリズムによって得られるマッチングは「男性最適」,つまり,男性にとっては好ましいが女性にとっては好ましくないマッチングである(逆に,男女の役割を入れ替えれば,女性最適なマッチングになる).GusfieldとIrvingによって提案された男女平等安定マッチング問題は,男女両者にとって「公平な」安定マッチングを求める,つまり,男性側の不満足度の和が女性側の不満足度の和になるべく近づくような安定マッチングを求める問題である.この問題は,強NP困難であることが知られている.本稿では,男女平等安定マッチング問題に対して,ほぼ最適な解を求める多項式時間アルゴリズムを与える.さらに,評価指標を一つ増やして,男女平等(sex-equality)の観点でほぼ最適なもののうち,全体の公平さ(egalitarian)が最小の安定マッチングを求める問題を考える.我々は,この問題がNP困難であることを示し,この問題に対して近似度が2より良い多項式時間アルゴリズムを構築した.

著者

柳澤 弘揮 宮崎 修一 岩間 一雄 ハルダースソン マグナス

出版者

FIT(電子情報通信学会・情報処理学会)運営委員会

雑誌

情報技術レターズ

巻号頁・発行日

vol.1, pp.13-14, 2002-09-13

著者

柳澤 弘揮 宮崎 修一 岩間 一雄 ハルダースソン マグナス

雑誌

情報技術レターズ

巻号頁・発行日

vol.1, pp.13-14, 2002-09-13

著者

岩間 一雄

出版者

全国障害者問題研究会

雑誌

障害者問題研究 (ISSN:03884155)

巻号頁・発行日

vol.36, no.1, pp.27-34, 2008-05

---

憲法25条とその精神を体した生活保護法は、勤労原則と必要即応原則との二つの原則を含んでいる。勤労原則とは、人はすべて労働すべきものであり、それによって生計を立て得ない部分について、保護の手を差し伸べるという原則である。エリザベス救貧法の根本原則であるといえる。対して、必要即応原則は、人間存在そのものに生存権を承認し、無条件にすべての人間の生存のために必要とするところを保障するという原則である。障害者、療養者、老人、シングルマザーなどに対する援助は、まさにこの原則によるといえる。すべての人間のために生存の条件を確保しようとする思考は、現代の「基礎収入」の思想である。憲法25条は、かくて、旧い勤労原則を保持しつつ新しい「基礎収入」原理を含んでいる。現代の第二の朝日訴訟は、旧い原則から新しい原則への転換という巨大な歴史的展望の中に立つものである。

著者

宮崎 修一 岩間 一雄

雑誌

全国大会講演論文集

巻号頁・発行日

vol.47, pp.79-80, 1993-09-27

---

NP完全問題は,問題のサイズに対して多項式時間で解くアルゴリズムが知られていない問題の代表例である.これらの問題は多項式程度の違いを無視すれば,同じ計算時間で解けるという点で,同じクラスに属する.即ち,ある問題を多項式時間で別の問題に変換することができる.これらの変換は,問題のNP完全性を証明するのに用いられてきた.多項式時間であればどのような変換であってもかまわないという大雑把なものであったが,問題を変換して解くという実用性を考えれば,変換の効率を良くすることが大切になってくる.例えば,CNF論理式の充足可能性問題(SAT)に対する効率の良いアルゴリズムに局所探索法と呼ばれるものがある.ハミルトン閉路問題をSATに変換し,局所探索法で解く場合には,変換によって得られる論理式のの変数の数によって計算時間に格段の差があることが分かっている.本研究では,別のNP完全問題である,グラフの頂点彩色可能性問題をSATに変換する方法を考察してみた.本稿では,まず,頂点数N,色数Kとして,N log K変数での比較的自然な変換の方法を述べる.次に,N logよりも少ない変数の数で変換する方法を2つ述べる.1つは,グラフ中に枝が少ないときに有効であり.もう1つは,枝の数が多いときに有効であることが分かった.NP完全問題は手に負えないという形で統一的に論じられることが多く,個々の問題の難しさの違いはあまり論じられていないようにみえる.本論文で述べている手法,つまりNP完全問題PをSATに変換するのに何変数必要であるかは,ある意味でPの難しさのメジャーになりうると考えられる.計算ステップ数,領滅量等の従来のメジャーとの大きな違いは,定数係数の違い,あるいは定数の差さえも十分に議論でき,それが重要とみなされる点である.

著者

大隅 剛史 伊藤 大雄 岩間 一雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.104, no.16, pp.31-36, 2004-04-15

---

近年のよく知られたWebグラフの問題の1つとして、グループ内で密にリンクされているWebページのグループを見つける問題がある。クリークは明らかにそのようなグループの例と言える。しかしクリークを求める問題(最大のものを求める、極大のものを列挙する)のほとんどは難しく、良い近似方法もない。本稿では「孤立した」クリークとその一般化として孤立した部分グラフを紹介する。部分グラフが「孤立している」とは、内部で密にリンクされているだけでなく、その部分グラフと外部とのリンクが少ないことをいう。例えば、サイズだのクリークでは、外部への枝はκ-1本以下しか許されない。このような孤立条件により、多くの問題が簡単になり、孤立したクリークを列挙する問題が多項式時間で解くことができる。また、孤立したクリークよりやや密度の低い準クリークについても、平均次数がκ-logだ以上でかつ最小次数がκ/(logκ)以上である準クリークを多項式時間で列挙できることを示す。さらにこれらの一般化として、連結度を利用して孤立した一般の部分グラフを多項式時間で列挙できることも示す。

著者

岩間 一雄 Lingas Andrzej 沖田 正樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.499, pp.49-55, 2005-12-15

参考文献数

17

---

木t-スパナーとは, グラフGの全域木でその伸長度がt以内(2つの頂点間の木上での距離がグラフ上での距離のt倍以内)であるものを言う. Gが木t-スパナーを持ち, 木t-1-スパナーを持たないとき, Gの伸長度がtであるという. 本稿ではグラフの伸長度を枝を追加して減少させる問題を議論する. 円グラフやグリッドグラフ等の特殊なグラフに対して最適な枝の追加アルゴリズムを与える. 一般のグラフに対しては問題は困難になるが, それでも, O(n/s')本の枝を追加して伸長度をs'にするアルゴリズムを与える.

著者

岩間 一雄

出版者

社団法人人工知能学会

雑誌

人工知能学会誌 (ISSN:09128085)

巻号頁・発行日

vol.24, no.1, pp.99-109, 2009-01-01