이 매칭 문제는 얼마나 어렵습니까?
허락하다 $A$ 과 $B$ 두 세트의 정수 $|A|>|B|$. 주어진지도$f: A \rightarrow B$ 과 $i \in A, j \in B$, 속기 "$i$ 일치한다 $j$" 만약 $f(i)=j$. 나는 해결을 찾고있다$$ \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. $$
즉, 기능 $f$ 어떤 것도 "이동"해서는 안됩니다. $i \in A$ 너무 멀어 가능한 한 일치에 가까워 야합니다.
이와 같은 것이 전에 연구 된 적이 있습니까? 그렇다면 NP-hard로 알려져 있습니까, 아니면 명백한 감소가 있습니까? 다항식 시간을 해결할 수있는 (예 : 비용 변경에 의한) 알려진 변형이 있습니까?
답변
최적의 솔루션이 존재하는지 관찰 $i_1<i_2$ , $f(i_1)\le f(i_2)$ (그렇지 않으면 $f(i_1)$ 과 $f(i_2)$), 문제를 해결하는 동적 프로그래밍 알고리즘이 있습니다.
우리는 정렬 $A$ 과 $B$첫째로. 가정$A=\{a_1,\ldots,a_n\}$ 과 $B=\{b_1,\ldots,b_m\}$, 어디 $a_1<\cdots<a_n$ 과 $b_1<\cdots <b_m$. 허락하다$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$, 다음 $$D(i,j)=\min_k D(i-k,j-1)+k^2,$$ 최소가 모든 것을 차지하는 곳 $k$ 그런 $a_{i-k}$ 일치 할 수 있습니다 $b_j$. 원래 목표는$D(n,m)$. 이 반복에 의해 수행 될 수 있습니다.$O(n^2m)$ 시각.
비슷한 목표를 달성 할 수 있고 다항식으로 풀 수있는 비용 함수에는 변형이 있습니다.
다음 문제를 고려하십시오. 주어진 정수 세트 $A,B$ 및 상수 $c$, 찾기 $f:A \to B$ 그런 $|i-f(i)| \le 2$ 모든 $i \in A$, 및 $|f^{-1}(j)| \le c$ 모든 $j \in B$ (즉, 각각 $j \in B$ 기껏해야 $c$ 일치하는 노드).
이 문제는 네트워크 흐름을 줄임으로써 다항식 시간에 해결 될 수 있습니다. 요소 당 하나의 정점이있는 흐름 그래프 작성$A$ 또는 $B$, 소스 $s$ 그리고 싱크대 $t$. 다음에서 용량 1의 에지 추가$s$ 각각에 $i \in A$, 각각에서 용량 1의 에지 $i\in A$ 각각에 $j \in B$ 와 $|i-j|\le 2$, 그리고 용량의 한계 $c$ 각각에서 $j \in B$ ...에 $t$. 이제 네트워크 흐름 알고리즘을 사용하여 최대 흐름을 찾고 용량 흐름을 찾을 수 있는지 테스트합니다.$|A|$. 많은 네트워크 흐름 알고리즘은 그러한 흐름이 존재하는 경우 적분 흐름을 찾도록 보장합니다. 그러한 흐름이 존재한다면 그러한 기능을 찾은 것입니다.$f$; 존재하지 않으면 기능이 없습니다.$f$ 존재합니다.
그런 다음 이진 검색을 사용할 수 있습니다. $c$ 최소한의 것을 찾기 위해 $c$ 그런 그런 $f$ 존재합니다.
원래 문제와 어떤 관련이 있습니까? 원래 문제는 다음과 같이 볼 수 있습니다.$\ell_2$ 내 변형은 비용 함수가있는 것으로 볼 수 있습니다. $\ell_\infty$비용 함수. 모든 솔루션$c$ 그것은 너무 크지 않습니다 $1$ 일치에 "가까울"것입니다.