Open Problems:16 - Revision history

Krzysztof Onak at 16:31, 10 March 2014

2014-03-10T16:31:20Z

Krzysztof Onak at 01:41, 7 March 2013

2013-03-07T01:41:42Z

Krzysztof Onak at 05:11, 16 November 2012

2012-11-16T05:11:02Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 16: Graph Matchings}} {{Infobox |label1 = Proposed by |data1 = Andrew McGregor |label2 = Source |data2 = Kanpur 2006 |label3 =..."

2012-10-16T14:48:15Z

Created page with "{{DISPLAYTITLE:Problem 16: Graph Matchings}} {{Infobox |label1 = Proposed by |data1 = Andrew McGregor |label2 = Source |data2 = Kanpur 2006 |label3 =..."

New page

{{DISPLAYTITLE:Problem 16: Graph Matchings}}
{{Infobox
|label1 = Proposed by
|data1 = Andrew McGregor
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/16
}}
Given a weighted graph with $n$ nodes and $m$ edges, the maximum weighted matching (MWM) problem is to find the set of edges of maximum weight such that no two edges share an end-point.
MWM is a classic graph problem and exact polynomial solutions are known {{cite|Edmonds-65|Gabow-90|HopcroftK-73|MicaliV-80}}. The fastest of these algorithms solves the maximum weighted matching problem with running time $O(nm+ n^2 \log n)$. For massive graphs this is still too much and there has been recent work on finding faster approximate algorithms. For the unweighted problem, a linear-time approximation-scheme is known {{cite|KalantariS-95}}. The best general result is a linear time $(2/3-\epsilon)$-approximation {{cite|DrakeH-03|PettieS-04}}.

Algorithms in the data stream model were presented in {{cite|McGregor-05}}. These include $O(n\log n)$-space, $O_\epsilon(1)$-pass algorithms that return a $(1-\epsilon)$-approximation in the unweighted case and a $(1/2-\epsilon)$-approximation in the weighted case. Both are also linear time algorithm in the RAM model.
The algorithms for unweighted matching are based on finding augmenting paths<ref>An augmenting path is a simple paths of odd length such that every second edge in the current matching.</ref> for an existing matching. Many of the ideas used for finding augmenting paths in the unweighted case carry over to the weighted case.
However, it seems that the intrinsic difficulty in achieving a $(1-\epsilon)$-approximation in the weighted case is that there may be augmenting cycles<ref>An augmenting cycle is an even length cycles such that every second edge is in the matching and swapping the matched edges for the unmatched edges will increase the weight of the matching.</ref>. It seems hard to find augmenting cycles in the streaming model. Is there a lower-bound or does there exist an $O_\epsilon(1)$-pass $O(n\log n)$-space algorithm that returns an $(1-\epsilon)$-approximation for MWM.
In the RAM model, does there exist a linear time $(1-\epsilon)$-approximation for MWM?

==Notes==
<references />

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Andrew McGregor

@@ Line 8: / Line 8: @@
 Algorithms in the data stream model were presented in {{cite|McGregor-05}}. These include $O(n\log n)$-space, $O_\epsilon(1)$-pass algorithms that return a $(1-\epsilon)$-approximation in the unweighted case and a  $(1/2-\epsilon)$-approximation in the weighted case. Both are also linear time algorithm in the RAM model.
 The algorithms for unweighted matching are based on finding augmenting paths<ref>An augmenting path is a simple paths of odd length such that every second edge in the current matching.</ref> for an existing matching. Many of the ideas used for finding augmenting paths in the unweighted case carry over to the weighted case.
-However, it seems that the intrinsic difficulty in achieving a $(1-\epsilon)$-approximation in the weighted case is that there may be augmenting cycles<ref>An augmenting cycle is an even length cycles such that every second edge is in the matching and swapping the matched edges for the unmatched edges will increase the weight of the matching.</ref>. It seems hard to find augmenting cycles in the streaming model. Is there a lower-bound or does there exist an $O_\epsilon(1)$-pass $O(n\log n)$-space algorithm that returns an $(1-\epsilon)$-approximation for MWM.
+However, it seems that the intrinsic difficulty in achieving a $(1-\epsilon)$-approximation in the weighted case is that there may be augmenting cycles<ref>An augmenting cycle is an even length cycles such that every second edge is in the matching and swapping the matched edges for the unmatched edges will increase the weight of the matching.</ref>. It seems hard to find augmenting cycles in the streaming model. Is there a lower-bound or does there exist an $O_\epsilon(1)$-pass $O(n\log n)$-space algorithm that returns an $(1-\epsilon)$-approximation for MWM?
 In the RAM model, does there exist a linear time $(1-\epsilon)$-approximation for MWM?
 ==Notes==
 <references />

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 16: Graph Matchings}}
+{{Header
-{{Infobox
+|title=Graph Matchings
-|label1 = Proposed by
+|source=kanpur06
-|data1 = Andrew McGregor
+|who=Andrew McGregor
 }}
 Given a weighted graph with $n$ nodes and $m$ edges, the maximum weighted matching (MWM) problem is to find the set of edges of maximum weight such that no two edges share an end-point.

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)