## Keywords (6)

Publications
Flow Formulations for the Student Scheduling Problem

# Flow Formulations for the Student Scheduling Problem,10.1007/978-3-540-45157-0_20,Eddie Cheng,Serge Kruk,Marc J. Lipman

Flow Formulations for the Student Scheduling Problem
We discuss the student scheduling problem as it generally applies to high-schools in North-America. We show that the problem is NP-hard and discuss various variations to its formulation. We focus on multi-commodity o w problems because there has recently been much work and a number of interesting results on approximates solutions to such problems.
View Publication
 The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
More »

## Citation Context (4)

• ...Cheng et al. (2003) formulated a student timetabling problem as a multi-commodity flow problem...

### Salem M. Al-Yakoob, et al. A mixed-integer mathematical modeling approach to exam timetabling

• ...Cheng, Kruk & Lipman [3] discuss the Student Scheduling Problem (SSP) as it generally applies to high schools in North America...

### John Van Den Broek, et al. Timetabling Problems at the TU Eindhoven

• ...The student scheduling problem [4] (SSP) has the same objective: providing conflict-free schedules...
• ...Actually, our problem can be seen as a specific demand driven timetabling problem [4] where the number of satisfied course requests is to be maximized...

### Hadrien Cambazard, et al. Interactively Solving School Timetabling Problems Using Extensions of ...

• ...ity of Order, it is easy to see that Order(s,t) is polynomial-time solvable for s 2. We show that (iii) Order(3,1) is in P...
• ...Hence, at this moment, a constructed instance is of Room(2,3)...
• ...In this section we present a polynomial-time algorithm to find an optimal solution for Order(3,1)...
• ...Theorem 3. Order(3,1) is in P. (Proof is omitted.)...
• ...In this paper, we considered the time complexity of Room(s,t) and Order(s,t) for several values of s and t. The apparent next step in this research is to investigate the complexity of Room(3,1) and Order(4,1)...

## References (20)

### AN ε-RELAXATION METHOD FOR SEPARABLE CONVEX COST NETWORK FLOW PROBLEMS1(Citations: 8)

Published in 1997.

### A polyhedral approach to an integer multicommodity flow problem(Citations: 12)

Journal: Discrete Applied Mathematics - DAM , vol. 101, no. 1-3, pp. 13-36, 2000

### A partitioned-relaxation algorithm for separable convex network flow problems(Citations: 5)

Published in 1999.

### Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming(Citations: 1153)

Journal: Journal of The ACM - JACM , vol. 42, no. 6, pp. 1115-1145, 1995
Sort by:

## Citations (4)

### A mixed-integer mathematical modeling approach to exam timetabling(Citations: 2)

Journal: Computational Management Science , vol. 7, no. 1, pp. 19-46, 2010

### Timetabling Problems at the TU Eindhoven(Citations: 5)

Journal: Electronic Notes in Discrete Mathematics , vol. 25, pp. 210-227, 2006