<p>The problem I have is as follows:
I know the minimizer/minimum of a non-negative submodular function, and want to use this to efficiently compute the minimizer/minimum of a "perturbed" submodular function. </p>

<p>E.g. Consider the special case of the submodular function being the cut-capacity function; i.e. We have a directed s-t graph $(V,E)$ with $n$ nodes and $m$ edges and the cut-capacity function is defined as $f(S)=\sum_{s\in S,t\in S^c} c(u,v)$ where $S\subseteq V$ and $c(u,v)$ denotes the capacity of the edge $(u,v)$. We find the s-t min-cut $A\subset V$. Now we add/delete an edge to the graph, which changes the cut-capacity function only slightly (i.e. the function value is unchanged for most of the arguments). Finding the new min-cut by utilizing the "warm start" $A$ can be done in time $O(m)$. This is more efficient than finding the min-cut from scratch which takes time at least $O(nm)$.</p>

<p>I am looking for any references/keywords for cases more general than the simple cut-function described above. It doesn't have to be the most general submodular function  e.g. I can restrict my attention to graphs but allow the cut function $f:2^V\rightarrow \mathbb{R}_+$ to be a more general (non-negative submodular) function, based on the capacities of the edges crossing the cut.</p>

<p>Thanks.</p>

<p>P.S. I am aware that there is some work on parametric submodular function minimization, however I can't use that since I have to do the above problem repeatedly. E.g. in the graph example I described, I have to add/delete an edge, reoptimize, add/delete an edge, reoptimize and so on. This does not fall in the parametric framework.</p>

CC BY-SA 3.0
2013-06-04T08:04:31.807Z
To me it's not clear what kind of submodular functions you have in mind. Cut functions are natural, but I wonder what is your function that is "more general" than cut functions but still lives around graphs. Do you have a specific example?
Yoshio Okamoto
CC BY-SA 3.0
2013-06-04T17:00:43.947Z
Sure, a very specific example would be this:
Consider a a graph with 4 nodes $\{s,r_1,r_2,t\}$. There are 4 edges in this graph $(s,r_1),(s,r_2),(r_1,t),(r_2,t)$ with some positive numbers associated with each edge $c_{sr_1},c_{sr_2},c_{r_1t},c_{r_2t}$ respectively. There are 4 s-t cuts in this graph depending on whether $r_1$ and $r_2$ are included in the cut or not. The cut function can be:

$f(\{s\}) = \log(1+c_{sr_1}+c_{sr_2})$,

$f(\{s,r_1\}) = \log(1+c_{sr_2})+\log(1+c_{r_1t})$,

$f(\{s,r_2\}) = \log(1+c_{sr_1})+\log(1+c_{r_2t})$,

$f(\{s,r_1,r_2\}) = \log(1+c_{r_1t}+c_{r_2t}).$
rk2
CC BY-SA 3.0
2013-06-06T22:07:22.840Z
Thank you. Although I don't have an answer, it'd be helpful to other people if you'd include the definition of your class of functions in the question.
Yoshio Okamoto
<submodularity>
Submodular function re-optimization (after an update)
rk2
# Submodular function re-optimization (after an update)

(Asked by: username_0 on 2013-06-03)

The problem I have is as follows:
I know the minimizer/minimum of a non-negative submodular function, and want to use this to efficiently compute the minimizer/minimum of a "perturbed" submodular function.

E.g. Consider the special case of the submodular function being the cut-capacity function; i.e. We have a directed s-t graph $(V,E)$ with $n$ nodes and $m$ edges and the cut-capacity function is defined as $f(S)=\sum\_{s\in S,t\in S^c} c(u,v)$ where $S\subseteq V$ and $c(u,v)$ denotes the capacity of the edge $(u,v)$. We find the s-t min-cut $A\subset V$. Now we add/delete an edge to the graph, which changes the cut-capacity function only slightly (i.e. the function value is unchanged for most of the arguments). Finding the new min-cut by utilizing the "warm start" $A$ can be done in time $O(m)$. This is more efficient than finding the min-cut from scratch which takes time at least $O(nm)$.

I am looking for any references/keywords for cases more general than the simple cut-function described above. It doesn't have to be the most general submodular function e.g. I can restrict my attention to graphs but allow the cut function $f:2^V\rightarrow \mathbb{R}\_+$ to be a more general (non-negative submodular) function, based on the capacities of the edges crossing the cut.

Thanks.

P.S. I am aware that there is some work on parametric submodular function minimization, however I can't use that since I have to do the above problem repeatedly. E.g. in the graph example I described, I have to add/delete an edge, reoptimize, add/delete an edge, reoptimize and so on. This does not fall in the parametric framework.

**Tags:** submodularity

> **Comments:**
> **username_1**: To me it's not clear what kind of submodular functions you have in mind. Cut functions are natural, but I wonder what is your function that is "more general" than cut functions but still lives around graphs. Do you have a specific example?  
> **username_0**: Sure, a very specific example would be this: Consider a a graph with 4 nodes $\{s,r_1,r_2,t\}$. There are 4 edges in this graph $(s,r_1),(s,r_2),(r_1,t),(r_2,t)$ with some positive numbers associated with each edge $c_{sr_1},c_{sr_2},c_{r_1t},c_{r_2t}$ respectively. There are 4 s-t cuts in this graph depending on whether $r_1$ and $r_2$ are included in the cut or not. The cut function can be:  $f(\{s\}) = \log(1+c_{sr_1}+c_{sr_2})$,  $f(\{s,r_1\}) = \log(1+c_{sr_2})+\log(1+c_{r_1t})$,  $f(\{s,r_2\}) = \log(1+c_{sr_1})+\log(1+c_{r_2t})$,  $f(\{s,r_1,r_2\}) = \log(1+c_{r_1t}+c_{r_2t}).$  
> **username_1**: Thank you. Although I don't have an answer, it'd be helpful to other people if you'd include the definition of your class of functions in the question.  

---

## 0 answers

