Difference between revisions of "Open Problems:63"
(Expanded problem definition, added citations, clarified meaning of instance-wise gap (Amit C)) |
(Cosmetic) |
||
| Line 5: | Line 5: | ||
}} | }} | ||
| − | Let $G = (V, E)$ be a graph. Fix a monotone submodular function $f : 2^E \rightarrow \mathbb{R}$. A matching $M \subseteq E$ is called a maximum submodular matching (MSM) with respect to $f$ if it maximizes $f(E)$. This generalizes maximum weight matching (MWM). Suppose the graph edges are streaming and we are allowed only one pass. It is known that using $O(n\log n)$ space we can approximate MWM within a factor of $4+\epsilon$ {{cite|Crouch-S14}} and MSM (for any $f$) within $7.75$ {{cite|ChakrabartiK-14}}. It is also known that we cannot approximate MWM to a factor better than $\frac{e}{e-1}$ using $n \operatorname{polylog}(n)$ space {{cite|Kapralov-12}}. 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 matching $M \subseteq E$ is called a maximum submodular matching (MSM) with respect to $f$ if it maximizes $f(E)$. This generalizes maximum weight matching (MWM). Suppose the graph edges are streaming and we are allowed only one pass. It is known that using $O(n\log n)$ space we can approximate MWM within a factor of $4+\epsilon$ {{cite|Crouch-S14}} and MSM (for any $f$) within $7.75$ {{cite|ChakrabartiK-14}}. It is also known that we cannot approximate MWM to a factor better than $\frac{e}{e-1}$ using $n \operatorname{polylog}(n)$ space {{cite|Kapralov-12}}. |
| + | |||
| + | 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? | 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:57, 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 matching $M \subseteq E$ is called a maximum submodular matching (MSM) with respect to $f$ if it maximizes $f(E)$. This generalizes maximum weight matching (MWM). Suppose the graph edges are streaming and we are allowed only one pass. It is known that using $O(n\log n)$ space we can approximate MWM within a factor of $4+\epsilon$ [Crouch-S14] and MSM (for any $f$) within $7.75$ [ChakrabartiK-14]. It is also known that we cannot approximate MWM to a factor better than $\frac{e}{e-1}$ using $n \operatorname{polylog}(n)$ space [Kapralov-12].
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?
