C inv C val C val min Without C' Determining C':  In the standard network flow graph Discretized Network Flow (contd) Heuristically select a valid flow & determine its cost C val Theorem [Ren et al., ICCAD'08]: A min-cost flow with C'-costs on MEA arcs ensures MEA satisfaction Obtain min-cost flow of cost C inv min w/o discretization constraints Set C'=C val -C inv min +1 Since C' inv ≥C' val +C', a valid flow is guaranteed to have a smaller cost than any invalid flow.
{}