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

宮崎 修一

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

基本情報

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

研究キーワード

 5

研究分野

 2

経歴

 4

学歴

 3

受賞

 3

論文

 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
  • Koki Hamada, Shuichi Miyazaki
    Proc. the 28th International Computing and Combinatorics Conference (COCOON 2022) 2022年10月
  • Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi
    Proc. the 15th International Symposium on Algorithmic Game Theory (SAGT 2022) 2022年9月
  • Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi
    39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) 2022年3月 Schloss Dagstuhl - Leibniz-Zentrum für Informatik
  • Toshiya Itoh, Shuichi Miyazaki, Makoto Satake
    Combinatorial Optimization and Applications (COCOA 2020) Lecture Notes in Computer Science book series (LNCS, volume 12577) 2020年12月 Springer International Publishing
  • Koki Hamada, Shuichi Miyazaki, Kazuya Okamoto
    Combinatorial Algorithms (IWOCA 2020). Lecture Notes in Computer Science, vol 12126 2020年 Springer International Publishing
  • Koki Hamada, Shuichi Miyazaki, Hiroki Yanagisawa
    30th International Symposium on Algorithms and Computation (ISAAC 2019), December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China. 2019年12月 Schloss Dagstuhl - Leibniz-Zentrum für Informatik
  • Yasuaki Kobayashi, Yusuke Kobayashi 0001, Shuichi Miyazaki, Suguru Tamaki
    Combinatorial Algorithms - 30th International Workshop (IWOCA 2019), Pisa, Italy, July 23-25, 2019, Proceedings 2019年7月 Springer
  • Shuichi Miyazaki, Kazuya Okamoto
    28th International Symposium on Algorithms and Computation (ISAAC 2017), December 9-12, 2017, Phuket, Thailand 2017年12月 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
  • Yoshiyuki Mihara, Shuichi Miyazaki, Yasuo Okabe, Tetsuya Yamaguchi, Manabu Okamoto
    2017 14TH IEEE ANNUAL CONSUMER COMMUNICATIONS & NETWORKING CONFERENCE (CCNC 2017) 2017年 IEEE
    In this article, we propose a method to identify the link layer home network topology, motivated by applications to cost reduction of support centers. If the topology of home networks can be identified automatically and efficiently, it is easier for operators of support centers to identify fault points. We use MAC address forwarding tables (AFTs) which can be collected from network devices via HTIP (ITU-T G.9973, Home network Topology Identifying Protocol). There are a couple of existing methods for identifying a network topology using AFTs, but they are insufficient for our purpose; they are not applicable to some specific network topologies that are typical in home networks. Our method proposed in this paper can handle such topologies. Furthermore, our method is faster because, for detecting a leaf node at each round, the existing methods use a result of set inclusion operations, while our method only needs to check the sizes of sets, which is much less costly. We also give experimental evaluations to show the advantages of our method.
  • Sushmita Gupta, Kazuo Iwama, Shuichi Miyazaki
    15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), June 22-24, 2016, Reykjavik, Iceland 2016年 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
  • Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa
    Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), August 24-26, 2015, Princeton, NJ, USA 2015年 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    The problem of finding a maximum cardinality stable matching in the presence of ties and unacceptable partners, called MAX SMTI, is a well-studied NP-hard problem. The MAX SMTI is NP-hard even for highly restricted instances where (i) ties appear only in women's preference lists and (ii) each tie appears at the end of each woman's preference list. The current best lower bounds on the approximation ratio for this variant are 1.1052 unless P=NP and 1.25 under the unique games conjecture, while the current best upper bound is 1.4616. In this paper, we improve the upper bound to 1.25, which matches the lower bound under the unique games conjecture. Note that this is the first special case of the MAX SMTI where the tight approximation bound is obtained. The improved ratio is achieved via a new analysis technique, which avoids the complicated case-by-case analysis used in earlier studies. As a by-product of our analysis, we show that the integrality gap of natural IP and LP formulations for this variant is 1.25. We also show that the unrestricted MAX SMTI cannot be approximated with less than 1.5 unless the approximation ratio of a certain special case of the minimum maximal matching problem can be improved.
  • Shuichi Miyazaki, Naoyuki Morimoto, Yasuo Okabe
    ALGORITHMS AND COMPLEXITY (CIAC 2015) 2015年 SPRINGER-VERLAG BERLIN
    This paper considers two variants of Multiple Knapsack Problems. The first one is the Multiple Knapsack Problem with Assignment Restrictions and Capacity Constraints (MK-AR-CC). In the MK-AR-CC(k) (where k is a positive integer), a subset of knapsacks is associated with each item and the item can be packed into only those knapsacks (Assignment Restrictions). Furthermore, the size of each knapsack is at least k times the largest item assignable to the knapsack (Capacity Constraints). The MK-AR-CC(k) is NP-hard for any constant k. In this paper, we give a polynomial-time (1 + 2/k+1 + epsilon)-approximation algorithm for the MK-AR-CC(k), and give a lower bound on the approximation ratio of our algorithm by showing an integrality gap of (1 + 1/k - epsilon) for the IP formulation we use in our algorithm, where epsilon is an arbitrary small positive constant. The second problem is the Splittable Multiple Knapsack Problem with Assignment Restrictions (S-MK-AR), in which the size of items may exceed the capacity of knapsacks and items can be split and packed into multiple knapsacks. We show that approximating the S-MK-AR with the ratio of n(1-epsilon) is NP-hard even when all the items have the same profit, where n is the number of items and epsilon is an arbitrary positive constant.
  • 24th International Symposium on Algorithms and Computation (ISAAC 2013) 2013年
  • Satoshi Ishibashi, Shuichi Miyazaki, Yasuo Okabe
    Proceedings - 11th IEEE/IPSJ International Symposium on Applications and the Internet (SAINT 2011) 2011年
    In this paper, we propose an online document delivery system which enables the sender to claim that documents are certainly delivered to the receiver. It is not difficult to realize this property by using a Trusted Third Party (TTP), but we focus on systems without TTP, considering a practical use. Our assumption is only the Public Key Infrastructure (PKI). Our work is based on the work by Shimizu et al., in which they applied the so-called ''gradual secret exchange protocol'' and implemented an e-mail exchange system using this protocol. The aim of this paper is to improve their system. We first point out that although the gradual secret exchange protocol is theoretically excellent, it is over-spec for our purpose. Hence we avoid using it and propose a simplified protocol, which has low computational cost. Using this protocol, we design a certified document delivery system based on the Half Agent Model proposed by Shimizu et al. Finally, we implement our protocol as a prototype system, and evaluate its performance. Experimental results show that our system runs efficiently with relatively small example documents, such as ones of size less than 30MB. © 2011 IEEE.
  • Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2011) 2011年 SPRINGER-VERLAG BERLIN
    Manlove and O'Malley [9] proposed the Student-Project Allocation Problem with Preferences over Projects (SPA-P). They proved that the problem of finding a maximum stable matching in SPA-P is APX-hard and gave a polynomial-time 2-approximation algorithm. In this paper, we give an improved upper bound of 1.5 and a lower bound of 21/19 (> 1.1052).
  • Koki Hamada, Kazuo Iwama, Shuichi Miyazaki
    ALGORITHMS (ESA 2011) 2011年 SPRINGER-VERLAG BERLIN
    The Hospitals/Residents problem is a many-to-one extension of the stable marriage problem. In its instance, each hospital specifies a quota, i.e., an upper bound on the number of positions it provides. It is well-known that in any instance, there exists at least one stable matching, and finding one can be done in polynomial time. In this paper, we consider an extension in which each hospital specifies not only an upper bound but also a lower bound on its number of positions. In this setting, there can be instances that admit no stable matching, but the problem of asking if there is a stable matching is solvable in polynomial time. In case there is no stable matching, we consider the problem of finding a matching that is "as stable as possible", namely, a matching with a minimum number of blocking pairs. We show that this problem is hard to approximate within the ratio of (vertical bar H vertical bar+vertical bar R vertical bar)(1-epsilon) for any positive constant epsilon where H and R are the sets of hospitals and residents, respectively. We tackle this hardness from two different angles. First, we give an exponential-time exact algorithm for a special case where all the upper bound quotas are one. This algorithm runs in time O(t(2)(vertical bar H vertical bar(vertical bar R vertical bar+t))(t+1)) for instances whose optimal cost is t. Second, we consider another measure for optimization criteria, i.e., the number of residents who are involved in blocking pairs. We show that this problem is still NP-hard but has a polynomial-time & root vertical bar R vertical bar-approximation algorithm.
  • Shuichi Miyazaki, Kazuya Okamoto
    THEORETICAL COMPUTER SCIENCE (IFIP TCS 2010) 2010年 SPRINGER-VERLAG BERLIN
    In the seat reservation problem, there are k stations, si through s(k), and one train with n seats departing from the station Si and arriving at the station s(k). Each passenger orders a ticket from station s(i) to station s(j) (1 <= i < j <= k) by specifying i and j. The task of an online algorithm is to assign one of n seats to each passenger online, i.e., without knowing future requests. The purpose of the problem is to maximize the total price of the sold tickets. There are two models, the unit price problem and the proportional price problem, depending on the pricing policy of tickets. In this paper, we improve upper and lower bounds on the competitive ratios for both models: For the unit price problem, we give an upper bound of 4/k-2 root k-1+4, which improves the previous bound of 8/k+5. We also give an upper bound of k 2/k-2 root k-1+2 for the competitive ratio of Worst-Fit algorithm, which improves the previous bound of 4/k-1. For the proportional price problem, we give upper and lower bounds of 3+root 13/k-1+root 13 (similar or equal to 6.6/k+2.6) and 2/k-1, respectively, on the competitive ratio, which improves the previous bounds of 4+2 root 13/k+3+2 root 13 and 1/k-1 respectively.
  • Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa
    ALGORITHMS (ESA 2010), PT II 2010年 SPRINGER-VERLAG BERLIN
    The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (> 1.1379) unless P=NP, and the current best approximation algorithm achieves the ratio of 1.5. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within 21/19 (> 1.1052) unless P=NP. However, even under this restriction, the best known approximation ratio is still 1.5. In this paper, we improve it to 25/17 (< 1.4706).
  • Keita Shimizu, Shuichi Miyazaki, Yasuo Okabe
    2009 9th Annual International Symposium on Applications and the Internet (SAINT 2009) 2009年 IEEE
    In this paper we design a certified e-mail exchange system based on a simultaneous secret exchange protocol. Among others, we use the protocol proposed by Okamoto and Ohta since the number of rounds it requires is relatively small compared to other similar protocols. We first modify the method of Okamoto and Ohta to further reduce the number of rounds without breaking the fairness condition too much. Next, we propose three different communication models considering the existence of MTAs (Mail Transfer Agents, e.g. SMTP Server) and MUAs (Mail User Agents). Then we adopt two models, which have several advantages; for example, they enable send-and-forget for the sender, or enable to exchange messages between the sender and the receiver directly, depending on the environment of the users. Finally, we design details of the system and implement it as a prototype.
  • Koji Kobayashi, Shuichi Miyazaki, Yasuo Okabe
    PROCEEDINGS OF THE TWENTY-FIRST ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA 2009) 2009年 ASSOC COMPUTING MACHINERY
    The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee. We focus on multi-queue switches in QoS networks proposed by Azar et al. To achieve good upper bounds, they introduced so-called "the relaxed model". Also, they showed that if the competitive ratio of the single-queue model is at most c, and if the competitive ratio of the relaxed model is at most e, then the competitive ratio of the multi-queue switch model is cc'. They proved that c' <= 2, and obtained upper bounds on the competitive ratios for several multi-queue switch models. In this paper, we propose an online algorithm called DS (Dual Scheduling) for the competitive ratio of the relaxed model and obtain some better competitive ratios of the 2-value multi-queue switch model, where the value of packets is restricted to 1 and alpha(>= 1). DS uses as subroutine any online algorithms A for the non-preemptive unit-value switch model, which has also been extensively studied. We prove that if the competitive ratio of A is at most c, the the competitive ratio of DS is at most alpha c(2-c)+c(2)-2c+2/alpha(2-c)+c-1, which is strictly better than 2. The followings are a couple of examples of the improvement on the competitive ratios of the 2-value multi-queue switch models using our result: (i) We have improved the competitive ratio of deterministic algorithms for the non-preemptive 2-value multi-queue switch model front 4 to 3.177 for large enough B, where B is the number of packets each queue can simultaneously store. (ii) We have proved that the competitive ratio of randomized algorithms for the non-preemptive 2-value multi-queue switch model is at most 17/2-root 30 similar or equal to for large enough B.
  • Toshihiro Takagi, Takaaki Komura, Shuichi Miyazaki, Yasuo Okabe
    Proceedings - 2008 International Symposium on Applications and the Internet (SAINT 2008) 2008年
    We propose an extension of the attribute exchange between an Identity Provider (IdP) and an Service Provider (SP) in Shibboleth. While in the conventional framework of Shibboleth attributes are exchanged in immediate values, in our new extension an SP and an IdP exchange attributes according to so-called "Magic Protocols". This extension enables the SP to know whether user's attributes meet the requirement for authorization, without the SP and the IdP revealing their confidential information. We also show how we can detect cheating in execution of this protocol, e.g. the IdP tells another value instead of the true value to the SP in malice. © 2008 IEEE.
  • Shuichi Miyazaki, Kazuya Okamoto
    ALGORITHMS AND COMPUTATION (ISAAC 2008) 2008年 SPRINGER-VERLAG BERLIN
    Online OVSF code assignment has an important application to wireless communications. Recently, this problem was formally modeled as an online problem, and performances of online algorithms have been analyzed by the competitive analysis. The previous best upper and lower bounds on the competitive ratio were 10 and 5/3, respectively. In this paper, we improve them to 7 and 2, respectively. We also show that our analysis for the tipper bound is tight by giving an input sequence for which the competitive ratio of our algorithm is 7 - epsilon for arbitrary epsilon > 0.
  • Kazuo Iwama, Shuichi Miyazaki
    INTERNATIONAL CONFERENCE ON INFORMATICS EDUCATION AND RESEARCH FOR KNOWLEDGE-CIRCULATING SOCIETY, PROCEEDINGS 2008年 IEEE COMPUTER SOC
    The stable marriage problem is to find a matching between men and women, considering preference lists in. which. each person expresses his/her preference over the members of the opposite gender. The output matching must be stable, which, intuitively means that there is no man-woman pair both. of which have incentive to elope. This problem was introduced in 1962 in the seminal paper of Gale and Shapley, and has attracted researchers in several areas, including mathematics, economics, game theory, computer science, etc. This paper introduces old and recent results on the stable marriage problem and some other related problems.
  • Shunsaku Kato, Shuichi Miyazaki, Yusuke Nishimura, Yasuo Okabe
    COMPUTERS AND GAMES (CG 2006) 2007年 SPRINGER-VERLAG BERLIN
    We consider playing online games on peer-to-peer networks, without assuming servers that control the execution of a game. In such an environment, players may cheat the opponent by, for example, illegally replacing the cards in their hands. The aim of this paper is to examine a possibility of excluding such cheatings. We show that by employing cryptographic techniques, we can exclude some types of cheating at some level. Finally, based on our discussion, we implement the cheat-proof network "Gunjin-Shogi", which is a variant of Japanese Chess.
  • Yuichi Asahiro, Eiji Miyano, Shuichi Miyazaki, Takuro Yoshimuta
    THEORY AND PRACTICE OF COMPUTER SCIENCE (SOFSEM 2007), PROCEEDINGS 2007年 SPRINGER-VERLAG BERLIN
    In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. The searcher is not aware of the existence of an edge until he/she visits one of its endpoints. The searcher's task is to visit all the nodes and go back to the starting node by traveling as a short tour as possible. One of the simplest strategies is the nearest neighbor algorithm (NN), which always chooses the unvisited node nearest to the searcher's current position. The weighted NN (WNN) is an extension of NN, which chooses the next node to visit by using the weighted distance. It is known that WNN with weight 3 is 16-competitive for planar graphs. In this paper we prove that NN achieves the competitive ratio of 1.5 for cycles. In addition, we show that the analysis for the competitive ratio of NN is tight by providing an instance for which the bound of 1.5 is attained, and NN is the best for cycles among WNN with all possible weights. Furthermore, we prove that no online algorithm is better than 1.25-competitive.
  • Koji Kobayashi, Shuichi Miyazaki, Yasuo Okabe
    PROCEEDINGS OF THE NINETEENTH ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA 2007) 2007年 ASSOC COMPUTING MACHINERY
    The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered. In this paper, we focus on shared memory switches with preemption. We prove that the competitive ratio of the Longest Queue Drop (LQD) policy is 4M-4/3M-2 in the case of N = 2, where N is the number of out put ports in a switch and M is the size of the buffer. This matches the lower bound given by Hahne, Kesselman and Mansour. Also, in the case of arbitrary N, we improve the competitive ratio of LQD from 2 to 2-1/M min k=1,2,..., N{left perpendicular M/K right perpendicular K - 1}.
  • Kazuo Iwama, Shuichi Miyazaki, Naoya Yamauchi
    PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2007) 2007年 SIAM
    We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed in preference lists. This problem is known to be APX-hard, and the current best known approximation algorithm achieves the approximation ratio 2 - c1/root N, where c is some positive constant. In this paper, we give a 1.875-approximation algorithm, which is the first result on the approximation ratio better than two.
  • Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa
    ALGORITHMS AND DATA STRUCTURES (WADS 2007), PROCEEDINGS 2007年 SPRINGER-VERLAG BERLIN
    The stable marriage problem is a classical matching problem introduced by Gale and Shapley. It is known that for any instance, there exists a solution, and there is a polynomial time algorithm to find one. However, the matching obtained by this algorithm is man-optimal, that is, the matching is preferable for men but unpreferable for women, (or, if we exchange the role of men and women, the resulting matching is woman-optimal). The sex-equal stable marriage problem posed by Gus-field and Irving asks to find a stable matching "fair" for both genders, namely it asks to find a stable matching with the property that the sum of the men's score is as close as possible to that of the women's. This problem is known to be strongly NP-hard. In this paper, we give a polynomial time algorithm for finding a near optimal solution in the sex-equal stable marriage problem. Furthermore, we consider the problem of optimizing additional criterion: among stable matchings that are near optimal in terms of the sex-equality, find a minimum egalitarian stable matching. We show that this problem is NP-hard, and give a polynomial time algorithm whose approximation ratio is less than two.
  • Kazuo Iwama, Shuichi Miyazaki, Naoya Yamauchi
    Algorithms and Computation (ISAAC 2005) 2005年 Springer Berlin Heidelberg
  • K Iwama, S Miyazaki, K Okamoto
    ALGORITHM THEORY (SWAT 2004) 2004年 SPRINGER-VERLAG BERLIN
    We propose an approximation algorithm for the problem of finding a maximum stable matching when both ties and unacceptable partners are allowed in preference lists. Our algorithm achieves the approximation ratio 2 - c (N)-(log N) for an arbitrarily positive constant c, where N denotes the number of men in an input. This improves the trivial approximation ratio of two.
  • M Halldorsson, K Iwama, S Miyazaki, H Yanagisawa
    COMPUTING AND COMBINATORICS (COCOON 2003), PROCEEDINGS 2003年 SPRINGER-VERLAG BERLIN
    While the original stable marriage problem requires all participants to rank all members of the opposite sex in a strict order, two natural variations are to allow for incomplete preference lists and ties in the preferences. Either variation is polynomially solvable, but it has recently been shown to be NP-hard to find a maximum cardinality stable matching when both of the variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. In this paper, we give a first nontrivial result for the approximation with factor less than two. Our randomized algorithm achieves a factor of 10/7 for a restricted but still NP-hard case, where ties occur in only men's lists, each man writes at most one tie, and the length of ties is two. Furthermore, we show that these restrictions except for the last one can be removed without increasing the approximation ratio too much.
  • MM Halldorsson, K Iwama, S Miyazaki, H Yanagisawa
    ALGORITHMS (ESA 2003), PROCEEDINGS 2003年 SPRINGER-VERLAG BERLIN
    The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially a factor two approximation. In this paper, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of 2/(1+L-2) for instances in which only men have ties of length at most L. When both men and women are allowed to have ties, we show a ratio of 13/7(< 1.858) for the case when ties are of length two. We also improve the lower bound on the approximation ratio to 21/19 (> 1.1052).
  • M Halldorsson, K Iwama, S Miyazaki, Y Morita
    THEORETICAL INFORMATICS (LATIN 2002) 2002年 SPRINGER-VERLAG BERLIN
    The stable marriage problem has received considerable attention both due to its practical applications as well as its mathematical structure. While the original problem has all participants rank all members of the opposite sex in a strict order of preference, two natural variations are to allow for incomplete preference lists and ties in the preferences. Both variations are polynomially solvable by a variation of the classical algorithm of Gale and Shapley. On the other hand, it has recently been shown to be NP-hard to find a maximum cardinality stable matching when both of the variations are allowed. We show here that it is APX-hard to approximate the maximum cardinality stable matching with incomplete lists and ties. This holds for some very restricted instances both in terms of lengths of preference lists, and lengths and occurrences of ties in the lists. We also obtain an optimal Omega(N) hardness results for 'minimum egalitarian' and 'minimum regret' variants.
  • Kazuo Iwama, Daisuke Kawai, Shuichi Miyazaki, Yasuo Okabe, Jun Umemoto
    Algorithm Engineering (WAE 2000) 2001年8月24日 Springer Berlin Heidelberg
  • MM Halldorsson, K Iwama, S Miyazaki, S Taketomi
    COMPUTING AND COMBINATORICS (COCOON 2000), PROCEEDINGS 2000年 SPRINGER-VERLAG BERLIN
    At each step of the online independent set problem, we axe given a vertex v and its edges to the previously given vertices. We are to decide whether or not to select v as a member of an independent set. Our goal is to maximize the size of the independent set. It is not difficult to see that no online algorithm can attain a performance ratio better than n - 1, where n denotes the total number of vertices. Given this extreme difficulty of the problem, we study here relaxations where the algorithm can hedge his bets by maintaining multiple alternative solutions simultaneously. We introduce two models. In the first, the algorithm can maintain a, polynomial number of solutions (independent sets) and choose the largest one as the final solution. We show that theta (n/log n) is the best competitive ratio for this model. In the second more powerful model, the algorithm can copy intermediate solutions and grow the copied solutions in different ways. We obtain an upper bound of O(n/(k log n)), and a lower bound of n/(e(k+1) log(3) n), when the algorithm can make n(k) operations per vertex.
  • K. Iwama, D. Manlove, S. Miyazaki, Y. Morita
    26th International Colloquium on Automata, Languages, and Programming (ICALP 1999), Lecture Notes in Computer Science 1999年
  • K Iwama, S Miyazaki
    ALGORITHMS AND COMPUTATIONS (ISAAC 1999) 1999年 SPRINGER-VERLAG BERLIN
    Our main result shows that a shortest proof size of tree-like resolution for the pigeonhole principle is superpolynomially larger than that of DAG-like resolution. In the proof of a lower bound, we exploit a relationship between tree-like resolution and backtracking, which has long been recognized in this field but not been used before to give explicit results.
  • Byungki Cha, Kazuo Iwama, Yahiko Kambayashi, Shuichi Miyazaki
    Proceedings of the National Conference on Artificial Intelligence (AAAI 1997) 1997年
  • Miyazaki, S, Iwama, K, Kambayashi, Y
    Proc. International Symposium on Cooperative Database Systems for Advanced Applications (CODAS 1996), pp.448-454, 1996. 1996年
  • K Iwama, S Miyazaki
    COMPUTING AND COMBINATORICS (COCOON 1995) 1995年 SPRINGER-VERLAG BERLIN
    It is said that a set L(1) in a class C-1 approximates a set L(2) in a class C-2 if L(1) is a subset of L(2). Approximation L(1) is said to be optimal if there is no approximation L(1)' such that L(1)' superset of L(1) and L(1)' - L(1) is infinite. When C-1=P and C-2=NP, it is known that there is no optimal approximation under a quite general condition unless P=NP. In this paper we discuss the case where C-1=the class of NP-complete sets and C-2=coNP. A similar result as above that shows the difficulty of the optimal approximation is obtained. Approximating coNP sets by NP-complete sets play an important role in the efficient generation of test instances for combinatorial algorithms.
  • K IWAMA, S MIYAZAKI
    IFIP World Computer Congress '94, VOL I 1994年 ELSEVIER SCIENCE PUBL B V
    This paper discusses polynomnial-time reductions from Halmiltonian Circuit (HC), k-Vertex Coloring (k-VC), and k-Clique Problems to Satisfiability Problem (SATI which;ire efficient in the number of Boolean variables needed in SAT. We first present a basic type of reductions that need (n - 1) log(n - 1), (n - 1] log k, and k log n variables for HC. k-VC and k-Clique: respectively. Several heuristics can reduce the number of variables. Some of them achieve: (n - I - 1) log(n - 1) + Sigma log d(i) for HC (I is the size of any independent set of vertices v(i)'s whose degree is d(i)'s), and log n + (k - 1) log D for k-Clique (D is the kth largest degree of the graph). Recent revolutionary progress in SAT algorithms will make it increasingly reasonable to solve (hard) combinatorial problems after reducing them to SAT. Efficiency in the above sense apparently plays a key role in this approach. From a different viewpoint, the number of variables can act as a complexity measure for the original problems, if the reduction is sufficiently efficient. The merits of heuristics can also be evaluated by (the reduction of) this complexity.

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

 7
もっとみる

所属学協会

 4

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

 23
もっとみる

社会貢献活動

 7
一覧へ戻る