I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.

The answer is probably negative. But my problem at hand is simply the shortest path problem.

Consider a graphical model with two variables

$$X - Y$$

Both $X$ and $Y$ can take one of the two states $\{1,2\}$. The task is to find the assignment of $X$ and $Y$ that minimizes

$$ f(X,Y) = \sum_{i=1}^2 \sum_{j=1}^2 T_{ij} \cdot [X=i \ \&\& \ Y=j]. $$

$T_{ij} \ge 0$ are given parameters. $[x]=1$ if $x$ is true, and $0$ otherwise. More generally we can have longer chains and more states, solvable by the Baum-Welch algorithm.

Question: is it possible to formulate this problem as a submodular minimization problem (over a lattice), so that the optimal $X$ and $Y$ can be read from its solution? Some straightforward trials fail:

  1. Encode $X=1$ by including $X$. It fails because no assumption is made on $T$.

  2. Introduce two indicator variables for $X=0$ and $X=1$. But then the constraint of exclusion leaves the feasible set not a lattice.

I guess it can be boiled down to min-cut, which has a submodular objective. But I still can't connect the dots. It is ok to add auxiliary variables, but going to the dual will be a pain (as this problem is nested in another problem at hand).

Thanks in advance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.