선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 (IP)의 선형계 획 완화문제를 푸는 대신에 이 문제의 쌍대문제를 풀어서 상한을 도출하려고 한다. 왜냐하면 쌍대문제의 구조적 특성이 해를 구성하기가 수월하기 때문이다.
- 주어진 그래프의 부분 그래프 중에서 부분그래프의 각 노드별로 하나 이상의 인접하는 노드가 부분그래프에 포함되는 경우에 이러한 부분그래프를 고립된 노드가 없는 부분 그래프라고 부르기로 하자. 본 논문에서는 고립된 노드가 없는 k-노드 부분그래프 중에서 부분그래프에 포함된 노드들의 가중치의 합이 최대가 되는 부분 그래프를 선택하는 문제를 다룬다. 이 문제는 CDMA를 기반으로 하는 멀티캐스트 네트워크 설계에 응용 예를 갖고 있다.
- 이 장에서는 정수계획모형의 실행가능해를 구하는 휴리스틱을 개발하려 한다. 우리의 해법은 노드를 추가해 가는 방식의 휴리스틱 (add heuristic)이다.
가설 설정
- 다음과 같이 정의된다. 노드( node)와 에지(edge)로 구성된 무방향 네트워크(undirected network)와 각 노드별 가중치가 주어져 있다고 가정하자. 두 노드가 에지로 연결되어 있는 경우에 두노드는 인접한다고 정의한다.
- 두 노드 /e "와 /e "에 걸쳐 있는 에지를 e=( i, /) 로 표시하기로 하고 두 노드 /와 /를 에지 e 의 종단노드(end nodes)라고 부르기로 한다. 주어진 그래프 G에는 두 노드를 동일한 종단 노드로 하는 복수의 에지(multiple edge)나 동일한 노드를 종단노드로 하는 에지(self-loop)는 존재하지 않는 것으로 가정한다. 각 노드 ie V 의 가중치를 d(i)로 표시하기로 한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.