最大サイズ最大安定度マッチング問題に対する近似下限の改良

• Material Type: 文書・図像類
• Title: 最大サイズ最大安定度マッチング問題に対する近似下限の改良
• Author/Editor: 濱田, 浩気; 宮崎, 修一; 岩間, 一雄
• Author Heading: 濱田, 浩気; 宮崎, 修一; 岩間, 一雄
• Publication, Distribution, etc.: 電子情報通信学会
• Publication Date: 2009-10-09
• Publication Date (W3CDTF): 2009-10-09
• Alternative Title: An Improved Approximation Lower Bound for Maximum Cardinality Almost Stable Matching Problem
• Periodical title: 電子情報通信学会技術研究報告
• No. or year of volume/issue: 109 235
• Volume: 109
• Issue: 235
• Pages: 35-40
• ISSN (Periodical Title): ISSN : 0913-5685
• Text Language Code: jpn
• Alias of Author: ハマダ, コウキ; ミヤザキ, シュウイチ; イワマ, カズオ
• Subject Heading: 安定結婚問題; 近似アルゴリズム; 近似度; 多項式時間変換; the stable marriage problem; approximation algorithms; approximation ratio; polynomial-time reduction
• Target Audience: 一般
• Note (General): <コンピュテーション研究会(COMP)> 2009年10月16日(金) 10:00 - 16:35, 東北大学 青葉山キャンパス 電子情報システム・応物系 南講義棟103講義室
• Format (IMT): application/pdf
• Source: IEICE_tec.rep_COMP2009-37.pdf （fulltext）; http://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/227006/1/IEICE_tec.rep_COMP2009-37.pdf
• Access Restrictions: インターネット公開
• Rights (production): ©2009 by IEICE
• Periodical Title (NCID): AN10013152; https://ci.nii.ac.jp/ncid/AN10013152
• Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）; https://irdb.nii.ac.jp
• Original Data Provider (Database): 京都大学 : 京都大学学術情報リポジトリ

• Summary, etc.: 安定結婚問題で不完全希望リストを許すと, 同じ例題に対する全ての安定マッチングは同サイズになる.しかし, 安定性を無視すると, 一般にはそれよりも大きなサイズのマッチングが存在する.Biroらは, 最大サイズのマッチングの中で出来るだけブロッキングペア数の少ないマッチングを求める問題を提案した.彼ら...