caa a22 4500 475750357 CHVBK 20180406123521.0 cr unu---uuuuu 170329e20000901xx s 000 0 eng 10.1023/A:1008720430012 doi (NATIONALLICENCE)springer-10.1023/A:1008720430012 Scheduling Classes on a College Campus [Elektronische Daten] [Perry Fizzano, Steven Swanson] We consider the problem of scheduling a set of classes to classrooms with the objective of minimizing the number of classrooms used. The major constraint that we must obey is that no two classes can be assigned to the same classroom at the same time on the same day of the week. We present an algorithm that produces a nearly optimal schedule for an arbitrary set of classes. The algorithm's first stage produces a packing of classes using a combination of a greedy algorithm and a non-bipartite matching and the second stage consists of a bipartite matching. First we show that for one variant of the problem our algorithm produces schedules that require a number of classrooms that is always within a small additive constant of optimal. Then we show that for an interesting variant of the problem the same algorithm produces schedules that require a small constant factor more classrooms than optimal. Finally, we report on experimental results of our algorithm using actual data and also show how to create schedules with other desirable characteristics. Kluwer Academic Publishers, 2000 timetabling nationallicence bipartite matching nationallicence assignment nationallicence approximation algorithm nationallicence Fizzano Perry Department of Mathematics, Computer Science University of Puget Sound, 98416, Tacoma, WA, USA aut Swanson Steven Department of Mathematics, Computer Science University of Puget Sound, 98416, Tacoma, WA, USA aut Computational Optimization and Applications Kluwer Academic Publishers 16/3(2000-09-01), 279-294 0926-6003 16:3<279 2000 16 10589 https://doi.org/10.1023/A:1008720430012 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1008720430012 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fizzano Perry Department of Mathematics, Computer Science University of Puget Sound, 98416, Tacoma, WA, USA aut NATIONALLICENCE 700 1- Swanson Steven Department of Mathematics, Computer Science University of Puget Sound, 98416, Tacoma, WA, USA aut NATIONALLICENCE 773 0- Computational Optimization and Applications Kluwer Academic Publishers 16/3(2000-09-01), 279-294 0926-6003 16:3<279 2000 16 10589 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer