著者
柳澤 弘揮 宮崎 修一 岩間 一雄
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
巻号頁・発行日
vol.107, no.537, pp.1-8, 2008-03-03

安定結婚問題は,GaleとShapleyによって提案されたマッチングの問題である.任意の例題について,解が存在し,それを見つける多項式時間が存在することが知られている.しかし,このアルゴリズムによって得られるマッチングは「男性最適」,つまり,男性にとっては好ましいが女性にとっては好ましくないマッチングである(逆に,男女の役割を入れ替えれば,女性最適なマッチングになる).GusfieldとIrvingによって提案された男女平等安定マッチング問題は,男女両者にとって「公平な」安定マッチングを求める,つまり,男性側の不満足度の和が女性側の不満足度の和になるべく近づくような安定マッチングを求める問題である.この問題は,強NP困難であることが知られている.本稿では,男女平等安定マッチング問題に対して,ほぼ最適な解を求める多項式時間アルゴリズムを与える.さらに,評価指標を一つ増やして,男女平等(sex-equality)の観点でほぼ最適なもののうち,全体の公平さ(egalitarian)が最小の安定マッチングを求める問題を考える.我々は,この問題がNP困難であることを示し,この問題に対して近似度が2より良い多項式時間アルゴリズムを構築した.
著者
宮崎 修一
雑誌
情報処理
巻号頁・発行日
vol.54, no.10, pp.1064-1071, 2013-09-15
著者
津崎 善晴 松本 亮介 小谷 大祐 宮崎 修一 岡部 寿男
雑誌
研究報告インターネットと運用技術(IOT)
巻号頁・発行日
vol.2014-IOT-24, no.11, pp.1-6, 2014-02-20

電子メールが広く普及し,メールが宛先に遅延なく配送されることが望まれてきている.意図しない大量メールが短時間にメール中継システムに送信されることは珍しくない.これらのメールはしばしば,システムの負荷を超過させ,ネットワーク帯域を占有する原因となり,このような状況ではメール配送に重大な遅延をもたらす.本稿ではハシシュテーブルで管理されたエンベロープ From アドレスとエンベロープ To アドレスの組を用いて効率的に大量のメールを検知するメール中継システムを提案する.提案システムではエンベロープ From アドレスとエンベロープ To アドレスの組数を数え,もし,ある短い期間で特定の組の配送数が事前に設定した閾値を超えた場合,これらのペアが大量メールの原因とみなす.エンベロープ From アドレスとエンベロープ To アドレスを管理するハッシュテーブルの肥大化を低減するために複数のハッシュテーブルを使用し,これらのハッシュテーブルを時間毎に分け,ある決まった間隔でエントリーを空にする.また,事前に大量のメールの判断するためにブロックリストも準備する.最終的にシステムを実装し評価する.
著者
畠山貴行 宮崎修一
雑誌
2014年度 情報処理学会関西支部 支部大会 講演論文集
巻号頁・発行日
vol.2014, 2014-09-10

ネットワーク通信を用いたサーバのないブラックジャックゲームに対して、マジックプロトコルを利用することで相手のプレイヤーが信頼できなくても公平なゲームを行うことができる通信プロトコルを設計し実装した。
著者
三宅 美行 宮崎 修一 辻 明良 金子 康子 山口 恵三 五島 瑳智子
出版者
公益社団法人 日本化学療法学会
雑誌
CHEMOTHERAPY (ISSN:00093165)
巻号頁・発行日
vol.42, no.Supplement2, pp.34-50, 1994-10-24 (Released:2011-08-04)
参考文献数
17

新しいβ-ラクタマーゼ阻害剤tazobactam (TAZ) とpiperacillin (PIPC) との1: 4の配合剤で あるtazobactam/piperacillin (TAZ/PIPC) のin vitroおよびin vivoにおける抗菌力を既存のβ-ラクタム系抗生物質と比較検討した。TAZ/PIPCはグラム陽性菌および陰性菌に対して幅広い抗菌スペクトルを示し, 陽性菌 では対照薬剤のなかで最も強く, 陰性菌においてもimipenem, ceftazidimeにつぐ強い抗菌 力を示した。特にβ-ラクタマーゼ産生株では配合相手であるPIPCよりも強い抗菌力を示 した。マウス全身感染治療実験において TAZ/PIPCは試験株のすべてに優れた治療効果を認 め, とくにβ-ラクタマーゼ産生株の感染ではPIPCよりも優れた治療効果を示した。また, TAZ/PIPCのβ-ラクタマーゼ非産生株単独感染での治療効果はPIPCとほぼ同様であったが, 産生株との混合感染においては明らかにPIPCより優れていた。β-ラクタマーゼ産生株であるEscherichia coli KU-3によるマウス尿路感染治療実験で, TAZ/PIPC投与マウスは PIPC投与マウスに比較して速やかな腎内生菌数の減少が観察された。また, 同様の方法にて尿路感染時の腎内PIPC濃度を測定したところ, PIPC投与群ではβ-ラクタマーゼによる分解を受けPIPC濃度はTAZ/PIPC投与群より有意に低下していたが, TAZ/PIPC投与群は正常マウスとほぼ同様であり, 分解を受けなかった。さらに, 臨床治療時を想定したヒト血中濃度シミュレーションシステムを用いてTAZ/PIPCの殺菌効果をβ-ラクタマーゼ産生株についてPIPCと比較したところ, TAZ/PIPCは PIPCより著明な生菌数の減少と再増殖の遅延が認められた。またE. coliとKlebsiella Pneumoniaeの混合接種においてもTAZ/PIPCはPIPCと比べ両菌に対し著明な殺菌作用が認められた。混合感染などβ-ラクタマーゼ産生株による感染治療においてTAZ/PIPCが優れた治療効果を示したのは, 感染部位に産生されたβ-ラクタマーゼによるPIPCの分解をTAZが阻害するためPIPC本来の抗菌力が発揮されたことによると考えられた。
著者
宮崎 修一 岩間 一雄
雑誌
全国大会講演論文集
巻号頁・発行日
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.110, no.325, pp.45-51, 2010-11-26

座席予約問題では駅s_1から駅s_kまでのk駅に停まるn席の座席を持った列車を考える.各乗客は出発駅s_iから到着駅s_j(1≦i≦j≦k)までのチケットを要求する.オンラインアルゴリズムは,未来の要求を知らずに各乗客をn席の座席の1つに割り当てる必要がある.座席予約問題の目的はチケットの売上合計額を最大化することである.チケットの価格設定により,座席予約問題には2つのモデルがある.一つは単一価格問題であり,もう一つは比例価格問題である.我々は,両方のモデルにおいて,競合比の上下限を改良した.単一価格問題に関しては,上限を8/(k+5)から4/(k-2√<k-1>+4)に改良した.また,Worst-Fitアルゴリズムの上限も4/(k-1)から2/(k-2√<k-1>+2)に改良した.さらに,比例価格問題に関しては,上限を(4+2√<13>)/(k+3+2√<13>)((&sime;11.2/(k+10.2))から(3+√<13>)/(k-1+√<13>)((&sime;6.6/(k+2.6))に改良し,下限を1/(k-1)から2/(k-1)に改良した.
著者
宮崎 修一
出版者
京都大学
雑誌
若手研究(B)
巻号頁・発行日
2008

安定マッチング問題とは、各男性が女性を、同様に各女性が男性を順序付けした希望リストを提出し、それに基づき「安定性」と呼ばれる性質を持つマッチングを求める問題である。本問題は、研修医の病院配属をはじめ、様々な配属問題に利用されている。本研究では、応用を視野に入れた本問題の様々なバリエーションを提案し、それらに対するアルゴリズムの開発や計算困難性・近似困難性の証明を行なった。
著者
朝廣 雄一 宮野 英次 宮崎 修一 吉牟田 拓朗
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
巻号頁・発行日
vol.106, no.405, pp.15-22, 2006-11-27

グラフ上での地図作成問題とは,探索者が未知のグラフの全ての頂点を訪問することによりグラフ構造を調査する問題である.探索者は辺の存在とその長さをその端点を訪れるまで判らないとする.探索者は,できるだけ短い経路を通ることにより全ての頂点と辺を調査して,出発点まで戻って来なければならない.本問題に対する最も単純な方法の一つは,最近傍アルゴリズム(NN)であり,まだ訪れていない頂点の中で探索者の現在の場所から最も近い場所に移動する戦略である.重み付き最近傍アルゴリズム(WNN)は,NNの拡張であり,ある重み付きの距離により次の移動場所を決める.平面グラフにおいては,重み3であるWNNが16競合であることが知られている.本稿ではサイクルグラフについては,NNの競合比が1.5となること,その解析が厳密であることを示す.また,サイクルグラフに対してはWNNの中でNNが最適であることを示す.さらに,本問題に対しては,1.25競合よりも良いアルゴリズムが存在しないことを示す.
著者
宮崎 修一
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会誌 (ISSN:09135693)
巻号頁・発行日
vol.88, no.3, pp.195-199, 2005-03-01
被引用文献数
1

安定結婚問題は二部グラフにおけるマッチング問題の一種である.複数の男女がおり, 各人は異性を自分の好みで順序付けした希望リストを持っている.その希望リストに基づいて「安定性」を満たすマッチング(結婚)を求めるのが, 安定結婚問題である.この問題は, アメリカの研修医配属への応用が有名であるが, 近年日本の研修医配属でも利用され始めた.本稿では, 安定結婚問題の基本的性質や応用例を紹介する.
著者
岡部 寿男 宮崎 修一 廣瀬 勝一
出版者
京都大学
雑誌
萌芽研究
巻号頁・発行日
2005

物理的に離れた場所にいるプレイヤがネットワーク上で対戦ゲームを行う環境構築の基盤を作ることが本研究の目標である。信頼できるサーバを用意することにより容易に実現できるが、サーバ自身の不正やサーバの負荷を考え、サーバなしのいわゆるpeer-to-peer型の環境を対象とする。そのような条件下で、対戦相手の不正を如何に防御するかを考察するのが、本研究の目的である。これまでの研究において、順序機械を用いてゲームを形式的に定義し、その定式化の汎用性を示すとともに、具体的ゲーム(軍人将棋)に対して計算量の削減を行いJaval.4を使って実装した。本年度は、その関連研究として、プライバシーを確保したまま二者間で情報をやりとりし、所望の計算結果(主に認証、認可)を得るためのプロトコルの研究を行った。本研究では、基盤となる認証体系としてShibbolethを仮定し、その上で「マジックプロトコル」と呼ばれる暗号技術を利用して所望のプロトコルを実現する方法を提案した。以下に例を2つ挙げる。例えば、年齢制限のあるWebコンテンツの閲覧の為には、利用者は制限年齢より上であることを証明すれば良く、自分の年齢そのものはできるだけ公開したくない。また、サービス提供側も、年齢制限がどこにあるのかを公開したくない場合がある。このような状況で、お互いに自分の秘密情報を公開しないまま、結果となる判定だけは正しく行いたいという要求が生じるが、これを、Yaoの金持ち比べプロトコル(2人の参加者が、自分の所持金を相手に知らせずに、どちらが金持ちかを正しく判定するプロトコル)を用いて解決した。また、例えば、会社の採用の条件として、大学時代に科目Aの単位を取得しているという条件を課している場合、会社はそれがどの科目であるかを明かさずに、また、大学側は、その科目A以外の単位取得状況は知らせずに、学生が科目Aの単位を取得しているか否かのみを、会社が知るという要求が考えられる。この問題は、紛失通信というプロトコルを応用することにより解決した。
著者
滝沢 茂 大槻 憲四郎 宮崎 修一 田中 秀実 西川 修 松井 智彰 八田 珠朗 興野 純 小澤 佳奈
出版者
筑波大学
雑誌
基盤研究(A)
巻号頁・発行日
2008

地震断層を引き起こした地殻の歪みエネルギーは主に粉砕粒子の非晶質化に費やされると予測して、粉砕粒子内の非晶質化を示し溶解熱測定を行った。この溶解熱測定はフッカ水素酸液用の試料カプセの開発に成功した。このカプセルは国内外を通じて例がない。特殊なカプセルで溶解熱を測定した結果、石英結晶をアモルファス化するのに要した熱量は約2000J/gであり、これをエネルギー量に換算すると1011ergオーダーとなる。この新知見に基づくと地震断層時の破壊エネルギーは表面エネルギー、すべり摩擦熱エネルギーおよび波動エネルギーとして分配され、主に消費されるエネルギーはすべり摩擦熱エネルギーと波動エネルギーと考えらているが、本研究課題の結論は最も消費エネルギーの大きいのは、結晶内消費エネルギーで、この事は新知見で物質地震学の新展開となる。