Polymatroid

From Wikipedia, the free encyclopedia

In mathematics, polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970.^[1]

Definition

Consider any submodular set function $f$ on $S$ . Then define two associated polyhedra.

$EP_{f}:=\{x\in {\mathbb {R}}^{S}|\sum _{{e\in U}}x(e)\leq f(U),\forall U\subseteq S\}$
$P_{f}:=EP_{f}\cap \{x\in {\mathbb {R}}^{S}|x\geq 0\}$

Here $P_{f}$ is called the polymatroid and $EP_{f}$ is called the extended polymatroid associated with $f$ .^[2]

$P_{f}$ is nonempty if and only if $f\geq 0$ and that $EP_{f}$ is nonempty if and only if $f(\emptyset )\geq 0$
Given any extended polymatroid $EP$ there is a unique submodular function $f$ such that $f(\emptyset )=0$ and $EP_{f}=EP$
If r is integral, 1-Lipschitz, and $r(\emptyset )=0$ then r is the rank-function of a matroid, and the polymatroid is the independent set polytope, so-called since Edmonds showed it is the convex hull of the characteristic vectors of all independent sets of the matroid.
For a supermodular f one analogously may define the contrapolymatroid

$w\in {\mathbb {R}}_{+}^{E}:\forall S\subseteq E,\sum _{{e\in S}}w(e)\geq r(S)$

This analogously generalizes the dominant of the spanning set polytope of matroids.

↑ 1.0 1.1 1.2 1.3 Edmonds, Jack. Submodular functions, matroids, and certain polyhedra. 1970. Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) pp. 69–87 Gordon and Breach, New York. MR 0270945
↑ (Schrijver 2003, §44, p. 767)

Schrijver, Alexander (2003), Combinatorial Optimization, Springer, ISBN 3-540-44389-4
Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge University Press, ISBN 0-521-01012-8
Fujishige, Saruto (2005), Submodular Functions and Optimization, Elsevier, ISBN 0-444-52086-4
Narayanan, H. (1997), Submodular Functions and Electrical Networks, ISBN 0-444-82523-1

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.