Difference between revisions of "Open Problems:63"
(Clarified meaning of instance-wise gap (Amit C)) |
|||
| 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)$. 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. | 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? | + | A related question (due to Deeparnab Chakrabarty): Is there an instance-wise gap between MWMs and MSMs in the stream setting, for some choice of submodular $f$ and with the MWM instance being derived by evaluating $f$ at singleton sets? |
Revision as of 18:41, 7 June 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, for some choice of submodular $f$ and with the MWM instance being derived by evaluating $f$ at singleton sets?
