TR-2001-09

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.



Abstract

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:

@techreport{egres-01-09,
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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-09}
}


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