- 소비자 네트워크의 변화 관리 문제 : 최소지배집합 역 문제의 계산 복잡성 증명
- ㆍ 저자명
- 정예림,박선주,정승화,Chung. Yerim,Park. Sunju,Chung. Seungwha
- ㆍ 간행물명
- 韓國經營科學會誌
- ㆍ 권/호정보
- 2014년|39권 2호|pp.131-140 (10 pages)
- ㆍ 발행정보
- 한국경영과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
Customer networks go through constant changes. They may expand or shrink once they are formed. In dynamic environments, it is a critical corporate challenge to identify and manage influential customer groups in a cost effective way. In this context, we apply inverse optimization theory to suggest an efficient method to manage customer networks. In this paper, we assume that there exists a subset of nodes that might have a large effect on the network and that the network can be modified via some strategic actions. Rather than making efforts to find influential nodes whenever the network changes, we focus on a subset of selective nodes and perturb as little as possible the interaction between nodes in order to make the selected nodes influential in the given network. We define the following problem based on the inverse optimization. Given a graph and a prescribed node subset, the objective is to modify the structure of the given graph so that the fixed subset of nodes becomes a minimum dominating set in the modified graph and the cost for modification is minimum under a fixed norm. We call this problem the inverse dominating set problem and investigate its computational complexity.