I am reading this classic paper by Klein, Plotkin and Rao titled Excluded Minors, Network Decomposition and Multicommodity Flow.

In section 3, Theorem 3.1, they define $\hat \ell(vw) = \lceil \ell(vw)/C\rceil$, where $C$ is the sum of capacities of edges, and $\ell: E \to \mathbb R^+$ is a length function.
$dist_\ell(s_i, t_i)$ is the shortest path length from $s_i$ to $t_i$ w.r.t. $\ell$, and $dist_\hat \ell(s_i, t_i)$ is w.r.t. $\hat \ell$.
Also, there is a constraint that $\sum_{vw \in E} \ell(uw) u(vw) = 1$, where $u(vw)$ is the nonnegative capacity of the edge. (So $\sum_{vw \in E} u(vw) = C$)

Then they claim that:

  1. $dist_\ell (s_i, t_i) \le (1/C)dist_\hat \ell (s_i, t_i)$
  2. $\sum_{vw \in E} \hat \ell(vw) u(vw) \le 2C$

However, ignoring non-integral parts, it is the case that $\hat \ell(vw) \approx (1/C) \ell(vw)$. So, it seems to me that the inequalities should have "$C$s on the other sides", or the $\hat \ell$ should have been defined as $\hat \ell (vw) = \lceil C \cdot \ell(vw) \rceil$.

Can anyone explain this to me?

  • $\begingroup$ Sometimes papers contain mistakes. $\endgroup$ – Yuval Filmus Jan 20 '16 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.