Difference between revisions of "Open Problems:63"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m
Line 7: Line 7:
 
Let $G = (V, E)$ be a graph. Fix a monotone  submodular function $f : 2^E \rightarrow \mathbb{R}$. A maximum submodular matching $M$ is a subset of $E$ that forms a matching and maximizes $f(E)$.  
 
Let $G = (V, E)$ be a graph. Fix a monotone  submodular function $f : 2^E \rightarrow \mathbb{R}$. A maximum submodular matching $M$ is a subset of $E$ that forms a matching and maximizes $f(E)$.  
  
Suppose the graph edges are streaming. It is known that we cannot compute a maximum weight matching in one pass and $n \text{poly}\log n$ space to a better approximation than $\frac{e}{e-1}$. Can we show a stronger lower bound for maximum ''submodular'' matchings ?  
+
Suppose the graph edges are streaming. It is known that we cannot compute a maximum weight matching in one pass and $n \operatorname{polylog}(n)$ space to a better approximation than $\frac{e}{e-1}$. Can we show a stronger lower bound for maximum ''submodular'' matchings?  
  
 
A conjecture is that it will be hard to get a better than 2-approximation in one pass with the same space constraints.  
 
A conjecture is that it will be hard to get a better than 2-approximation in one pass with the same space constraints.  
  
A related question  (due to Deeparnab Chakrabarty): Is there an instance-wise gap between MWMs and MSMs in the stream setting ?
+
A related question  (due to Deeparnab Chakrabarty): Is there an instance-wise gap between MWMs and MSMs in the stream setting?

Revision as of 08:39, 30 May 2014

Suggested by Amit Chakrabarti
Source Bertinoro 2014
Short link https://sublinear.info/63

Let $G = (V, E)$ be a graph. Fix a monotone submodular function $f : 2^E \rightarrow \mathbb{R}$. A maximum submodular matching $M$ is a subset of $E$ that forms a matching and maximizes $f(E)$.

Suppose the graph edges are streaming. It is known that we cannot compute a maximum weight matching in one pass and $n \operatorname{polylog}(n)$ space to a better approximation than $\frac{e}{e-1}$. Can we show a stronger lower bound for maximum submodular matchings?

A conjecture is that it will be hard to get a better than 2-approximation in one pass with the same space constraints.

A related question (due to Deeparnab Chakrabarty): Is there an instance-wise gap between MWMs and MSMs in the stream setting?