I have question on understanding the following neighborhood relation within a local-search approximation scheme. Let $M$ be a legal matching on any bipartite graph. Let $U_k$ be the neighborhood defined as follows: $$U_k := \{M' : |(M' \backslash M) \cup (M \backslash M')| \leq k\}$$
Can somebody give me an example or explain this to me?
If i choose a small k-value, the cardinality of $M'$ will be small as well, but how does an algorithm decide which matching pair of nodes to take?
If we define node-values and make it a weighted matching,let say we define a weight function $w_e \in \mathbb{R}$ for any edge e in our graph, now the algorithm may use greedy method and take the best possible pair of nodes (with greatest weight).
But I still don't understand the exact set definition of our neighborhood.
I would be grateful for an example, because I'm stumped on this one.