A Structure Theory for the Parametric Submodular Intersection Problem

• 成果类型: Article
• 署名作者: Fujishige, Satoru; Nagano, Kiyohito
• 署名单位: Kyoto University; Institute of Science Tokyo; Tokyo Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1090.0395
• 发表日期: 2009
• 页码: 513-521
• 关键词: function minimization; maximum flow; algorithm

摘要

A linearly parameterized polymatroid intersection problem appears in the context of principal partitions. We consider a submodular intersection problem on a pair of strong-map sequences of submodular functions, which is an extension of the linearly parameterized polymatroid intersection problem to a nonlinearly parameterized one. We introduce the concept of a basis frame on a finite nonempty set of cardinality n that gives a mapping from the set of all base polyhedra in n-dimensional space into n-dimensional vectors such that each base polyhedron is mapped to one of its bases. We show the existence of a simple universal representation of all optimal solutions of the parameterized submodular intersection problem by means of basis frames.