최소 내가 일치하는 문제가 내가 그것을 해결하는 방법을 모르는 문제

Question

을 최대 일치 :

Given a complete bipartite graph (A, B). 
Each node a_i in A, has two states: s(a_i)=0 or s(a_i)=1 
Weighted edges are declared as: w(a_i, b_j, s(a_i)) 

이 상태의 구성을 수정은 문제가 최대 일치된다.

목표는 최소 최대 일치를 갖는 구성을 찾는 것입니다.

예 :

|A|=|B|=1 
w(a_0, b_0, 0) = 5; 
w(a_0, b_0, 1) = 9; 

MAX-matchings 5 ​​9이므로, (5)는 응답이다. (그래서 구성은 s (a_0) = 0 임)

Answer 1

질문자가 실명을 사용하고 있기 때문에 이것이 숙제라고 생각하지 않습니다.

불행히도, 근사 비율이 2보다 큰 상태의 할당을 찾는 경우 (고유 게임, 그렇지 않으면 1.3606이라고 가정)는 NP 하드입니다. G를 최소 꼭지점 덮개의 인스턴스라고합시다. 세트 A는 G의 각 에지에 대한 정점을 갖는다. 세트 B는 G의 각 정점에 대한 정점을 가진다. w (a_j, b _k, 0)는 1에 해당하는 에지의 더 작은 끝점 a _j은 b _k에 해당하고 그렇지 않은 경우 0에 해당합니다. 더 큰 끝점에 대해 비슷하게 w (_j, b _k, 1)를 정의하십시오. 이 인스턴스의 최소 최대 일치는 G의 최소 정점 커버와 동일한 카디널리티를 가지며, 후자의 문제는 근사하기 어렵습니다.

알고리즘 앞면에서 최소를 최소화하기 위해 내부 최대 무게 일치 문제를 선형 프로그래밍 이중으로 대체 할 수 있습니다. 여기 _J 듀얼 _J에 대응하는 변수이며, Z _{K는 K} ㄴ에 대응하는 듀얼 변수는 Y이다.

분 Σ _{Y J} J + Σ _{K Z K}

s.t.

∀j, k. Y _J + Z _K ≥ (1 - S (a _J)) w (a _J, _K B, 0) + S (a _J) w (a _J, b _k, 1)

∀j. s (a _j) ∈ {0, 1}

∀j. y _j ≥ 0

∀k.Z _K ≥ 0

이 제형은 상용 소프트웨어 (예를 들어, GNU 선형 계획법 키트)에 의해 너무 많은 인적 노력없이 공격 할 수있는 혼합 정수 프로그램이다. 무차별 한 힘보다 낫지 않을 수도 있습니다.