Successive shortest paths: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 2: | Line 2: | ||
'''Invariant:''' | '''Invariant:''' | ||
The capacity constraints are fulfilled. | # The capacity constraints are fulfilled, that is, <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>. | ||
# The '''balance discrepancy''' of each node <math>v\in V</math> is '''underestimating''', that is, | |||
'''Variant:''' | '''Variant:''' | ||
The '''balance discrepancy''' strictly decreases, that is, the value | The '''balance discrepancy''' strictly decreases, that is, the value | ||
:<math>\sum_{v\in V}\left|\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)-b(v)\right|</math>. | :<math>\sum_{v\in V}\left|\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)-b(v)\right|</math>. | ||
'''Induction basis:''' | |||
'''Abstract view:''' | |||
Start with an arbitrary value <math>f(a)\in[0\ldots u(a) | |||
Revision as of 08:02, 23 October 2014
Abstract view
Invariant:
- The capacity constraints are fulfilled, that is, [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] for all [math]\displaystyle{ a\in A }[/math].
- The balance discrepancy of each node [math]\displaystyle{ v\in V }[/math] is underestimating, that is,
Variant: The balance discrepancy strictly decreases, that is, the value
- [math]\displaystyle{ \sum_{v\in V}\left|\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)-b(v)\right| }[/math].
Induction basis:
Abstract view: Start with an arbitrary value <math>f(a)\in[0\ldots u(a)