patternMinor
How difficult is this matching-like problem?
Viewed 0 times
thisproblemlikehowmatchingdifficult
Problem
Let $A$ and $B$ be two sets of integers with $|A|>|B|$.
Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand "$i$ is matched to $j$" if $f(i)=j$. I am looking to solve
$$ \min_{f: A \rightarrow B} \sum_{j \in B} (\mbox{ number of nodes matched to } j)^2, $$
$$ \mbox{ subject to } |i-f(i)| \leq 2 \mbox{ for all } i \in A. $$
In other words, the function $f$ should not "move" any $i \in A$ too far and should come as close to a matching as possible.
Has something like this been studied before? If so, is it known to be NP-hard, or is there an obvious reduction? Are there any known variations on this (e.g., by changing the cost) that are polynomial-time solvable?
Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand "$i$ is matched to $j$" if $f(i)=j$. I am looking to solve
$$ \min_{f: A \rightarrow B} \sum_{j \in B} (\mbox{ number of nodes matched to } j)^2, $$
$$ \mbox{ subject to } |i-f(i)| \leq 2 \mbox{ for all } i \in A. $$
In other words, the function $f$ should not "move" any $i \in A$ too far and should come as close to a matching as possible.
Has something like this been studied before? If so, is it known to be NP-hard, or is there an obvious reduction? Are there any known variations on this (e.g., by changing the cost) that are polynomial-time solvable?
Solution
Observing that there exists an optimal solution such that for any $i_1 , $f(i_1)\le f(i_2)$ (otherwise, we can swap $f(i_1)$ and $f(i_2)$), there is a dynamic programming algorithm solving your problem.
We sort $A$ and $B$ firstly. Suppose $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_m\}$, where $a_1<\cdots and $b_1<\cdots . Let $D(i,j)=\min_{f:\{a_1,\ldots,a_i\}\to\{b_1,\ldots,b_j\}}\sum_{j'\le j}(\text{number of nodes matched to }j')^2$, then $$D(i,j)=\min_k D(i-k,j-1)+k^2,$$
where the minimum is taken over all $k$ such that $a_{i-k}$ is able to be matched to $b_j$. The original objective is to compute $D(n,m)$. It can be done by this recurrence in $O(n^2m)$ time.
We sort $A$ and $B$ firstly. Suppose $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_m\}$, where $a_1<\cdots and $b_1<\cdots . Let $D(i,j)=\min_{f:\{a_1,\ldots,a_i\}\to\{b_1,\ldots,b_j\}}\sum_{j'\le j}(\text{number of nodes matched to }j')^2$, then $$D(i,j)=\min_k D(i-k,j-1)+k^2,$$
where the minimum is taken over all $k$ such that $a_{i-k}$ is able to be matched to $b_j$. The original objective is to compute $D(n,m)$. It can be done by this recurrence in $O(n^2m)$ time.
Context
StackExchange Computer Science Q#130697, answer score: 2
Revisions (0)
No revisions yet.