Local search: Problem with neighborhood definition

Question

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.

Answer 1

The metric used for the definition of the neighborhood is the size of the symmetric difference. The symmetric difference $A\triangle B$ of two sets $A,B$ is the number of elements which are in exactly one of the sets $A,B$. So $A\triangle B = (A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$. A matching is considered a set of edges, so $M\triangle M'$ is the set of edges that are found in exactly one of the matchings. The metric is $d(M,M') = |M \triangle M'|$, and the $k$th neighborhood of a matching $M$ is the set of matchings $M'$ at distance at most $k$ from $M$.

As an example, if $M'$ results from adding an edge to $M$ or from removing an edge from $M$ then $d(M,M') = 1$, and if $M'$ results from replacing one edge of $M$ with another then $d(M,M') = 2$.