A constructive proof for the induction of M-convex functions through networks

✍ Scribed by A. Shioura

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 414 KB
• Volume: 82
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00089-9

✦ Synopsis

Murota ( I995

) introduced an M-convex function as a quantitative generalization of the set of integral vectors in an integral base polyhedron as well as an extension of valuated matroid over base polyhedron. Just as a base polyhedron can be transformed through a network. an M-convex function can be induced through a network. This paper gives a constructive proof for the induction of an M-convex function. The proof is based on the correctness of a simple algorithm, which finds an exchangeable element. We also analyze a behavior of induced functions when they take the value --x.