1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If you choose k=3 is it possible to get stuck in a local optima with $M \leq 2 \cdot M^{opt}$. Lets say we have a fully bipartite graph and a local solution M. Can we achieve an approximation-factor two or better with this neighborhood (for the weighted case)? I thought it would act like greedy for $k = 3$. $\endgroup$ – user12731 Jan 11 '14 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.