Curriculum Vitaes
Profile Information
- Affiliation
- Professor, Graduate School of Information Science, University of Hyogo
- Degree
- Doctor of Engineering(Kyushu University)
- J-GLOBAL ID
- 200901042786776786
- researchmap Member ID
- 1000259772
- External link
Research Interests
5Research History
4-
Apr, 2022 - Present
-
Apr, 2007 - Mar, 2022
-
Apr, 2002 - Mar, 2007
-
Apr, 1998 - Mar, 2002
Education
3-
Apr, 1995 - Mar, 1998
-
Apr, 1993 - Mar, 1995
-
Apr, 1989 - Mar, 1993
Awards
3-
Nov, 2009
Papers
42-
Discrete Mathematics, Algorithms and Applications, 16(05) 2350057-1-2350057-39, Jul, 2024 Peer-reviewedIn 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.
-
Theoretical Computer Science, 989 114389-1-114389-18, Mar, 2024 Peer-reviewed
-
International Journal of Foundations of Computer Science, 34(07) 853-873, Jun 30, 2023 Peer-reviewedThis 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.
-
Discrete Mathematics, Algorithms and Applications, 13(06), Dec, 2021 Peer-reviewedIn 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.
-
Algorithmica, 83(9) 2678-2696, Sep, 2021 Peer-reviewedCorresponding author
Misc.
110-
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 117(301) 67-74, Nov 16, 2017
-
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 117(300) 67-74, Nov 16, 2017
-
IEICE technical report. Social Implications of Technology and Information Ethics, 114(494) 143-147, Mar 5, 2015Given 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.
-
IEICE technical report. Internet Architecture, 114(495) 143-147, Mar 5, 2015Given 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.
-
IPSJ Journal, 56(2), Feb 15, 2015The Hospitals/Residents problem is a many-to-one generalization of the well-known Stable Marriage problem. Its instance consists of a set of residents, a set of hospitals, each resident's preference list, each hospital's preference list, and each hospital's capacity (i.e., the number of available positions). It asks to find a stable matching between residents and hospitals. In this paper, we consider the problem of deciding, given residents' preference lists and a matching, whether there are hospitals' preference lists that make a given matching stable. We call this problem Stable Hospital's Preference List problem (SHPL). It is easy to see that there always exists a solution if we allow arbitrary preference lists of hospitals. Considering more suitable situations, we pose a restricted version, called k-SHPL, in which there are only k kinds of preference lists of hospitals. We show that 1-SHPL is solvable in polynomial time, while k-SHPL is NP-complete for any k such that 2 ? k ? n1-ε, where n is the number of residents and ε is any positive constant. We also present four heuristics algorithms (first-fit algorithms) for 2-SHPL. We implement these algorithms and present a computational study using random instances.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.23(2015) No.2 (online)------------------------------
-
IEICE technical report. Theoretical foundations of Computing, 114(19) 37-44, Apr 24, 2014We consider a variant of the online buffer management problem in network switches, called the k-frame throughput maximization problem (k-FTM). This problem models the situation where a large frame is fragmented into k packets and transmitted through the Internet, and the receiver can reconstruct the frame only if he/she accepts all the k packets. Kesselman et al. introduced this problem and showed that its competitive ratio is unbounded even when k=2. They also introduced a restricted variant of k-FTM, called k-OFTM. They proposed an online algorithm and showed that its competitive ratio is at most (2kB)/([B/k])+k for any B≧k, where B is the size of the buffer. They also presented a lower bound of B/([2B/k])=Ω(k) for deterministic online algorithms when 2B≧k and k is a power of 2. In this paper, we improve upper and lower bounds on the competitive ratio of k-OFTM. Our main result is to improve an upper bound of O(k^2) by Kesselman et al. to (5B+[B/k]-4)/([B/2k])=O(k) for B≧2k, which matches their lower bound of Ω(k) asymptotically. We also present an improved lower bound of (2B)/([B/(k-1)])+1 on the competitive ratio of deterministic online algorithms for any k≧2 and any B≧k-1, and the first nontrivial lower bound of k-1 on the competitive ratio of randomized algorithms for any k≧3 and any B.
-
2014(11) 1-6, Feb 20, 2014
-
IEICE technical report. Internet Architecture, 113(443) 61-66, Feb, 2014With the wide use of e-mail, it has become commonly expected that e-mails are delivered to recipients immediately. It is not rare that a huge amount of e-mails are delivered to a mail transfer system in a very short time unintentionally. Such e-mails sometimes causes excessive load to the system and to increase traffic of network, and e-mails are delivered with serious delay in such situations. We propose a mail transfer system to detect efficiently such e-mail with each pair of envelope-from and envelope-to address managed by a hash table. In proposed system, the number of each pair envelope-from and envelope-to address is counted, and if the number of the delivery including a specific pair (envelope-from, envelope-to address) during a short period exceeds a pre-specified threshold, we regard this pair as a cause of a huge amount of e-mails. We prepare multiple hash tables which managed envelope-from and envelope-to address to prevent an increase in scale of the hash table, and we divide such hash tables every time and empty all entries at fixed intervals. We also prepare for the blocklist to judge a huge amount of e-mails beforehand. We implement the proposed system and evaluate it.
-
2013 INTERNATIONAL CONFERENCE ON SIGNAL-IMAGE TECHNOLOGY & INTERNET-BASED SYSTEMS (SITIS), 896-900, 2013 Peer-reviewedWith the wide use of e-mail, it has become commonly expected that e-mails sent are delivered to recipients immediately. It is not rare that a huge amount of e-mails are posted to a mail transfer system in very short time unintentionally, due to misconfiguration such as an e-mail loop. Such e-mail flood increases the load of the mail transfer system, and causes serious delays in e-mail delivery of the system. We propose a mail transfer system with resiliency against e-mail flood. In the proposed system, the number of each pair of envelope-from and envelope-to is counted. If the number of sessions including a specific pair (envelope-from, envelope-to) during a short period exceeds a pre-specified threshold, we regard this pair as a cause of a huge amount of e-mails, and reject e-mails including this pair after that. In this way, a huge amount of e-mails are selectively restricted without affecting transfer of ordinary e-mails.
-
Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2011) pp. 309-313,, May, 2011
-
IEICE technical report, 110(325(COMP2010 39-46)) 45-51, Nov 26, 2010In the seat reservation problem, there are k station, s_1 through s_k, and one train with n seats departing from the station s_1 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 spacifying 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√<k-1>+4), which improves the previous bound of 8/(k+5). We also give an upper bound of 2/(k-2√<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+√<13>)/(k-1+√<13>)((≃6.6/(k+2.6)) and 2/(k-1), respectively, on the competitive ratio, which improves the previous bounds of (4+2√<13>)/(k+3+2√<13>)((≃11.2/(k+10.2)) and 1/(k-1), respectively.
-
IEICE technical report, 110(304(IA2010 51-57)) 19-24, Nov 17, 2010These days, as e-mails become more and more important, the demand for certified e-mail is growing. Methods for certified e-mail are classified into ones with a Trsuted Third Party (TTP) as a intermediate and ones without a TTP. The latter is superior to the former in terms of costs and flexibility. However, most of studies on methods without a TTP are on a theoretical aspect, therefore the number of studies which discuss the actual operation of the system is small. In this paper, we propose the protocol without an intermediate, and we show that on the basis of Public Key Infrastructure (PKI) the protocol satisfies security requirements for delivery certificate by using only a simple bit transfer. We also discuss the actual operation and design the system with this protocol.
-
電子情報通信学会総合大会講演論文集, 2010(2) "S-154"-"S-155", Mar 2, 2010
-
IEICE technical report, 109(391(COMP2009 39-48)) 1-8, Jan 18, 2010The k-Canadian Traveller Problem (k-CTP) is one of the online problems. In this problem, we are given an undirected edge-weighted graph G=(V,E), a source vertex s, and a destination vertex t, and our purpose is to traverse G from s to t. An online algorithm knows the topology of G and the weight of each edge in advance. However, at most k edges of G are blocked and the algorithm cannot go through these edges. Initially, the algorithm does not know which edges are blocked; when it reaches either endpoint of a blocked edge, it first learns that this edge is blocked. For this problem, Westphal gave a deterministic (2k+1)-competitive algorithm, and proved that there is no better algorithm. In this paper, we restrict the graph class to obtain a better competitive ratio. Specifically, we consider the case that (i) edge weights are uniform (i.e., all the weights are 1), and (ii) edge weights satisfy the triangle inequality, on complete graphs. (We also assume that k≦|V|-2 in order to guarantee the connectivity of the input graphs.) In both cases, we give optimal online algorithms whose competitive ratios are (k+1)/2 and k, respectively.
-
信学技報,Vol.109, No. 391, CQMP2009-39:( 電子情報通信学会コンピュテーション研究会) pp. 1-8, 2010 年1 月., 2010
-
IEICE technical report, 109(235) 35-40, Oct 9, 2009In the stable marriage problem that allows incomplete preference lists, all stable matchings for a given instance have the same size. However, if we ignore the stability, there can be larger matchings. Biro et al. defined the problem of finding a maximum cardinality matching that contains minimum number of blocking pairs. They proved that (i) this problem is NP-hard and cannot be approximated within the ratio of n^<1-ε> for any constant ε>0 unless P=NP, where n is the number of men in an input, (ii) even if each preference list is of length at most 3, the problem remains NP-hard and there exists a constant δ(>1) such that this problem cannot be approximated within the ratio of δ unless P=NP, and (iii) if the length of preference lists of one sex is at most 2, this problem is solvable in polynomial time. In this paper, we improve the constant δ of (ii) to n^<1-ε> for any ε>0.
-
IEICE technical report, 109(211(AI2009 9-18)) 19-22, Sep 18, 2009In the stable matching problem, we are given a set of men and women, and each person's preference list that orders members of the opposite gender. Our task is to find a matching between men and women that satisfies the "stability" condition. This problem has wide variety of applications in real-world, such as assigning medical students to hospitals, primary school students to secondary schools, and graduate students to supervisors. In this presentation, we introduce the problem and show some elementary properties of the problem. We also show some of recent results on this problem, which are mainly obtained by the authors.
-
Proceedings of the IEICE General Conference, 2009(1) "S-31"-"S-32", Mar 4, 2009
-
IEICE technical report, 108(275(IA2008 41-46)) 7-12, Oct 29, 2008These days, e-mails have become one of the most important communication tools, and hence demand on certified e-mails is growing. Although some commercial services provided by intermediate agent, like U.S. Postal Service, have already launched, they are not used commonly because of costs and reliabilities. In this paper, we propose a protocol which enables users to exchange certified e-mails and receipts without using intermediate agents. Our protocol uses a gradual secret exchange protocol proposed by Okamoto and Ohta. We also discuss how to implement our protocol on a system.
-
IEICE technical report, 108(206(COMP2008 23-33)) 71-78, Sep 4, 2008The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service guarantee. For this problem, a lot of models have been considered. Among others, we focus on multi-queue switches in QoS Networks proposed by Azar et alAzar et al introduced the relaxed model in order to achieve a good upper bound on the competitive ratio for this model. In this paper, we improve the competitive ratios of several multi-queue models by improving an upper bound for the relaxed model. We propose an online algorithm DS (Dual Scheduling) for the relaxed model. This algorithm works for (either preemptive or non-preemptive) 2-value model, but it uses as subroutines online algorithms for the non-preemptive unit-value model, which has been extensively studied. The performance of DS depends on the performance of the algorithms used as subroutines. The followings are a couple of examples of the improvement on the competitive ratios of multi-queue models using our result: (i) We improved the competitive ratio of deterministic algorithms for the non-preemptive 2-value model from 4 to 3.177 for large enough B. a switch can store up to B packets simultaneously. (ii) We proved that the competitive ratio of randomized algorithms for the non-preemptive 2-value model is at most (17)/2-√<30>≃3.023 for large enough B.
-
IEICE technical report, 107(537(COMP2007 55-67)) 1-8, Mar 3, 2008The 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 Gusfield 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.
-
信学技報, vol. 108, no. 275, IA2008-42, pp. 7-12, 2008-11., 2008
-
Proc. 1st Asian Association for Algorithms and Computation (AAAC), p.42, 2008-4., 2008 Peer-reviewed
-
Proc. 1st Asian Association for Algorithms and Computation (AAAC), p.30, 2008-4., 2008 Peer-reviewed
-
IEICE technical report, 107(258(COMP2007 41-47)) 1-6, Oct 9, 2007In the stable roommates problem, we are given 2N people, each having a preference list that ranks remaining 2N-1 people in a strict order according to his/her preferences. It asks to find a stable matching, namely, a set of N pairs that satisfies the "stability" condition. There are instances that have no solution, but Irving has developed a polynomial time algorithm that decides if there exists a solution, and finds one if exists. We extend this problem into 3-dimension. In our problem, we are given 3N people and are asked to partition them into N triples. We prove that the problem of deciding if a stable matching exists is NP-complete.
-
IEICE technical report, 107(219(COMP2007 32-40)) 51-57, Sep 13, 2007The purpose of the online graph exploration problem is to visit all the nodes of a given graph and come back to the starting node with the minimum total traverse cost. However, unlike the classical traveling salesperson problem, information of the graph is given online. When an online algorithm (called a searcher) visits a node v, then it learns information on nodes and edges adjacent to v. It is known that there is a 16-competitive online algorithm for planer graphs. Recently, Asahiro et al. considered this problem on cycles and proved that there is a 1.5-competitive online algorithm, while no online algorithm can be (1.25-ε)-competitive for any positive constant e. In this paper, we give an optimal online algorithm for this problem; namely, we give a 1+√<3>/2(≃1.366)-competitive algorithm, and prove that there is no (1+√<3>/2-ε)-competitive algorithm for any positive constant ε.
-
電子情報通信学会技術研究報告, 107(127(COMP2007 18-31)) 63-70, Jun 22, 2007
-
Proceedings of the IEICE General Conference, 2007(1) "S-5"-"S-6", Mar 7, 2007
-
信学技報,Ｖｏｌ.107 ,No.219, CQMP2007-39, (電 子 晴報通 信 学会コ ンピュ テ ーショ ン 研 究会),pp. 51-57, 2007-9., 2007
-
Proc. 10th KOREAJAPAN Joint Workshop on Algorithms and Computation (WAAC 2007), pp. 105-112, 2007 Peer-reviewed
-
IEICE technical report, 106(405(COMP2006 41-49)) 15-22, Nov 27, 2006In 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.
Books and Other Publications
10-
Springer Singapore, Mar, 2024 (ISBN: 9789819997725) Refereed
Presentations
41-
Proc. the 28th International Computing and Combinatorics Conference (COCOON 2022), Oct, 2022
-
Proc. the 15th International Symposium on Algorithmic Game Theory (SAGT 2022), Sep, 2022
-
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Mar, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik
-
Combinatorial Optimization and Applications (COCOA 2020) Lecture Notes in Computer Science book series (LNCS, volume 12577), Dec, 2020, Springer International Publishing
-
Combinatorial Algorithms (IWOCA 2020). Lecture Notes in Computer Science, vol 12126, 2020, Springer International Publishing
Teaching Experience
7-
Apr, 2023 - PresentDA (University of Hyogo)
-
Apr, 2022 - PresentGraph Theory (University of Hyogo)
-
2022 - Presentアルゴリズム特論 (兵庫県立大学)
-
Apr, 2019 - Present社会情報科学のための数学 (University of Hyogo)
-
Apr, 2012 - Mar, 2022Graph Theory (Kyoto University)
Research Projects
21-
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Japan Society for the Promotion of Science, Apr, 2020 - Mar, 2025
-
科学研究費助成事業, 日本学術振興会, Apr, 2021 - Mar, 2024
-
Grants-in-Aid for Scientific Research, Japan Society for the Promotion of Science, Apr, 2016 - Mar, 2021
-
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Japan Society for the Promotion of Science, Apr, 2016 - Mar, 2021
-
Grants-in-Aid for Scientific Research, Japan Society for the Promotion of Science, Apr, 2013 - Mar, 2016