Algorithms and Graph-Theoretic Characterizations of Problems in Matching Under Preferences

Digital data available（東京工業大学リサーチリポジトリ）

学術機関リポジトリデータベース（IRDB）（機関リポジトリ）

Algorithms and Graph-Theoretic Characterizations of Problems in Matching Under Preferences

Material type: 博士論文

Author: Ruangwises, Sutheeほか

Publisher: -

Publication date: 2020-09

Material Format: Digital

Capacity, size, etc.: -

Name of awarding university/degree: 東京工業大学,博士(理学)

View All

Notes on use

Note (General)：: Matching under preferences is one of the most actively studied problems in theoretical computer science. The general objective of this problem is to m...

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

Tokyo Tech Research Repository
Digital
You can check the holdings of institutions and databases with which Institutional Repositories DataBase(IRDB)(Institutional Repository) is linked at the site of Institutional Repositories DataBase(IRDB)(Institutional Repository).
Tokyo Tech Research Repository

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 博士論文
Title: Algorithms and Graph-Theoretic Characterizations of Problems in Matching Under Preferences
Author/Editor: Ruangwises, Suthee
RUANGWISES, Suthee
Author Heading: Ruangwises, Suthee
RUANGWISES, Suthee
Publication Date: 2020-09
Publication Date (W3CDTF): 2020-09
Degree grantor/type: 東京工業大学
Date Granted: 2020-09-25
Dissertation Number: 甲第11573号
Degree Type: 博士(理学)
Text Language Code: eng
Subject Heading: matching under preferences, popular matching, stable matching, noncrossing matching
Target Audience: 一般
Note (General): 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
Format (IMT): application/pdf
Source: fulltext
http://t2r2.star.titech.ac.jp/rrws/file/CTT100830349/ATD100000413/thesis_17D38055_RuangwisesSuthee.pdf
Access Restrictions: インターネット公開
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 東京工業大学 : 東京工業大学リサーチリポジトリ