一般化メディアン安定結婚問題に対する乱択近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,一般化メディアン安定結婚(generalized median stable matching:GMSM)問題について議論する.GMSMは,問題構造から誘導される公平な安定マッチングとして,Teo-Sethuraman(1998)によって提案された.Cheng(2008)はi番目のGMSMを見つけることは#P困難であることを,i=O(N)の場合について示した.ただしNは入力例に対する安定マッチングの個数を表す.本稿では計算困難性に関する2つの結果を与える,ひとつはi番目のGMSMを見つけることはi=o(N^<1/c>)の場合でさえ#P困難であることを示す.ただしc≥1は任意の定数である.もうひとつは,与えられたマッチングがGMSMとして現れるか否かの判定が#P困難であることを示す.また,i番目のGMSMに対する乱択近似計算法を2つ提案する.この計算法においては,半順序集合のイデアルの近似一様ランダム生成オラクルを仮定する.
- 一般社団法人情報処理学会の論文
- 2008-10-31
著者
関連論文
- 対数優/劣モジュラ分布からのサンプリング (アルゴリズムと計算機科学の数理的基盤とその応用)
- A polynomial-time perfect sampler for the Q-Ising with local fields (アルゴリズムと計算機科学の数理的基盤とその応用--RIMS研究集会報告集)
- 頂点独立なノイズ付きQ-イジング模型のための多項式時間パーフェクトサンプラー
- グラフ・ネットワーク・OR(初学者のためのOR事例)
- コーダルグラフサンドイッチ問題とその応用
- 2-D-3 小選挙区区割画定問題に対する行政区域変化の影響分析(政策・行政)
- 一票の重みの格差から観た小選挙区数
- 1-C-11 衆議院小選挙区数に着目した一票の重みの格差是正効果(政策・行政・医療・福祉)
- 公平な小選挙区制のための数理モデル(公平な社会の数理モデル)
- 衆議院小選挙区制における一票の重みの格差の限界とその考察
- 小選挙区最適区割に基づく議員定数配分(政策・行政(1))
- 離散最適化とその応用第6回区割画定問題のモデル化と最適区割の導出
- 区割画定問題に対する数理的アプローチ(政策・行政・福祉・生活(2))
- 久保幹雄・松井知己著, 組合せ最適化[短編集], 朝倉書店, 1999年
- Algorithms for the Minimax k-Ideal Problem
- The Minimum-weight k-Ideal Problem on a Directed Tree Poset and Its Polyhedron
- 平成大合併を経た衆議院小選挙区制区割環境の変化と一票の重みの格差
- 対数優モジュラ分布からのサンプリング
- 特集にあたって(次世代ORのオープン・プロブレム)
- 最適化から観た選挙の図解(新・ORの図解,学会創立50周年記念号)
- 平成大合併を経た衆議院小選挙区制区割環境の変化と一票の重みの格差
- 平成20年春季研究発表会ルポ(情報の窓)
- マルコフ連鎖の完璧シミュレーション(超ロバスト計算原理とモデリング・シミュレーション)
- Enumeration of Graph Sandwiches (Acceleration and Visualization of Computation for Enumeration Problems)
- 一般化メディアン安定結婚問題に対する乱択近似アルゴリズム
- 1-B-3 一般化メディアン安定結婚問題に対する乱択近似アルゴリズム(アルゴリズム)
- マルコフ連鎖モンテカルロ法における近似精度保証と完璧サンプリング法(研究会推薦博士論文速報)
- コーダルサンドイッチの列挙, ランダム生成, 数え上げについて (理論計算機科学の深化 : 新たな計算世界観を求めて)
- On the Limits of the Reduction in Population Disparity Between Single-Member Election Districts in Japan