Share Your Experience: Take the 2024 Developer Survey

# Tag Info

Accepted

### Restriction of a convex function to {0, 1}^n

Any real valued function $g$ defined on $\{0,1\}^n$ can be extended to a convex function over $[0,1]^n$ (it is called the convex closure). See Dughmi's nice survey. The implication for your question ...
• 6,999
Accepted

### Minimizing a submodular function given noisy oracle access

A FOCS'15 paper by Lee, Sidford, and Wong [LSW15] can be leveraged to obtain such minimization guarantees -- cf. Section 5 (specifically, Corollary 5.4) in our recent paper ([BCELR16]). Corollary 5....
• 4,471
Accepted

### Maximizing difference of a submodular and a modular function

To simplify life, let $\mathcal V = [n] := \{1,2,\ldots,n\}$. For $A \subseteq [n]$, define $h(A):=\sum_{i \in A}c_i$. Note that $h$ defines a modular (i.e additive) set function. Now, suppose there ...
• 291
1 vote
Accepted

### A variant of the generalised assignment problem

OP's problem generalizes the maximum coverage problem, a well-studied problem for which the best poly-time approximation ratio possibly is $1-1/e$, unless P=NP. So achieving a better ratio for OP's ...
• 10.8k
1 vote

### Reference request --- minimizing a non-increasing submodular function with (upper bound) cardinality constraint

If the only thing that you know about $f$ is that it is non-increasing, then there is a simple adversary argument to show that you need to examine the value of $f$ on at least ${n \choose k}$ inputs (...
• 12.1k
1 vote

### How to sample from a distribution with submodular weights

There is a paper by Gotovos, Hassani, and Krause (NIPS, 2015) titled "Sampling from Probabilistic Submodular Models" which describes a MCMC method based on Gibbs sampling. They show that the mixing ...

Only top scored, non community-wiki answers of a minimum length are eligible