TY - GEN A1 - Liebchen, Christian T1 - A Cut-based Heuristic to Produce Almost Feasible Periodic Railway Timetables N2 - We consider the problem of satisfying the maximum number of constraints of an instance of the Periodic Event Scheduling Problem (PESP). This is a key issue in periodic railway timetable construction, and has many other applications, e.g. for traffic light scheduling. We generalize two (in-) approximability results, which are known for MAXIMUM- K-COLORABLE-SUBGRAPH. Moreover, we present a deterministic combinatorial polynomial time algorithm. Its output violates only very few constraints for five real-world instances. Y1 - 2005 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/229 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-2297 ER -