document: Node-capacitated ring routing 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 nonnegative node weights . For rings , this -LRB- straightforward -RRB- 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 -LRB- 0-1-2 -RRB- - valued node weights , a requirement that 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 that 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
doc_bio_tags: O O O O O O O O O O O B I I O O O B I O O O O O O O O O B I O O O O O O O O O B I O O O O O O O O O O O O O O O B I O O O O O B I O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O
extractive_keyphrases: undirected ring network fractional relaxation feasibility problem undirected graphs distance inequality distance functions nonnegative node weights
abstractive_keyphrases: node-capacitated routing problem node-capacitated ring routing node-capacitated multicommodity flow problem farkas lemma node capacity integrality double-cut condition integer-valued node capacities half-integral multicommodity flow integer-valued multicommodity flow combinatorial strongly polynomial algorithm violating double-cut edge-cut criterion