Difference between revisions of "Open Problems:63"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Submodular Matching Maximization
 
 
|source=bertinoro14
 
|source=bertinoro14
 
|who=Amit Chakrabarti
 
|who=Amit Chakrabarti
 
}}
 
}}
 +
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|CrouchS-14}} 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}}.
  
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)$.  
+
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.  
  
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 ?
+
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 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 ?
 

Latest revision as of 22:57, 13 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$ [CrouchS-14] 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?