Minimizing entropy plus a modular function I have a question about whether there are faster algorithms for specific submodular minimization problems.

In particular, I am trying to find a fast algorithm for minimizing the following set function

$$f(S) = - [\sum_{i \in S} \alpha_i \log(\alpha_i) + (1-\sum_{i \in S} \alpha_i) \log(1-\sum_{i \in S} \alpha_i)] + \sum_{i \in S} w_i$$

where $S \subset \{1,...,n\}$, $\{\alpha_i\}_{i=1}^N$ is a vector of positive numbers that add up to 1, and $w_i$ is a set of (possibly negative) weights. 

The first term in the function is a submodular function of $S$. The second term is a modular function of $S$. I know there exist algorithms (Fujishige-Wolfe) to minimize a general submodular function. Are there known algorithms to quickly minimize the sum of the entropy of a set and a modular function?
Unless I'm mistaken, you can solve your problem in $O(n\log n)$ time using a greedy algorithm.

Minimizing $f(S)$ is equivalent to maximizing
$$\textstyle g(S') = \sum_{i \in S'} b_i + \big(\sum_{i\in S'} \alpha_i\big) \log \sum_{j \in S'} \alpha_j$$
for $b_i=w_i + \alpha_i\log(\alpha_i)$.  Here $S'$ is the complement of your $S$.

Assume WLOG that $\alpha_i&gt;0$ (otherwise $i\in S'$ iff $b_i&gt;0$).

Introduce indicator variable $x_i$ for the event that $i\in S'$,
then relax the problem by allowing $x_i\in[0,1]$.  The relaxed problem is to choose $x\in[0,1]^n$ maximizing
$$\textstyle G(x) = \sum_{i} x_i b_i + \big(\sum_i x_i \alpha_i\big) \log \sum_{j} x_j \alpha_j.$$
The partial derivative of $G(x)$ with respect to $x_i$ is
$$\textstyle b_i + \alpha_i\, \lambda(x),$$
where $\lambda(x) = 1 + \log\sum_j x_j \alpha_j$.
So at any optimal $x$, you have 
$$x_i = \begin{cases}
0 &amp; \text{if}~ b_i/\alpha_i &lt; -\lambda(x) \\
1 &amp; \text{if}~ b_i/\alpha_i &gt; -\lambda(x) \\
? &amp; \text{if}~ b_i/\alpha_i = -\lambda(x).
\end{cases}
$$

WLOG, the ratios $b_i/\alpha_i$ are distinct for each $i$ (otherwise an insignificant perturbation of the $b_i$'s makes them so).  So only a single $x_i$ is undetermined by the above condition.  Since $G(x)$ is convex, one of the two neighboring solutions $x'$ (obtained by changing that $x_i$ to zero or one) has $G(x') \ge G(x)$.
Hence, defining $S_j = \{i : b_i/\alpha_i \le b_j/\alpha_j\}$ and $S_0=\emptyset$, the optimal set is $S_j$ for some $j\in\{0,\ldots,n\}$.

So, here is the algorithm.  Assume that $\alpha_i &gt; 0$ for each $i$, and (by sorting first in $O(n\log n)$ time), that
$b_1/\alpha_1 &gt; b_2/\alpha_2 &gt; \cdots &gt; b_n/\alpha_n$.
Enumerate all sets $S_j$ (and compute $G(S_j)$ for each) in $O(n)$ time, then take the best.