Open Problems:63 - Revision history

Krzysztof Onak at 22:57, 13 June 2014

2014-06-13T22:57:21Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Amit Chakrabarti to Open Problems:63

2014-06-13T22:56:56Z

Krzysztof Onak moved page Waiting:Amit Chakrabarti to Open Problems:63

Krzysztof Onak at 21:27, 7 June 2014

2014-06-07T21:27:22Z

75.69.101.137: Cosmetic

2014-06-07T18:57:52Z

Cosmetic

75.69.101.137: Expanded problem definition, added citations, clarified meaning of instance-wise gap (Amit C)

2014-06-07T18:57:07Z

Expanded problem definition, added citations, clarified meaning of instance-wise gap (Amit C)

75.69.101.137: Clarified meaning of instance-wise gap (Amit C)

2014-06-07T18:41:54Z

Clarified meaning of instance-wise gap (Amit C)

Krzysztof Onak at 04:16, 4 June 2014

2014-06-04T04:16:08Z

Krzysztof Onak at 08:39, 30 May 2014

2014-05-30T08:39:10Z

Geomblog at 21:39, 28 May 2014

2014-05-28T21:39:23Z

Krzysztof Onak: Created page with "{{Header |title=Submodular Matching Maximization |source=bertinoro14 |who=Amit Chakrabarti }} ???"

2014-05-28T15:47:45Z

Created page with "{{Header |title=Submodular Matching Maximization |source=bertinoro14 |who=Amit Chakrabarti }} ???"

New page

{{Header
|title=Submodular Matching Maximization
|source=bertinoro14
|who=Amit Chakrabarti
}}
???

@@ 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}}.
+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}}.
 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?

@@ 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}}.
 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?

@@ Line 5: / Line 5: @@
 }}
-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 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?

← Older revision		Revision as of 18:41, 7 June 2014
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?

@@ Line 5: / Line 5: @@
 }}
-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 \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?

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro14
 |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}}.

← Older revision	Revision as of 22:56, 13 June 2014
(No difference)