TY - CONF A1 - Tesch, Alexander T1 - A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n) T2 - Principles and Practice of Constraint Programming (CP 2016) N2 - In constraint programming, energetic reasoning constitutes a powerful start time propagation rule for cumulative scheduling problems (CuSP). In this paper, we first present an improved time interval checking algorithm that is derived from a polyhedral model. In a second step, we extend this algorithm to an energetic reasoning propagation algorithm with complexity O(n^2 log n) where n denotes the number of jobs. The key idea is based on a new sweep line subroutine that efficiently evaluates the relevant time intervals for all jobs. In particular, our algorithm yields at least one possible energetic reasoning propagation for each job. Finally, we show that on the vast number of relevant time intervals our approach yields the maximum possible propagation according to the energetic reasoning rule. Y1 - 2016 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6206 VL - 22 SP - 493 EP - 519 ER -