Toshiya Itoh
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Toshiya Itoh has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Suthee Ruangwises
Chulalongkorn University
17 shared publications - Steven Ge
Tokyo Institute of Technology
5 shared publications - Tsubasa Harada
Tokyo Institute of Technology
5 shared publications - Shuichi Miyazaki
University of Hyogo
4 shared publications Yoshinori Takei
Department of Electrical and Information Engineering, National Institute of Technology, Akita College
2 shared publications- Hiroki Shizuya
Tohoku University
1 shared publication
Latest Publications
- Open Access
- 26 October 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
Near-Optimal Deterministic Online Transportation
For the online transportation problem with \(m\) server sites, it has long been known that the competitive ratio of any deterministic algorithm is at least \(2m-1\) . Kalyanasundaram and Pruhs conjectured in 1998 that a deterministic \((2m-1)\) -competitive algorithm exists for this problem, a conjecture that has remained open for over two decades. In this paper, we propose a new deterministic algorithm for the online transportation problem and show that it achieves a competitive ratio of at most \(8m-13\) . This is the first \(O(m)\) -competitive deterministic algorithm, coming close to the lower bound of \(2m-1\) within a constant factor.- 26 October 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
Open AccessNear-Optimal Deterministic Online Transportation
For the online transportation problem with \(m\) server sites, it has long been known that the competitive ratio of any deterministic algorithm is at least \(2m-1\) . Kalyanasundaram and Pruhs conjectured in 1998 that a deterministic \((2m-1)\) -competitive algorithm exists for this problem, a conjecture that has remained open for over two decades. In this paper, we propose a new deterministic algorithm for the online transportation problem and show that it achieves a competitive ratio of at most \(8m-13\) . This is the first \(O(m)\) -competitive deterministic algorithm, coming close to the lower bound of \(2m-1\) within a constant factor. - 21 February 2025
- Published by Springer Nature
- p. 196-214
Popularity on the 3D-Euclidean Stable Roommates
- 21 February 2025
- Published by Springer Nature
- p. 196-214
Popularity on the 3D-Euclidean Stable Roommates
- Open Access
- 14 March 2024
- Published by Springer Nature
- p. 187-215
Mechanism Design for Mobility
This chapter presents the development of matching theory toward implementing the next-generation car-sharing systems, consisting of three topics: (1) online facility assignment problems on a line, (2) two-sided matching with flexible quotas: student-project-resource matching-allocation problem, and (3) formalizing station-based one-way car sharing as three-sided matching. The first two relate to developments in basic research, while the last one is application-oriented.
- 14 March 2024
- Published by Springer Nature
- p. 187-215
Open AccessMechanism Design for Mobility
This chapter presents the development of matching theory toward implementing the next-generation car-sharing systems, consisting of three topics: (1) online facility assignment problems on a line, (2) two-sided matching with flexible quotas: student-project-resource matching-allocation problem, and (3) formalizing station-based one-way car sharing as three-sided matching. The first two relate to developments in basic research, while the last one is application-oriented.
- 9 December 2023
- Published by Springer Nature
- p. 316-329
Popularity on the Roommate Diversity Problem
- 9 December 2023
- Published by Springer Nature
- p. 310-322
Online Facility Assignment for General Layout of Servers on a Line
- 9 December 2023
- Published by Springer Nature
- p. 310-322
Online Facility Assignment for General Layout of Servers on a Line
- Open Access
Popularity on the 3D-Euclidean Stable Roommates
We study the 3D-Euclidean Multidimensional Stable Roommates problem, which asks whether a given set $V$ of $s\cdot n$ agents with a location in 3-dimensional Euclidean space can be partitioned into $n$ disjoint subsets $π= \{R_1 ,\dots , R_n\}$ with $|R_i| = s$ for each $R_i \in π$ such that $π$ is (strictly) popular, where $s$ is the room size. A partitioning is popular if there does not exist another partitioning in which more agents are better off than worse off. Computing a popular partition in a stable roommates game is NP-hard, even if the preferences are strict. The preference of an agent solely depends on the distance to its roommates. An agent prefers to be in a room where the sum of the distances to its roommates is small. We show that determining the existence of a strictly popular outcome in a 3D-Euclidean Multidimensional Stable Roommates game with room size $3$ is co-NP-hard.Open AccessPopularity on the 3D-Euclidean Stable Roommates
We study the 3D-Euclidean Multidimensional Stable Roommates problem, which asks whether a given set $V$ of $s\cdot n$ agents with a location in 3-dimensional Euclidean space can be partitioned into $n$ disjoint subsets $π= \{R_1 ,\dots , R_n\}$ with $|R_i| = s$ for each $R_i \in π$ such that $π$ is (strictly) popular, where $s$ is the room size. A partitioning is popular if there does not exist another partitioning in which more agents are better off than worse off. Computing a popular partition in a stable roommates game is NP-hard, even if the preferences are strict. The preference of an agent solely depends on the distance to its roommates. An agent prefers to be in a room where the sum of the distances to its roommates is small. We show that determining the existence of a strictly popular outcome in a 3D-Euclidean Multidimensional Stable Roommates game with room size $3$ is co-NP-hard. - Open Access
Competitive Analysis of Online Facility Assignment for General Layout of Servers on a Line
In the online facility assignment on a line ${\rm OFAL}(S,c)$ with a set $S$ of $k$ servers and a capacity $c:S\to\mathbb{N}$, each server $s\in S$ with a capacity $c(s)$ is placed on a line, and a request arrives on a line 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. An algorithm can match up to $c(s)$ requests to a server $s\in S$. In this paper, we propose a new online algorithm PTCP (Policy Transition at Critical Point) for $\mathrm{OFAL}(S,c)$ and show that PTCP is $(2α(S)+1)$-competitive, where $α(S)$ is informally the ratio of the diameter of $S$ to the maximum distance between two adjacent servers in $S$. Depending on the layout of servers, $α(S)$ ranges from constant (independent of $k$) to $k-1$. Among all of known algorithms for $\mathrm{OFAL}(S,c)$, this upper bound on the competitive ratio is the best when $α(S)$ is small. We also show that the competitive ratio of any MPFS (Most Preferred Free Servers) algorithm is at least $2α(S)+1$. For $\mathrm{OFAL}(S,c)$, recall that MPFS is a class of algorithms whose competitive ratio does not depend on a capacity $c$ and it includes the natural greedy algorithm and PTCP, etc. Thus, this implies that PTCP is the best for $\mathrm{OFAL}(S,c)$ in the class MPFS.Open AccessCompetitive Analysis of Online Facility Assignment for General Layout of Servers on a Line
In the online facility assignment on a line ${\rm OFAL}(S,c)$ with a set $S$ of $k$ servers and a capacity $c:S\to\mathbb{N}$, each server $s\in S$ with a capacity $c(s)$ is placed on a line, and a request arrives on a line 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. An algorithm can match up to $c(s)$ requests to a server $s\in S$. In this paper, we propose a new online algorithm PTCP (Policy Transition at Critical Point) for $\mathrm{OFAL}(S,c)$ and show that PTCP is $(2α(S)+1)$-competitive, where $α(S)$ is informally the ratio of the diameter of $S$ to the maximum distance between two adjacent servers in $S$. Depending on the layout of servers, $α(S)$ ranges from constant (independent of $k$) to $k-1$. Among all of known algorithms for $\mathrm{OFAL}(S,c)$, this upper bound on the competitive ratio is the best when $α(S)$ is small. We also show that the competitive ratio of any MPFS (Most Preferred Free Servers) algorithm is at least $2α(S)+1$. For $\mathrm{OFAL}(S,c)$, recall that MPFS is a class of algorithms whose competitive ratio does not depend on a capacity $c$ and it includes the natural greedy algorithm and PTCP, etc. Thus, this implies that PTCP is the best for $\mathrm{OFAL}(S,c)$ in the class MPFS. - Open Access
How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku
Shikaku is a pencil puzzle consisting of a rectangular grid, with some cells containing a number. The player has to partition the grid into rectangles such that each rectangle contains exactly one number equal to the area of that rectangle. In this paper, we propose two physical zero-knowledge proof protocols for Shikaku using a deck of playing cards, which allow a prover to physically show that he/she knows a solution of the puzzle without revealing it. Most importantly, in our second protocol we develop a general technique to physically verify a rectangle-shaped area with a certain size in a rectangular grid, which can be used to verify other problems with similar constraints.
Open AccessHow to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku
Shikaku is a pencil puzzle consisting of a rectangular grid, with some cells containing a number. The player has to partition the grid into rectangles such that each rectangle contains exactly one number equal to the area of that rectangle. In this paper, we propose two physical zero-knowledge proof protocols for Shikaku using a deck of playing cards, which allow a prover to physically show that he/she knows a solution of the puzzle without revealing it. Most importantly, in our second protocol we develop a general technique to physically verify a rectangle-shaped area with a certain size in a rectangular grid, which can be used to verify other problems with similar constraints.
- Open Access
Physical ZKP for Makaro Using a Standard Deck of Cards
Makaro is a logic puzzle with an objective to fill numbers into a rectangular grid to satisfy certain conditions. In 2018, Bultel et al. developed a physical zero-knowledge proof (ZKP) protocol for Makaro using a deck of cards, which allows a prover to physically convince a verifier that he/she knows a solution of the puzzle without revealing it. However, their protocol requires several identical copies of some cards, making it impractical as a deck of playing cards found in everyday life typically consists of all different cards. In this paper, we propose a new ZKP protocol for Makaro that can be implemented using a standard deck (a deck consisting of all different cards). Our protocol also uses asymptotically less cards than the protocol of Bultel et al. Most importantly, we develop a general method to encode a number with a sequence of all different cards. This allows us to securely compute several numerical functions using a standard deck, such as verifying that two given numbers are different and verifying that a number is the largest one among the given numbers.
Open AccessPhysical ZKP for Makaro Using a Standard Deck of Cards
Makaro is a logic puzzle with an objective to fill numbers into a rectangular grid to satisfy certain conditions. In 2018, Bultel et al. developed a physical zero-knowledge proof (ZKP) protocol for Makaro using a deck of cards, which allows a prover to physically convince a verifier that he/she knows a solution of the puzzle without revealing it. However, their protocol requires several identical copies of some cards, making it impractical as a deck of playing cards found in everyday life typically consists of all different cards. In this paper, we propose a new ZKP protocol for Makaro that can be implemented using a standard deck (a deck consisting of all different cards). Our protocol also uses asymptotically less cards than the protocol of Bultel et al. Most importantly, we develop a general method to encode a number with a sequence of all different cards. This allows us to securely compute several numerical functions using a standard deck, such as verifying that two given numbers are different and verifying that a number is the largest one among the given numbers.
- Open Access
Capacity-Insensitive Algorithms for Online Facility Assignment Problems on a Line
In the online facility assignment problem OFA(k,\ell), there exist k servers with a capacity \ell \geq 1 on a metric space 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 OFA(k,\ell), we consider OFA(k,\ell) on a line, which is denoted by OFAL(k,\ell) and OFAL_{eq}(k,\ell), where the latter is the case of OFAL(k,\ell) with equidistant servers. In this paper, we deal with 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 \ell \geq 1, ALG is c-competitive for OFA(k,1) iff ALG is c-competitive for OFA(k,\ell). By applying the capacity-insensitive property of the greedy algorithm GRDY, we derive the matching upper and lower bounds 4k-5 on the competitive ratio of GRDY for OFAL_{eq}(k,\ell). To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm ALG for OFAL_{eq}(k,\ell) is at least $2k-1$. Then we propose a new MPFS algorithm IDAS (Interior Division for Adjacent Servers) for OFAL(k,\ell) and show that the competitive ratio of IDAS for OFAL}_{eq}(k,\ell) is at most 2k-1, i.e., IDAS for OFAL_{eq}(k,\ell) is best possible in all the MPFS algorithms.Open AccessCapacity-Insensitive Algorithms for Online Facility Assignment Problems on a Line
In the online facility assignment problem OFA(k,\ell), there exist k servers with a capacity \ell \geq 1 on a metric space 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 OFA(k,\ell), we consider OFA(k,\ell) on a line, which is denoted by OFAL(k,\ell) and OFAL_{eq}(k,\ell), where the latter is the case of OFAL(k,\ell) with equidistant servers. In this paper, we deal with 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 \ell \geq 1, ALG is c-competitive for OFA(k,1) iff ALG is c-competitive for OFA(k,\ell). By applying the capacity-insensitive property of the greedy algorithm GRDY, we derive the matching upper and lower bounds 4k-5 on the competitive ratio of GRDY for OFAL_{eq}(k,\ell). To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm ALG for OFAL_{eq}(k,\ell) is at least $2k-1$. Then we propose a new MPFS algorithm IDAS (Interior Division for Adjacent Servers) for OFAL(k,\ell) and show that the competitive ratio of IDAS for OFAL}_{eq}(k,\ell) is at most 2k-1, i.e., IDAS for OFAL_{eq}(k,\ell) is best possible in all the MPFS algorithms.