Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11427186_31 | WEA |
Keywords | Field | DocType |
cut-based heuristic,approximability result,periodic event scheduling problem,deterministic combinatorial polynomial time,traffic light scheduling,feasible periodic railway timetable,periodic railway timetable construction,maximum number,key issue,real-world instance,scheduling problem,satisfiability | Mathematical optimization,Heuristic,Traffic signal,Algorithmics,Computer science,Scheduling (computing),Algorithm,Schedule,Periodic event scheduling problem,Time complexity,Periodic graph (geometry) | Conference |
Volume | ISSN | ISBN |
3503 | 0302-9743 | 3-540-25920-1 |
Citations | PageRank | References |
6 | 0.74 | 9 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Liebchen | 1 | 325 | 28.64 |