Approximate algorithms for time separations of events

We describe a polynomial-time approximate algorithm for computing minimum and maximum time separations be-tween all pairs of events in systems specified by acyclic tim-ing constraint graphs. Even for acyclic graphs, the prob-lem is NP-complete. We propose finding an approximate so-lution by first approximating the non-convex feasible space with a suitable convex “envelope”, and then solving the problem efficiently in the approximate convex space. Un-like previous works, our algorithm can handle both min and max type timing constraints in the same system, and has a computational complexity that is polynomial in the number of events. Although the computed separations are conserva-tive in the worst-case, experiments indicate that our results are highly accurate in practice. 1