Skip to main content
6 votes
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 ...
Chandra Chekuri's user avatar
6 votes
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....
Clement C.'s user avatar
  • 4,471
4 votes
Accepted

Minimizing entropy plus 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 ...
Neal Young's user avatar
  • 10.8k
3 votes
Accepted

A bound that follows from submodularity

The following lemma implies the inequality in question. Lemma 1. $E[f_{R\setminus \{a\}}(a)] \le E[f_{R\setminus\{a\}}(a) \,|\, a \in R]$ Proof. Consider the following experiment: Let $R$ be ...
Neal Young's user avatar
  • 10.8k
3 votes
Accepted

A maximization problem containing summation and multiplication

I think both of your problems are in P. Here's an algorithm that works in P without any restriction on the $(a_i,b_i)$ pairs. Formulate your problem as the problem of choosing $x\in\{0,1\}^n$ ...
Neal Young's user avatar
  • 10.8k
3 votes
Accepted

Properties of convex polytope of 0-1 matrices

Sasho already gave you a yes/no answer, but here's an actual convex combination for you: If $B_\ell$ is the $k \times k$ matrix which is $1$ when $|S_i \cap S_j| \ge \ell$ and zero otherwise, then $M =...
Andrew Morgan's user avatar
2 votes

Minimizing SubModular Function: Cardinality

It is NP-hard. Svitkina and Fleischer showed that there is no $o(\sqrt{n/\log n})$ approximation using only a polynomial number of queries.
Chao Xu's user avatar
  • 4,479
2 votes
Accepted

Monotone supermodular function minimization under partition matroid constraints

Consider a graph $G=(V,E)$. Define the set function $f$ over $V$ where $f(A)$ is the number of edges with both end points in $A$. Then $f$ is supermodular and monotone. Suppose $G$ has an independent ...
Chandra Chekuri's user avatar
2 votes
Accepted

Maximum weight matching and submodular functions

Definition. For a given finite set $A$, a set function $f:2^A \rightarrow \mathbb{R}$ is submodular if for any $X, Y \subseteq A$ it holds that: $$ f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y). $$ ...
George Octavian Rabanca's user avatar
2 votes

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 ...
dohmatob's user avatar
  • 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 ...
Neal Young's user avatar
  • 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 (...
D.W.'s user avatar
  • 12.2k
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 ...
Chris Harshaw's user avatar

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