TIToshiya Itoh

Toshiya Itoh

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    Near-Optimal Deterministic Online Transportation

    by Tsubasa Harada, Toshiya Itoh

    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.

  • Open Access

    Mechanism Design for Mobility

    by Tsubasa Harada, Toshiya Itoh, Shigeo Matsubara, Shuichi Miyazaki, Makoto Yokoo

    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.

  • Open Access

    Popularity on the 3D-Euclidean Stable Roommates

    by Steven Ge, Toshiya Itoh

    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

    by Tsubasa Harada, Toshiya Itoh

    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

    by Suthee Ruangwises, Toshiya Itoh

    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

    by Suthee Ruangwises, Toshiya Itoh

    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

    by Tsubasa Harada, Toshiya Itoh, Shuichi Miyazaki

    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.