Computational Complexities of University Interview Timetabling

スポンサーリンク

概要

• 論文の詳細を見る

• 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. Our task is to construct a presentation timetable of these 2n students using n timeslots and two rooms, so that two students evaluated by the same referee must be assigned to different timeslots. The optimization goal is to minimize the total number of movements of all referees between two rooms. This problem comes from the real world in the interview timetabling in Kyoto University. We propose two restricted models of this problem, and investigate their time complexities.

• （社）電子情報通信学会の論文
• 2009-02-01

著者

• KAMIYAMA Naoyuki

  Department of Information and System Engineering, Faculty of Science and Engineering, Chuo Universit

• YAMANAKA KATSUHISA

  Graduate School of Information Systems, University of Electro-communications

• Kamiyama Naoyuki

  Department Of Architecture And Architectural Engineering Kyoto University

• Katsuhisa Yamanaka

  Graduate School Of Information Systems University Of Electro-communications.

• Yamanaka Katsuhisa

  Graduate School Of Information Systems The University Of Electro-communications

• KIYONARI Yuuki

  Department of Systems Design and Informatics, Kyushu Institute of Technology

• MIYANO Eiji

  Department of Systems Design and Informatics, Kyushu Institute of Technology

• MIYAZAKI Shuichi

  Academic Center for Computing and Media Studies, Kyoto University

• Kiyonari Yuuki

  Department Of Systems Design And Informatics Kyushu Institute Of Technology

• Miyano Eiji

  Department Of Systems Design And Informatics Kyushu Institute Of Technology

• Miyazaki Shuichi

  Academic Center For Computing And Media Studies Kyoto University

• MIYANO Eiji

  Department of System Design and Informatics, Kyushu Institute of Technology

関連論文

• Enumerating All Rooted Trees Including k Leaves
• Improved Approximation Algorithms for Firefighter Problem on Trees
• Enumerating All Rooted Trees Including k Leaves
• A (2-c(logN)/N)-Approximation Algorithm for the Stable Marriage Problem(Invited Papers from New Horizons in Computing)
• Efficient Enumeration of All Pseudoline Arrangements
• 1B2 The Multicover Problem in Graphs arising from Patrol Route Planning
• An Efficient Algorithm for Evacuation Problem in Dynamic Network Flows with Uniform Arc Capacity(Invited Papers from New Horizons in Computing)
• Computational Complexities of University Interview Timetabling
• Random Generation and Enumeration of Proper Interval Graphs
• Efficient Enumeration of All Ladder Lotteries with k Bars
• Efficient Enumeration of All Pseudoline Arrangements
• The Bump Hunting Method Using the Genetic Algorithm with the Extreme-Value Statistics
• A Tight Upper Bound on Online Buffer Management for Multi-Queue Switches with Bicodal Buffers
• A Tight Bound on Online Buffer Management for Two-Port Shared-Memory Switches
• A Compact Encoding of Rectangular Drawings with Edge Lengths
• Approximating the path-distance-width for k-cocomparability graphs
• Coding Ladder Lotteries
• Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems

もっと見る 閉じる

スポンサーリンク