3 citations · 6 across the 11 of their papers we have counts for
12 papers
Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
Sota Kawase, Shuichi Miyazaki
The Seat Arrangement Problem is a problem of finding a desirable seat arrangement for given preferences of agents and a seat graph that represents a configuration of seats. In this…
Marriage and Roommate
Kazuo Iwama, Shuichi Miyazaki
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…
Capacity-Insensitive Algorithms for Online Facility Assignment Problems on a Line
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 a…
Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas
Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi
To mitigate the imbalance in the number of assignees in the Hospitals/Residents problem, Goko et al. [Goko et al., Maximally Satisfying Lower Quotas in the Hospitals/Residents Prob…
Refined Computational Complexities of Hospitals/Residents Problem with Regional Caps
Koki Hamada, Shuichi Miyazaki
The Hospitals/Residents problem (HR) is a many-to-one matching problem whose solution concept is stability. It is widely used in assignment systems such as assigning medical studen…
Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties
Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki +1
Motivated by the serious problem that hospitals in rural areas suffer from a shortage of residents, we study the Hospitals/Residents model in which hospitals are associated with lo…
Competitive Analysis for Two Variants of Online Metric Matching Problem
Toshiya Itoh, Shuichi Miyazaki, Makoto Satake
In this paper, we study two variants of the online metric matching problem. The first problem is the online metric matching problem where all the servers are placed at one of two p…
Strongly Stable and Maximum Weakly Stable Noncrossing Matchings
Koki Hamada, Shuichi Miyazaki, Kazuya Okamoto
In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are…
An FPT Algorithm for Max-Cut Parameterized by Crossing Number
Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki +1
The Max-Cut problem is known to be NP-hard on general graphs, while it can be solved in polynomial time on planar graphs. In this paper, we present a fixed-parameter tractable algo…
Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists
Koki Hamada, Shuichi Miyazaki, Hiroki Yanagisawa
In the stable marriage problem (SM), a mechanism that always outputs a stable matching is called a stable mechanism. One of the well-known stable mechanisms is the man-oriented Gal…
Stable Nash Equilibria in the Gale-Shapley Matching Game
Sushmita Gupta, Kazuo Iwama, Shuichi Miyazaki
In this article we study the stable marriage game induced by the men-proposing Gale-Shapley algorithm. Our setting is standard: all the lists are complete and the matching mechanis…
Better Bounds for Online -Frame Throughput Maximization in Network Switches
Jun Kawahara, Koji M. Kobayashi, Shuichi Miyazaki
We consider a variant of the online buffer management problem in network switches, called the -frame throughput maximization problem (-FTM). This problem models the situation…