If you want to make money online : Register now

[Solved]: Local search: Problem with neighborhood definition

, ,
Problem Detail:

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.

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$.

Question Source : http://cs.stackexchange.com/questions/19625

3.2K people like this