研究者業績

宮崎 修一

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

基本情報

所属
兵庫県立大学 情報科学研究科 教授
学位
博士(工学)(九州大学)

J-GLOBAL ID
200901042786776786
researchmap会員ID
1000259772

外部リンク

論文

 45
  • 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
  • Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki
    CoRR abs/1904.05011 2019年  
  • 岡本和也, 宮崎修一
    2018年度情報処理学会関西支部支部大会 2018年9月  
  • 岡本 和也, 宮崎 修一
    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 117(301) 67-74 2017年11月16日  
  • 岡本 和也, 宮崎 修一
    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 117(300) 67-74 2017年11月16日  
  • リー アンドリュー, 宮崎 修一, 岡部 寿男
    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 114(494) 143-147 2015年3月5日  
    Given the same amount of hardware resource and bandwidth limitation, networks with optimal configurations enable Internet service providers to provide a lower end-to-end latency service for clients to use. In the case of designing VLAN, due to the lack of effective automation tool at present, most configurations are still done manually, hence it becomes hard to ensure the optimum of a designed network especially when the scale of the given network grows larger. In this paper, our goal is to construct an automated procedure for embedding multiple VLANs above the same physical network by first defining the performance criteria and then introducing the Minimum Diameter Multiple Steiner Tree problem as the model of this problem. We propose several greedy algorithms to solve the model problem as well as evaluating the performance results obtained by simulated data. Our result shows that an embedding order of higher bandwidth requirement first has a higher chance to reduce the latency sum of multiple VLANs in a full mesh network.

書籍等出版物

 10

講演・口頭発表等

 41

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

 7

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

 23

社会貢献活動

 7