Node-capacitated ring routing

András Frank, Bruce Shepherd, Vivek Tandon, Zoltán Végh

Published in:
Mathematics of Operations Research 27 (2002) 372-383.


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-09}

Last modification: 29.12.2020. Please email your comments to Tamás Király!