Difference between revisions of "Open Problems:16"
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=kanpur06 | |source=kanpur06 | ||
|who=Andrew McGregor | |who=Andrew McGregor | ||
| Line 9: | 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. | 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. | 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? | In the RAM model, does there exist a linear time $(1-\epsilon)$-approximation for MWM? | ||
==Notes== | ==Notes== | ||
<references /> | <references /> | ||
Latest revision as of 16:31, 10 March 2014
| Suggested by | Andrew McGregor |
|---|---|
| Source | Kanpur 2006 |
| Short link | https://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 [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 [KalantariS-95]. The best general result is a linear time $(2/3-\epsilon)$-approximation [DrakeH-03,PettieS-04].
Algorithms in the data stream model were presented in [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[1] 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[2]. 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?
