|
Published in:
We consider the node-capacitated routing problem in
an undirected ring network along with its fractional relaxation, the
node-capacitated multicommodity flow problem. For the feasibility
problem, Farkas' lemma provides a characterization for general
undirected graphs asserting roughly that there exists such a flow if
and only if the so-called distance inequality holds for every choice
of distance functions arising from non-negative node-weigths. For
rings this (straightforward) result will be improved in two ways. We
prove that, independent of the integrality of node-capacities, it
suffices to require the distance inequality only for distances arising
from (0-1-2)-valued node-weights, a requirement which will be called
the double-cut condition. Moreover, for integer-valued
node-capacities, the double-cut condition implies the existence of a
half-integral multicommodity flow. In this case there is even an
integer-valued multicommodity flow which violates each node-capacity
by at most one.
Our approach gives rise to a combinatorial, strongly polynomial
algorithm to compute either a violating double-cut or a
node-capacitated multicommodity flow. A relation of the problem to
its edge-capacitated counterpart will also be explained.
Bibtex entry:
| AUTHOR | = | {Frank, Andr{\'a}s and Shepherd, Bruce and Tandon, Vivek and V{\'e}gh, Zolt{\'a}n}, |
| TITLE | = | {Node-capacitated ring routing}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2001}, |
| NUMBER | = | {TR-2001-09} |