2
$\begingroup$

I know why and how the push relabel algorithm works for solving the max-flow problem. But why is a global update step required?

$\endgroup$

migrated from cstheory.stackexchange.com Jul 19 '12 at 2:10

This question came from our site for theoretical computer scientists and researchers in related fields.

3
$\begingroup$

Global relabeling is not required; it's an optimization. In the push-relabel paper, Goldberg and Tarjan describe a parallel version not amenable to such an update. The kind of performance problem global relabeling addresses is when two nodes u and v with surplus and residual arcs to one another become disconnected from the sink in the residual graph. The local relabeling rule can only increase u's label to one more than v's, and vice versa, so surplus is pushed back and forth and the labels slowly count up until the maximum of n is reached. Now imagine if this happens to a dense subgraph with many nodes.

By alternating m steps of push/relabel with global updates, the running time at worst goes up by a constant factor but in practice typically goes down, by a lot. The best implementations of push-relabel use gap relabeling as well as global relabeling. Both heuristics are described, with some experiments, by Cherkassky and Goldberg.

$\endgroup$
  • $\begingroup$ What is the main observation for global relabeling? I mean what motivates this heuristic? $\endgroup$ – username_4567 Jul 20 '12 at 11:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.