Substitutes and Complements in Network Flow Problems.
CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Pagination or Media Count:
If f is a function of several variables, one calls a pair of variables substitutes complements if the change of the value of the function when both variables are increased is at most at least equal to the sum of the changes when each is increased separately. We here consider the case where f is the value of a maximum weight circulation on a network and the variables are the upper and lower bounds and the weights of a pair of arcs. We introduce a simple combinatorial criterion for two arcs to be in series or parallel and show that these two cases correspond to the variables being complements or substitutes respectively. This generalizes results of Shapley for the special case of the maximum flow and optimal assignment problems. We also show that our result is best possible in that if two arcs are neither in series nor parallel, then the corresponding variables can be either substitutes or complements or both. Author
- Statistics and Probability