Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects

• 岩間, 一雄

  Graduate School of InformaticsKyoto University

• 宮崎, 修一

  Academic Center for Computing and Media StudiesKyoto University

• 柳澤, 弘揮

  IBM Research

抄録

Manlove and O’Malley [9] proposed the Student-Project Allocation Problem with Preferences over Projects (SPA-P). They proved that the problem of finding a maximum stable matching in SPA-P is APX-hard and gave a polynomial-time 2-approximation algorithm. In this paper, we give an improved upper bound of 1.5 and a lower bound of 21/19 (>1.1052)21/19 (>1.1052) .

'Theory and Applications of Models of Computation' 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings

収録刊行物

• Lecture Notes in Computer Science

  Lecture Notes in Computer Science 6648 440-451, 2011

  Springer Berlin Heidelberg

詳細情報

• CRID: 1050282810826145792
• NII論文ID: 120006338072
• ISSN: 03029743
• HANDLE: 2433/226946
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles