We describe a polynomial-time approximate algorithm for computing
minimum and maximum time separations between all pairs of events in
systems specified by acyclic timing constraint graphs. Even for
acyclic graphs, the problem is NP-complete. We propose finding an
approximate solution by first approximating the non-convex feasible
space with a suitable convex ``envelope'', and then solving the
problem efficiently in the approximate convex space. Unlike 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 conservative in the worst-case, experiments indicate that our
results are highly accurate in practice.