安定結婚問題

404 Blog Not Found:アルゴリズム - 合コンの効用を最大化する
安定結婚問題が取上げられているので情報の添加.

Iwama, K., Manlove, D. F., Miyazaki, S. and Morita, Y. “Stable Marriage with Incomplete Lists and Ties” (ICALP 99) によれば, リストに異性全員を書かず (結婚したくない人は書かないと), またランク付けに同着を許すような条件緩和型安定結婚問題はNP困難である.

結婚における現実的な条件を考えると問題が急に難しくなる場合があるわけですね. あら大変.