찾기 그래프 파티션은 내가 최근 몇 알고리즘에 노력하고있다 다음과 같은 문제에 붙어 입수했습니다

Question

교차 파티션 가장자리 각 파티션은 같은 수의 정점 (정점의 총수는 k의 배수라고 가정)과 다른 파티션의 정점을 연결하는 G의 최소 수의 모서리가 있음을 알 수 있습니다.

이 문제에 대한 다항식 시간 알고리즘 (어쨌든 NP 하드 임)을 찾는 것이 아니라 오히려 150 개의 정점과 1200 개의 에지를 24 시간 이내에 해결하는 알고리즘을 찾는 알고리즘입니다. 어떤 좋은 근사 알고리즘도 잘 받아 들여지 겠지만 정확한 해결책을 선호합니다.

난 그러나 관한 가중 그래프에 대한 일반적인 해결책은도 좋은 것, 가능한 한 간단하게 문제가 있었다.

도움 주셔서 감사합니다.

업데이트 : 좀 더 많은 연구를했고, 이것은 수정 된 연결 문제로 재 해석 될 수있다 깨달았다. 어쩌면 그 사고 방식에 따라 해결책이 있을까요?

Answer 1

이것은 실제로 NP 하드 문제입니다. 볼록 최적화에 도움이되거나 배우게된다면, 본능적 인 문제는 많은 변수 (| V |/k 버텍스의 서브 세트 당 하나)가있는 exact coverinteger program으로이 문제를 공식화 한 다음 정수 프로그램으로 generating columns 솔버를 사용하여 많은 내부 모서리가있는 파티션을 찾습니다. w_v가 마스터 문제 이중 용액에 의해 결정된 가중치 직관적 특정 정점 따르면 시급히 필요 방법으로 이해되는 곳 하위 문제 제형

maximize sum_{vertices v} w_v x_v + sum_{edges uv} y_{uv} 
subject to 
sum_{vertices v} x_v = |V|/k 
y_{uv} <= x_u for all edges uv 
y_{uv} <= x_v for all edges uv 
x_v in {0, 1} for all vertices v 
y_{uv} in {0, 1} for all edges uv 

같을 것이다.

Answer 2

하나의 접근법은 클러스터링 알고리즘을 사용하는 것입니다. 최적의 솔루션을 얻지는 못하지만 신속한 준 최적 솔루션입니다.

당신은 여러 가지 방법으로 접근 할 수있다. 예를 들어, biclustering을 사용할 수 있습니다. 또는 주성분 분석을 수행하고 몇 가지 구성 요소를 선택하고 수정 된 k-means 알고리즘을 실행할 수 있습니다.