This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Fujishige, S. Articles by Nagano, K.

A Structure Theory for the Parametric Submodular Intersection Problem

Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan
Department of Mathematical and Computing Sciences, Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Tokyo 152-8552, Japan
fujishig{at}kurims.kyoto-u.ac.jp
nagano{at}is.titech.ac.jp

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.

Key Words: submodular functions; polymatroid intersection; polytopes
History: Received: April 1, 2008; revision received: March 11, 2009;