マッチングモデルと離散凸解析を用いたその拡張 : アルゴリズムの観点から(セッション2)
スポンサーリンク
概要
- 論文の詳細を見る
研修医の病院への配属, 労働者への仕事の配分など異なる2つの集合間の割当を扱うモデルをここではマッチングモデルと総称することにする.マッチングモデルにはGaleとShapleyによる安定結婚モデルとShapleyとShubikによる割当モデルという標準的な2つのモデルが提案されている.これらのモデルでは割当についてある種の安定性を定義し, 安定割当の存在, 安定割当の束構造などの良い性質が議論されている.一方, 離散凸解析を用いることでこれらのモデルの拡張が試みられ, 安定割当の存在も示されている.本講演では, 安定割当を求めるアルゴリズムあるいはその計算量という観点から, 上記のモデルやその拡張について概説する.
- 一般社団法人情報処理学会の論文
- 2006-01-20
著者
関連論文
- 1-F-10 Existence of sports schedules with multiple venues
- パーフェクト双向グラフ(グラフ・ネットワーク(3))
- On the Local Face Structure of 0-1 Polytopes Related to a Class of Combinatorial Optimizaiton Problems
- Adjacency of the Best and Second Best Valued Solutions in Combinatorial Optimization Problems
- Algorithms for Finding a Kth Best Valued Assignment
- A Recursive Algorithm for a Class of Convex Min-Max Problems
- ON GROTSCHEL-LOVASZ-SCHRIJVER'S RELAXATION OF STABLE SET POLYTOPES
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- A LINEAR TIME ALGORITHM FOR THE GENERALIZED STABLE SET PROBLEM ON TRIANGULATED BIDIRECTED GRAPHS
- 確率モデルにおける最適化研究部会終了報告(ペーパーフェア)
- 制限付き安定部屋割問題とミニマックス安定部屋割問題(組合せ・グラフ・ネットワーク)
- The Rooted Tree Embedding Problem
- A property of the divorce digraph for a stable marriage
- マッチングモデルと離散凸解析を用いたその拡張 : アルゴリズムの観点から(セッション2)
- マッチングモデル(モデリング-最適化モデリング-)
- 第22回FMESシンポジウム「デジタル・エンジニアリングと経営工学」(情報の窓)
- 安定結婚からサプライチェーンネットワークの安定性へ(離散凸解析)
- 2-B-4 サプライチェーンネットワークの安定性(離散最適化(5))