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, 106(405) 49-56, Nov, 2006We 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 NP-hard and the current best known approximation algorithm achieves the approximation ratio 2-c1/√<N>, where c is a constant such that c≦1/4√<6> and N is the number of men in an input. In this paper, we improve the ratio to 1.875.
-
IEICE technical report, 106(128(COMP2006 17-24)) 7-14, Jun 16, 2006This paper introduces a new timetabling problem on universities, called interview timetabling. In this problem, some constant number, say, three, of referees are assigned to each of 2n graduate students. It requires to assign these students to an n×2 array, consisting of n timeslots and two rooms, so that two students sharing the same referee must be assigned to different timeslots. Furthermore, we want to minimize the total number of movements of all referees between two rooms. This is a problem actually having arisen in the interview timetabling in Kyoto University. We propose two restricted models of this problem, and investigate their time complexity.
-
The Journal of the Institute of Electronics, Information and Communication Engineers, 89(4) 299-303, Apr 1, 2006
-
Proc. of The 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2006). pp. 448-453, August 2006., 2006 Peer-reviewed
-
IEICE technical report. Theoretical foundations of Computing, 105(144(COMP2005 18-27)) 17-22, Jun 17, 2005The buffer management problem is a kind of online problems, which formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered, and in this paper, we focus on the model of shared memory switches. We improve the competitive ratio of the Longest Queue Policy (LQD) to 2-1/N, where N is the number of output ports in a switch.
-
IEICE technical report. Theoretical foundations of Computing, 105(72(COMP2005 9-17)) 45-51, May 13, 2005We 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 NP-hard and the current best known approximation algorithm achieves the approximation ratio 2-c (logN)/N, where c is an arbitrary positive constant and N is the number of men in an input. In this paper, we improve the ratio to 2-c 1/(N^<2/3>), where c is a constant such that c≦1/(2(√^3<6>)).
-
The Journal of the Institute of Electronics, Information and Communication Engineers, 88(3) 195-199, Mar 1, 2005
-
IEICE technical report. Theoretical foundations of Computing, 104(16(COMP2004 1-8)) 53-60, Apr 22, 2004An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both of these 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. There are several contributions that give approximation algorithms with factor better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio 2-c(log N)/N for an arbitrarily positive constant c, where N denotes the number of men in an input.
-
Proceedings of the IEICE General Conference, 2004(1) 2-2, Mar 8, 2004
-
Technical report of IEICE. ISEC, 103(499(ISEC2003 84-95)) 1-6, Dec 15, 2003Cheating is a serious problem in network games, because we cannot see our opponent. One can use a reliable judgment server to solve this problem, but it is reasonable to assume, in the network society, that people trust nobody but only himself/herself. It is then important to play a network game securely without server, namely via peer-to-peer communication. There are several attacks to be consdered. For example, in card games, attackers may control card shuffling or look at cards in the deck illegally. There is a protocol, so called a Mental Poker Protocol, to exclude these kinds of attacks. In this paper, we consider the Gunjin-Shogi. Our goal of research is to develop secure protocols for this game and implement the game using these or other known protocols.
-
IEICE technical report. Theoretical foundations of Computing, 102(522(COMP2002 53-61)) 41-47, Dec 19, 2002While 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, approximation of factor two is trivial. In this paper, we give a first nontrivial result for approximation of factor less than two. Our algorithm achieves a factor of 25/13(< 1.924) for a restricted case where each tie is of length two.
-
Proceedings of the IEICE General Conference, 2001(1) 4-4, Mar 7, 2001
-
Proc. KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2001),/,59-66, 2001
-
IEICE technical report. Theoretical foundations of Computing, 100(25(COMP2000 1-5)) 25-32, Apr 26, 2000At each step of the online independent set problem, we are given a vertex and edges to the vertices previously given. We are reqired to decide whether we choose that vertex as a member of an independent set or not, before receiving the next vertex. In an ordinary setting of this problem, Halldorsson gave a tight upper and lower bound, n-1, of the competitive ratio. Also, he generalized the problem and gave a tight n/4 upper and lower bound. In this paper, we further extend the problem and give nontrivial upper and lower bounds.
-
IPSJ SIG Notes, 2000(23) 95-100, Mar 2, 2000The 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.
-
IEICE technical report. Theoretical foundations of Computing, 99(549(COMP99 69-78)) 49-56, Jan 19, 2000Satisfiability Problem (SAT) is one of the most fundamental combinatorial problems. Local search algorithms, which were developed recently, are probably the most popular SAT algorithms because of the surprising efficiency. However, as the number of variables and clauses increase, it becomes still difficult to solve SAT in practical time. The purpose of this paper is to speed up local search using vectorization and parallelization. We resolve several issues that arise when we implement on a vector supercomputer and show efficiency of our method. Furthermore, we show experimental results for benchmarks of 2nd DIMACS Implementation Challenge.
-
Proc. The AAAI-2000 workshop on parallel and distributed search for reasoning,, 2000
-
RIMS Kokyuroku, 1120 51-57, Dec, 1999
-
IEICE technical report. Theoretical foundations of Computing, 99(288(COMP99 31-38)) 15-22, Sep 3, 1999
-
IEICE technical report. Theoretical foundations of Computing, 99(30(COMP99 1-9)) 57-64, Apr 23, 1999In this paper, we give two online problems, Online MAX WEIGHTED SAT and Online MAX WEIGHTED INDEPENDENT SET, which are hardest in the following two senses: (i) These problems can simulate all online problems without worsening the competitive ration at all. (ii) We can show that the lower bound of the competitive ration for these problems is the worst possible even if we can use probably the most powerful online algorithm (an algorithm which can hold many intermediate solutions simultaneously).
-
IPSJ SIG Notes, 99(26) 15-22, Mar 15, 1999An 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 natura 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.
-
IEICE technical report. Theoretical foundations of Computing, 98(432(COMP98 51-62)) 33-40, Nov 20, 1998The original stable marriage problem requires both each man and woman to submit a complete and strict order of his/her preference, i.e., a total order list of, say, 100 people, if there are 100 men and women. This is obviously unrealistic often in practice, and several relaxations have been proposed, including the following two common ones: One is to allow an incomplete list, i.e., a man is allowed to accept only a subset of the women and vice versa. The other is to allow a "weaker"preference list such as a list including ties and partial orders. A little surprisingly, it is known that both problems can still be solved in polynomial time. In this paper, we show that the problem becomes NP-hard, if we allow both relaxations(incomplete lists and partial orders)at the same time.
-
IEICE technical report. Theoretical foundations of Computing, 97(375(COMP97 60-72)) 73-79, Nov 14, 1997partial MAXSAT (PMSAT) is a generalization of MAXSAT and has flexibility to simulate general combinatorial optimization problems, such as scheduling problems. However, it is shown empirically that it can be solved efficiently by local search algorithms for MAXSAT using weighting strategy. In this paper, we show the completeness of PMSAT and other partial optimization problems in order to demonstrate their usefulness.
-
Proceedings of the IEICE General Conference, 1995(1) 8-8, Mar 27, 1995
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
23-
科学研究費助成事業, 日本学術振興会, Apr, 2024 - Mar, 2027
-
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