4 papers · 1 filter
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…
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…