一般注記出版タイプ： VoR
Matching under preferences is one of the most actively studied problems in theoretical computer science. The general objective of this problem is to match people with other people or with items, while each person has a list that ranks other people or items in order of preference. Two measures of optimality have been widely studied: popularity and stability. A matching is popular if it does not lose in a head-to-head election against any other matching. A matching is stable if there is no pair of people that are not matched to each other but prefer each other to their own partners.
In this thesis, we investigate three open problems related to popular and stable matchings using graph-theoretic characterizations. In the first problem, we study a probability that a popular matching exists in a random instance. In the second problem, we present an algorithm to measure badness of a matching that is not popular. In the third problem, we develop an algorithm to find a matching that has a property close to that of a stable matching and does not cross itself geometrically.
identifier:oai:t2r2.star.titech.ac.jp:50535285
連携機関・データベース国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
提供元機関・データベース東京科学大学 : 東京科学大学リサーチリポジトリ(T2R2)