Editing Open Problems:16
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| 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. | 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 /> | ||
