TY - JOUR
T1 - Substitutes and complements in network flows viewed as discrete convexity
AU - Murota, Kazuo
AU - Shioura, Akiyoshi
N1 - Funding Information:
The authors thank anonymous referees for their valuable comments on the manuscript. This work is supported by Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology of Japan.
PY - 2005/9
Y1 - 2005/9
N2 - We study combinatorial properties of the optimal value function of the network flow problem. It is shown by Gale-Politof [Substitutes and complements in networks flow problems, Discrete Appl. Math. 3 (1981) 175-186] that the optimal value function has submodularity and supermodularity w.r.t. problem parameters such as weights and capacities. In this paper we shed a new light on this result from the viewpoint of discrete convex analysis to point out that the submodularity and supermodularity are naturally implied by discrete convexity, called M-convexity and L-convexity, of the optimal value function.
AB - We study combinatorial properties of the optimal value function of the network flow problem. It is shown by Gale-Politof [Substitutes and complements in networks flow problems, Discrete Appl. Math. 3 (1981) 175-186] that the optimal value function has submodularity and supermodularity w.r.t. problem parameters such as weights and capacities. In this paper we shed a new light on this result from the viewpoint of discrete convex analysis to point out that the submodularity and supermodularity are naturally implied by discrete convexity, called M-convexity and L-convexity, of the optimal value function.
KW - Combinatorial optimization
KW - Discrete convexity
KW - Network flow
KW - Submodularity
UR - http://www.scopus.com/inward/record.url?scp=27144494590&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=27144494590&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2005.04.002
DO - 10.1016/j.disopt.2005.04.002
M3 - Article
AN - SCOPUS:27144494590
SN - 1572-5286
VL - 2
SP - 256
EP - 268
JO - Discrete Optimization
JF - Discrete Optimization
IS - 3
ER -