| Presentation | 2006-06-23 On the Computational Complexity of Interview Timetabling Problems Yuuki KIYONARI, Eiji MIYANO, Shuuichi MIYAZAKI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This paper introduces a new timetabling problem on universities, called interview timetabling. In this problem, some constant number, say, three, of referees are assigned to each of 2n graduate students. It requires to assign these students to an n×2 array, consisting of n timeslots and two rooms, so that two students sharing the same referee must be assigned to different timeslots. Furthermore, we want to minimize the total number of movements of all referees between two rooms. This is a problem actually having arisen in the interview timetabling in Kyoto University. We propose two restricted models of this problem, and investigate their time complexity. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Interview timetabling / optimization problem / computational complexity |
| Paper # | COMP2006-18 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2006/6/16(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the Computational Complexity of Interview Timetabling Problems |
| Sub Title (in English) | |
| Keyword(1) | Interview timetabling |
| Keyword(2) | optimization problem |
| Keyword(3) | computational complexity |
| 1st Author's Name | Yuuki KIYONARI |
| 1st Author's Affiliation | Department of Systems Innovation and Informatics, Kyushu Institute of Technology() |
| 2nd Author's Name | Eiji MIYANO |
| 2nd Author's Affiliation | Department of Systems Innovation and Informatics, Kyushu Institute of Technology |
| 3rd Author's Name | Shuuichi MIYAZAKI |
| 3rd Author's Affiliation | Academic Center for Computing and Media Studies, Kyoto University |
| Date | 2006-06-23 |
| Paper # | COMP2006-18 |
| Volume (vol) | vol.106 |
| Number (no) | 128 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |