Accession Number:

ADA526806

Title:

The Structure of Optimal Solutions to the Submodular Function Minimization Problem

Descriptive Note:

Technical rept.

Corporate Author:

MINNESOTA UNIV MINNEAPOLIS INST FOR MATHEMATICS AND ITS APPLICATIONS

Personal Author(s):

Report Date:

2003-06-23

Pagination or Media Count:

25.0

Abstract:

In this paper, we study the structure of optimal solutions to the submodular function minimization problem. We introduce prime sets and pseudoprime sets as basic building block of minimizer sets, and investigate composition, decomposition, recognition, and certification of prime sets. We show how Schrijvers submodular function minimization algorithm can be modified to construct in polynomial time a prime or pseudoprime decomposition of the ground set. We also show that the final vector x obtained by this algorithm is an extreme point of the polyhedron P x epsilon Rv x less than or equal to 0 xA less than or equal to fA for all A reflex subset contained in V.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE