研究者業績
  1. 研究者検索結果一覧
  2. 宮崎 修一

宮崎 修一

ミヤザキ シュウイチ  (Shuichi Miyazaki)

基本情報

所属
兵庫県立大学 情報科学研究科 教授
学位
博士(工学)(九州大学)
J-GLOBAL ID
200901042786776786
researchmap会員ID
1000259772
外部リンク

研究キーワード

 5

研究分野

 2

経歴

 4

学歴

 3

受賞

 3

論文

 42
  • Tsubasa Harada, Toshiya Itoh, Shuichi Miyazaki
    Discrete Mathematics, Algorithms and Applications 16(05) 2350057-1-2350057-39 2024年7月  査読有り
    In the online facility assignment problem [Formula: see text], there exist [Formula: see text] servers [Formula: see text] on a metric space where each [Formula: see text] has an integer capacity [Formula: see text] and a request arrives one-by-one. The task of an online algorithm is to irrevocably match a current request with one of the servers with vacancies before the next request arrives. As special cases for [Formula: see text], we consider [Formula: see text] on a line , which is denoted by [Formula: see text] and [Formula: see text], where the latter is the case of [Formula: see text] with equidistant servers. In this paper, we perform the competitive analysis for the above problems. As a natural generalization of the greedy algorithm grdy, we introduce a class of algorithms called MPFS (Most Preferred Free Servers) and show that any MPFS algorithm has the capacity-insensitive property, i.e., for any MPFS algorithm alg for [Formula: see text], if alg is [Formula: see text]-competitive when [Formula: see text], then alg is [Formula: see text]-competitive for general [Formula: see text]. By applying the capacity-insensitive property of the greedy algorithm grdy, we derive the matching upper and lower bounds [Formula: see text] on the competitive ratio of grdy for [Formula: see text]. To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm alg for [Formula: see text] is at least [Formula: see text]. Then, we propose a new MPFS algorithm idas (Interior Division for Adjacent Servers) for [Formula: see text] and show that the competitive ratio of idas for [Formula: see text] is at most [Formula: see text], i.e., idas for [Formula: see text] is best possible in all the MPFS algorithms. We also give numerical experiments to investigate the performance of idas and grdy and show that idas performs better than grdy for distribution of request sequences with locality.
  • Koki Hamada, Shuichi Miyazaki
    Theoretical Computer Science 989 114389-1-114389-18 2024年3月  査読有り
  • Kazuo Iwama, Shuichi Miyazaki
    International Journal of Foundations of Computer Science 34(07) 853-873 2023年6月30日  査読有り
    This paper has two objectives. One is to give a linear time algorithm that solves the stable roommates problem (i.e., obtains one stable matching) using the stable marriage problem. The idea is that a stable matching of a roommate instance [Formula: see text] is a stable matching (that however must satisfy a certain condition) of some marriage instance [Formula: see text]. [Formula: see text] is obtained just by making two copies of [Formula: see text], one for the men’s table and the other for the women’s table. The second objective is to investigate the possibility of reducing the roommate problem to the marriage problem (with one-to-one correspondence between their stable matchings) in polynomial time. For a given [Formula: see text], we construct the rotation POSET [Formula: see text] of [Formula: see text] and then we “halve” it to obtain [Formula: see text], by which we can forget the above condition and can use all the closed subsets of [Formula: see text] for all the stable matchings of [Formula: see text]. Unfortunately this approach works (runs in polynomial time) only for restricted instances.
  • Toshiya Itoh, Shuichi Miyazaki, Makoto Satake
    Discrete Mathematics, Algorithms and Applications 13(06) 2021年12月  査読有り
    In the online metric matching problem, there are servers on a given metric space and requests are given one-by-one. The task of an online algorithm is to match each request immediately and irrevocably with one of the unused servers. In this paper, we pursue competitive analysis for two variants of the online metric matching problem. The first variant is a restriction where each server is placed at one of two positions, which is denoted by OMM([Formula: see text]). We show that a simple greedy algorithm achieves the competitive ratio of 3 for OMM([Formula: see text]). We also show that this greedy algorithm is optimal by showing that the competitive ratio of any deterministic online algorithm for OMM([Formula: see text]) is at least 3. The second variant is the online facility assignment problem on a line. In this problem, the metric space is a line, the servers have capacities, and the distances between any two consecutive servers are the same. We denote this problem by OFAL([Formula: see text]), where [Formula: see text] is the number of servers. We first observe that the upper and lower bounds for OMM([Formula: see text]) also hold for OFAL([Formula: see text]), so the competitive ratio for OFAL([Formula: see text]) is exactly 3. We then show lower bounds on the competitive ratio [Formula: see text] [Formula: see text], [Formula: see text] [Formula: see text] and [Formula: see text] [Formula: see text] for OFAL([Formula: see text]), OFAL([Formula: see text]) and OFAL([Formula: see text]), respectively.
  • Koki Hamada, Shuichi Miyazaki, Kazuya Okamoto
    Algorithmica 83(9) 2678-2696 2021年9月  査読有り責任著者
もっとみる

MISC

 110
  • 山内 直哉, 宮崎 修一, 岩間 一雄
    電子情報通信学会技術研究報告. COMP, コンピュテーション 106(405) 49-56 2006年11月  
    安定結婚問題において,同順位リストと不完全リストの存在を許した問題に対して最大サイズの安定マッチングを見つける問題を考える.この間題はNP困難であり,現在知られている中で最も良い近似アルゴリズムは,(2-c1/√<N>)-近似アルゴリズムである.(ここで,cはc≦1/4√<6>を満たす正定数であり,Nは入力中の男性の数である.)本論文では,この近似度を1.875に改良した.
  • 清成悠貴, 宮野英次, 宮崎修一
    電子情報通信学会技術研究報告 106(128(COMP2006 17-24)) 7-14 2006年6月16日  
    本稿では,試問予定表作成問題と呼ばれる大学における時間割表作成問題を考える.この問題では,m人の審査員の集合,2n人の学生の集合,各学生について審査する複数の審査員の担当割当(例えば各学生を3人ずつの審査員が担当)が与えられる.審査はn人ずつ2つの部屋で同時に行われるため,学生と担当審査員の組は,n個の時刻と2つの部屋から成るn×2行列に割り当てられる必要がある.ここで,同じ審査員が担当する異なる2人の学生は異なる時刻に割り当てられなければならない.さらに,すべての審査員が2つの部屋を移動する回数の合計をできるだけ少なくしたい.本問題は,実際に京都大学の試問予定表作成時に起きた問題を形式化したものである.この問題について2つの制約付きモデルを提案し,それらの計算複雑さについて調査する.
  • 小林 浩二, 宮崎 修一, 岡部 寿男
    数理解析研究所講究録 1489 91-97 2006年5月  
  • 宮崎修一
    電子情報通信学会誌 89(4) 299-303 2006年4月1日  
    ネットワーク上でふくそうが起った際に, ルータは到着するパケットをすべて処理しきれない場合がある.このとき, パケットの取捨選択やバッファの管理をいかに行うかが, QoS (Quality of Service)保証においては重要となる.近年, この間題をオンライン問題として定式化し, オンラインアルゴリズムの競合比解析を行う研究が盛んに行われている.本稿ではこれらの結果を紹介する.
  • 吉牟田拓朗, 宮野英次, 宮崎修一
    平成18 年 度第59 回電気関係学会九州支部連合大会10-2A-07, 2006-9 2006年  
  • 小林浩二, 宮崎修一, 岡部寿男
    2005 年度冬のLA シンポジウム, [14], 2006-1. 2006年  
  • Kiyonari, Y, Miyano, E, Miyazaki, S
    Proc. of The 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2006). pp. 448-453, August 2006. 2006年  査読有り
  • 宮崎修一, 久保浩史, 高見好男, 四方敏明, 櫻井恒正, 山元伸幸, 河野典, 江原康生, 高倉弘喜, 沢田篤史, 中村素典, 岡部寿男, 北野正雄
    全国共同利用情報基盤センター研究開発論文集 (27) 47-51 2005年10月  
  • 小林浩二, 宮崎修一, 岡部寿男
    電子情報通信学会技術研究報告 105(144(COMP2005 18-27)) 17-22 2005年6月17日  
    オンラインバッファ管理問題は, 近年のネットワーク運用における主要な論点となっているQoS (Quality of Service)保証実現のための, スイッチなどのキュー管理をオンライン問題として定式化した問題であり, 様々なモデルが考案されている.本論文ではその中の1つである共有メモリ型スイッチを扱ったモデルを取り上げる.我々は, アルゴリズムLongest Queue Policy (LQD)の競合比の既知の上限を2-1/Nに改良した.ここで, Nはスイッチの出力ポート数である.
  • 山内直哉, 宮崎修一, 岩間一雄
    電子情報通信学会技術研究報告 105(72(COMP2005 9-17)) 45-51 2005年5月13日  
    安定結婚問題において, 同順位リストと不完全リストの存在を許した問題に対して最大サイズの安定マッチングを見つける問題を考える.この問題はNP困難であり, 現在知られている最良の近似アルゴリズムは, (2-c (logN)/N)-近似アルゴリズムである.(ここで, cは任意の正定数であり, Nは入力中の男性の数である.)本論文では, この近似度を2-c 1/(N^<2/3>)に改良した.(cはc≦1/(2(√^3<6>)))を満たす正定数である.
  • 宮崎 修一
    電子情報通信学会誌 88(3) 195-199 2005年3月1日  
    安定結婚問題は二部グラフにおけるマッチング問題の一種である.複数の男女がおり, 各人は異性を自分の好みで順序付けした希望リストを持っている.その希望リストに基づいて「安定性」を満たすマッチング(結婚)を求めるのが, 安定結婚問題である.この問題は, アメリカの研修医配属への応用が有名であるが, 近年日本の研修医配属でも利用され始めた.本稿では, 安定結婚問題の基本的性質や応用例を紹介する.
  • 岡本和也, 宮崎修一, 岩間一雄
    電子情報通信学会技術研究報告 104(16(COMP2004 1-8)) 53-60 2004年4月22日  
    安定結婚問題の例題では、各個人の希望リストは異性全員を含み、完全に順位付けされている必要がある。しかし、実世界での応用を考えると、ペアになりたくない相手は希望リストに書かない不完全リストや、好みが同じ程度の人は優劣をつけなくて良い同順位リストという2つの自然な拡張が考えられる。どちらか一方の拡張のみを許した問題は多項式時間で解くことができるが、両方の拡張を許した場合、最大サイズの安定マツチングを見つける問題はNP困難になることが知られている。任意の2つの安定マッチングのサイズは最大でも2倍しか異ならないということは簡単にわかるため、近似度が2の近似アルゴリズムは自明である。2よりも良い近似度を実現する近似アルゴリズムを与える結果はいくつか知られているが、それらは、例えば同順位の長さや出現数などの制限を加えられた下でのものだけである。現在まで一般的な入力に対し、近似度が2未満となる近似アルゴリズムは知られていない。本論文では、一般的な例題に対し、近似度が2未満となる非自明な結果を初めて示した。我々のアルゴリズムの近似度は2-c(log N)/Nである。(ここで、cは任意の正定数で、Nは入力中の男性の数である。)
  • 岡本 和也, 宮崎 修一, 岩間 一雄
    電子情報通信学会総合大会講演論文集 2004(1) 2-2 2004年3月8日  
  • 岡本和也, 宮崎修一, 岩間一雄
    電子情報通信学会大会講演論文集 2004 2 2004年3月8日  
  • 加藤俊策, 宮崎修一, 岡部寿男
    電子情報通信学会技術研究報告 103(499(ISEC2003 84-95)) 1-6 2003年12月15日  
    対戦ゲームをネットワーク上で実現する場合、相手が物理的に見えないため、不正の排除が深刻な問題となる。最も簡単な解決方法は、信頼できる第三者的な審判サーバを用意することであるが、ネットワーク社会では自分以外を全く信用できないというのは自然な仮定であるため、サーバを利用せずプレーヤー同士が情報を交換し合うことでゲームを進行する方式が重要となる。この際に考えられる不正は、例えばトランプでシャッフルの結果を自分に都合の良いように操作することや、山に伏せられているカードの内容を覗き見ることなどが挙げられるが、公関鍵暗号技術を用いたプロトコルを用いることにより解決されている。本研究では軍人将棋を取り上げ、ゲーム進行に対して必要なプロトコルを関発し実装することを目標としている。軍人将棋では、例えば駒がぶつかった際に、相手の駒の種類を知らないままに勝ち負けだけを判定するという技術が必要となり、上記のトランプに対する技術だけでは自明に解決できない。本稿では、これらのプロトコルを提案し、実装の概要について述べる。
  • 江原 康生, 高倉 弘喜, 宮崎 修一
    シンポジウム報告集 (1) 20-26 2003年3月  
  • 宮崎 修一
    分散システム／インターネット運用技術シンポジウム2003,pp.19-24 2003年  
  • 柳沢弘揮, 宮崎修一, 岩間一雄, HALLDORSSON M
    電子情報通信学会技術研究報告 102(522(COMP2002 53-61)) 41-47 2002年12月19日  
    安定結婚問題とは,提出された希望リストに基づき,ある安定条件を満たすマッチングを求める問題である.従来の安定結婚問題では,希望リストに異性全員を全順序で記述する必要があった.タイ(同順位)を含んだ希望リストや不完全な希望リストを許すと,最大サイズの安定マッチジグを求める問題はNP困難になる.この問題に対する2-近似アルゴリズムは容易に作ることができるが,近似度が2よりも小さいアルゴリズムは知られていない.本研究では,タイの長さを2に制限した比較的自然な例題集合に対して,近似度が25/13(<1.924)の近似アルゴリズムを与えた.
  • 柳沢弘揮, 宮崎修一, 岩間一雄, HALLDORSSON M
    情報科学技術フォーラム FIT 2002 13-14 2002年9月13日  査読有り
  • 柳澤 弘揮, 宮崎 修一, 岩間 一雄, ハルダースソン マグナス
    情報技術レターズ 1 13-14 2002年9月  
  • 宮武和史, 宮崎修一, 岩間一雄
    電子情報通信学会大会講演論文集 2001(1) 4-4 2001年3月7日  
  • 宮崎 修一
    2001年夏のLAシンポジュム予稿（LAシンポジュウム）,/,4.1-4.11 2001年  
  • 宮崎 修一
    電子情報通信学会総合大会,D-1-4/, 2001年  
  • Halldorsson, M. M, Iwama, K, Miyazaki, S, Morita, Y
    Proc. KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2001),/,59-66 2001年  
  • 武富史郎, 宮崎修一, 岩間一雄, HALLDORSSON M M
    電子情報通信学会技術研究報告 100(25(COMP2000 1-5)) 25-32 2000年4月26日  
    オンライン独立頂点集合問題とは各時点で1つの頂点V_iと, V_iに接続する枝が与えられ, その頂点を独立頂点集合に入れるか否かを決定し, 最終的にできるだけ大きなサイズの独立頂点集合を得ることを目的とする問題である.従来の設定のように解を1つしか持つことを許さないモデルを用いた場合には, グラフの総頂点数をnとして, 競合比の上下限はn-1となる.本研究では同時に多項式個の解を保持することを許したモデルを2つ考案し, それぞれの競合比の上限と下限を与えた.
  • 盛田 保文, 宮崎 修一, 岩間 一雄, ハルダースソン マグナス
    数理解析研究所講究録 1148 124-129 2000年4月  
  • 梅本 潤, 宮崎 修一, 岡部 寿男, 岩間 一雄
    情報処理学会研究報告. [ハイパフォーマンスコンピューティング] 2000(23) 95-100 2000年3月2日  
    充足可能性問題(SAT)は基本的な組み合わせ問題である．高速なSATの解法アルゴリズムとして局所探索法があるが，大規模な問題にも対応するため更なる高速化の重要性が高まっている．そこで，本稿では局所探索法をネットワーク並列計算用ソフトウェアシステムであるPVM(Parallel Virtual Machine)で並列化して実行する高速化手法を提案する．局所探索法のTRYという実行単位を各計算機で並列に実行するTRY同時実行により，効率的に高速化できることを示した．さらに，2nd DIMACS Implementation Challengeのsatisfiabilityのベンチマークに対して計算機実験を行い，これまで解かれていなかった例題をワークステーション70台を用いて8 500秒程で解くことができた．The Satisfiability Problem(SAT) is one of the most fundamental combinatorial problems. The local search algorithm, which was developed recently, is probably the most popular SAT algorithm because of its surprising efficiency. The purpose of this paper is to speed up local search using PVM(Parallel Virtual Machine), which is the software system designed for networked parallel computing. We show that the local search algorithm can be efficiantly speeded up by the method 'TRY simultaneous execution'. The method executes TRYs, the unit process of the local search, on several computers in parallel, Furthermore, we show experimental results using benchmarks of 2nd DIMACS Implemaentation Challenge. In this experiment, we were able to solve an instance, which has not been solved by other programs, in about 8,500 seconds using 70 workstations.
  • 河合大輔, 宮崎修一, 岡部寿男, 岩間一雄
    電子情報通信学会技術研究報告 99(549(COMP99 69-78)) 49-56 2000年1月19日  
    充足可能性問題(SAT)は基本的な組合せ問題である.高速なSATの解法アルゴリズムとして局所探索法があるが, 変数数・項数が膨大になると実用的時間で解くのは困難となる.ゆえに, 局所探索法の高速化の重要性が高まっている.本稿では, 局所探索法をベクトル並列計算機でベクトル化して実行する高速化手法を提案する.ベクトル化の際に発生する様々な問題を解決し, その有効性を検証した.さらに, 2nd DIMACS Implementation ChallengeのSatisfiabilityのベンチマークに対して計算機実験を行い, その実用性を示した.
  • Iwama, K, Kawai, D, Miyazaki, S, Okabe, Y, Umemoto, J
    Proc. The AAAI-2000 workshop on parallel and distributed search for reasoning, 2000年  
  • 宮崎 修一
    並列処理シンポジウム(JSPP2000),/,43-50 2000年  査読有り
  • 宮崎 修一
    第60回(平成12年後期)情処全国大会講演論文集,1/,193 2000年  
  • 宮崎 修一
    第60回(平成12年後期)情処全国大会講演論文集,/,199 2000年  
  • 宮崎 修一
    京都大学数理解析研究所講究録「計算機科学の基礎理論:21世紀の計算パラダイムを目指して」,/,124-129 2000年  
  • 宮崎 修一
    第60回(平成12年後期)情処全国大会講演論文集,/,177 2000年  
  • 宮崎 修一, 岩間 一雄
    数理解析研究所講究録 1120 51-57 1999年12月  
  • MIYAZAKI S, IWAMA K
    電子情報通信学会技術研究報告 99(288(COMP99 31-38)) 15-22 1999年9月3日  
  • UCHIDA A, MIYAZAKI S, IWAMA K
    電子情報通信学会技術研究報告 99(30(COMP99 1-9)) 57-64 1999年4月23日  
    本稿ではOnline MWSAT, Online MWISという2つのオンライン問題を導入し, これらの問題が以下の2つの意味で最も困難なオンライン問題であることを示す. (i)これらの問題は, 任意のオンライン問題を模倣可能である. (ii)これらの問題は, より強力なオンラインアルゴリズム(複数の解を同時に保持することを許されたオンラインアルゴリズム)によっても, 最悪の競合比しか得られない. 証明には, NP最適化問題の完全性の証明を利用した. 即ち, オンライン問題を非決定性チューリング機械で定式化し, それをOnline MWSATが模倣可能であることを示した.
  • 盛田 保文, 宮崎 修一, 岩間 一雄
    情報処理学会研究報告. AL, アルゴリズム研究会報告 99(26) 15-22 1999年3月15日  
    安定結婚問題とは，N人ずつの男女と各個人が異性に対する好みの順を書いた希望リストが与えられたときに7安定なN組のペアを求める問題である．本問題に対しては多項式時間アルゴリズムが存在することが知られている．また，この問題の希望リストに対する条件の緩和として，異性全員を書かなくてもよい場合や，異性の希望順位に同順位を許す場合などが考えられるが，これらの緩和を単独で用いた場合にも，解の存在を判定する多項式時間アルゴリズムが知られている．本稿ではこれらの緩和を同時に行った場合に問題がNP完全になることを示す．また，本問題にコストを導入した最適化問題に対して，近似度の良いアルゴリズムが存在しないことを示す．An instance of the original stable marriage problem consists of N men and N women. Each person submits a preference list in which he/she writes all the members of the opposite sex in the strict order. The problem is known to be solved in polynomial time. Considering practical applications, two natural relaxations for the preference lists have been introduced. One is to allow the list to be incomplete, namely, one can exclude persons whom he/she does not want to accept. The other one is to allow the list including ties. Each of these relaxations does not make the problem complicated, i.e.，both problems are still in the class P. In this paper, we show that the problem becomes NP-complete if both relaxations are allowed. We also show the inapproximability for the optimization version of the stable marriage.
  • 内田 敦, 宮崎 修一, 岩間 一雄
    全国大会講演論文集 58(1) "1-319"-"1-320" 1999年3月9日  
  • 内田 敦, 宮崎 修一, 岩間 一雄
    全国大会講演論文集 58(1) "1-319"-"1-320" 1999年3月9日  
  • Iwama, K, Miyazaki, S, Uchida, A
    Proc. Korea-Japan Joint Workshop on Algorithms and Computation,/,59-66 1999年  
  • MIYAZAKI S, IWAMA K
    電子情報通信学会技術研究報告 98(432(COMP98 51-62)) 33-40 1998年11月20日  
    安定結婚問題は, 入力としてN人ずつの男女と各個人の異性に対する希望リスト(異性N人の順序付け)が与えられ, 安定なN組のペアを求める(安定なN組のペアが存在するかどうかを問う)問題である.本問題の自然な拡張として, (i)希望リストに異性N人全員を書かなくても良いもの, (ii)希望の順序付けに半順序を許すもの, があるが, いずれも解の存在は多項式時間で判定できることが知られている.本研究では, (i)および(ii)を同時に許した場合に, 本問題がNP完全になることを示す.また, 本問題に関連した問題のNP完全性も示す.
  • 盛田 保文, 宮崎 修一, 岩間 一雄
    情報処理学会研究報告. データベース・システム研究会報告 98(58) 335-342 1998年7月9日  
  • 宮崎 修一
    情報基礎理論ワークショップ98,/,13-18 1998年  
  • 宮崎修一, 岩間一雄
    電子情報通信学会技術研究報告 97(375(COMP97 60-72)) 73-79 1997年11月14日  
    部分MAXSATは, MAXSATを一般化した組合せ最適化問題であり, スケジュール問題等の現実社会に則した組合せ最適化問題を模倣する能力を持っている. また, 部分MAXSATは, 項の重みづけを施すことにより, 従来のMAXSATアルゴリズムを用いて, 効率良く解けることが実験によって示されている. このように, 部分MAXSATは有用な問題であるが, どのような問題を模倣することができるかを理論的に明らかにする必要がある. 本論文では, 部分MAXSATの組合せ最適化問題のクラスでの完全性を示す. また, 他の組合せ最適化問題に対応する部分最適化問題の完全性も示す.
  • 宮崎 修一, 岩間 一雄
    全国大会講演論文集 55(1) 299-300 1997年9月24日  
    CNF論理式の充足可能性問題(SAT)は基本的な組合せ問題であり, 解法アルゴリズム, 例題生成アルゴリズム等の研究が盛んに行われている。しかし, SATを実用的時間で解くのは不可能であると考えられているため, 近年では, 実用時間でできるだけ多くの項を充足する解を見つける問題であるMAXSATの近似解法の研究も行われている。その中で, 特に局所探索法は最適に近い解を高速に見つけるとの報告もあり, 注目を集めている。これにより, 様々な組合せ最適化問題をMAXSATに変換し, MAXSATに対する高速アルゴリズムを利用して解くという方法を考えることができる。しかしFスケジュール問題等の現実社会に則した最適化問題を模倣するのにはMAXSATは不十分であり, MAXSATの一般化である部分MAXSATという問題が新たに提案された。部分MAXSATの例題は2つのCNF論理式f_Aおよびf_Bからなり, f_Aの項を全て充足させた上でf_Bの項をできるだけ充足する割当を求める問題である。部分MAXSATはMAXSATよりも一般性を有しているにも関わらず, 項に重み付けを施すことによって, 従来のMAXSATアルゴリズムを用いて, 十分に良い解を探索できるということが実験により分かった。このように, 部分MAXSATは様々な問題を模倣でき, 高速に良い解を求めることのできる問題であるが, どのような問題が部分MAXSATを利用して解けるかは明らかになっていない。本論文では, 部分MAXSATの最適化問題のクラスでの完全性を示し, あらゆる最適化問題を模倣可能であることを示す。最適化問題の完全性の議論は盛んに行なわれているが, 部分MAXSATのような, 「部分最適化問題」を取り扱った文献は見受けられない。また, MAXSATに対して部分MAXSATが存在するように, 他の最適化問題にも対応する部分最適化問題を考えることができる。本論文では, そのような部分最適化問題の完全性に関しても議論を行う。
  • 宮崎 修一, 岩間 一雄
    数理解析研究所講究録 950 240-245 1996年5月  
  • 宮崎 修一
    京都大学数理解析研究所講究録950 「計算モデルと計算の複雑さに関する研究」,/,240-245 1996年  
  • 宮崎 修一
    平成8年度 第49回電気関係学会九州支部連合大会講演論文集,/,674 1996年  
  • 宮崎 修一, 岩間 一雄
    電子情報通信学会総合大会講演論文集 1995(1) 8-8 1995年3月27日  
    NP完全問題の例題を生成することは、アルゴリズムを実験的に評価するために重要なことであり,数多くの研究がなされている.ここで重要なことは答えがYESである例題とNOである例題を独立に生成するこである.しかし,NOである例題の集合はco-NP完全に属するため,NP&bne;co-NPならば全ての例題を多項式時間で生成することはできない.そこで,co-NP完全集合の部分集合を生成するという手法が用いられている.この場合特に大切なことは生成された(部分)例題集合が(i)易しすぎないこと,(ii)元の集合にできるだけ近いことである.(ii)についてco-NP完全集合Aの部分集合であるNP完全集合Bに対して,そさよりも無限に多くの要素を持つNP完全集合B'(B'&supE;B)がある条件の下で存在することが証明されている.今回は別の条件下での証明を行なった.また,具体的にAとして非ハミルトングラフの集合が,Bとして非-1-toughグラフが与えられた時にB'を生成する方法を示す.

書籍等出版物

 10
もっとみる

講演・口頭発表等

 41
もっとみる

担当経験のある科目(授業)

 7
もっとみる

所属学協会

 4

共同研究・競争的資金等の研究課題

 21
もっとみる

社会貢献活動

 7
一覧へ戻る