Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose there is a submodular function $f$ over a ground set $V$ with cardinality $|V| = n$.

Let $x \in \mathbb{R}^V$ is a function.
Define $x(S) = \sum_{v \in S} x(v)$
I define a polyhedron in n-dimensional space as follows :

$$P(f) = \{x \in \mathbb{R}^V | x(S) \leq f(S)\;\; \forall S\subseteq V\;\; \} $$

I further define a base polyhedron :

$$ B(f) = \{ x \in P(f) | x(V) = f(V) \}$$

Each point on the base polyhedron is called a base. Now, the task is to find an extreme base on the base polyhedron. These can be generated efficiently using a greedy algorithm by Edmond.

Now, for some reason that I do not understand, it is said that the problem can be formulated as an LP :

$$ max\;\; w^Tx\;\; subject\;\; to\;\; x \in B(f)$$

I don't understand, how solving the above is equivalent to finding extreme bases. What are the weights w. It is described as

The problem of identifying whether B(f) is bounded by a line orientation w, ||w|| = 1, and if so how to find a point $x \in B(f) $ which touches this line

This seems somehow related to the greedy algorithm on weighted matroids which I am also unfamiliar with.

share|improve this question
I think in the definition of $x(S)$ you probably want to sum over $v\in S$ –  gfes Jun 27 '11 at 8:50
@gfes Oh sorry yeah. I'll correct it –  AnkurVijay Jun 27 '11 at 9:05
Extreme bases are vertices in the polyhedron $B(f)$. And for any poyhedron, $\max w^Tx$ is obtained at vertices for all $w$ (whenever max exists). With the way these polyhedra are defined, we can see that this max exists if and only if $w \geq 0$. –  polkjh Mar 2 '13 at 15:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.