http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
안형찬(Hyung-Chan An) 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.5·6
트리의 최소단말경로분할이란 트리를 에지가 서로 소인 단말 노드 간 경로들로 분할하되, 가장 긴 경로의 길이를 최소화하는 문제이다. 본 논문에서는 트리의 최소단말경로분할을 O(│V│²) 시간에 구하는 알고리즘을 제시한다. 이 알고리즘은 주어진 최적화 문제를 이에 대응하는 결정 문제, 즉 최소단말경로 분할의 비용이 ℓ 이하인지를 결정하는 문제를 이용한 이진 탐색으로 환원한다. 결정 문제는 트리를 한 차례 순회하는 동안 동적 계획법에 의해 해결된다. A minimum terminal path decomposition of a tree is defined as a partition of the tree into edge-disjoint terminal-to-terminal paths that minimizes the weight of the longest path. In this paper, we present an O(│V│²)-time algorithm to find a minimum terminal path decomposition of trees. The algorithm reduces the given optimization problem to the binary search using the corresponding decision problem, the problem to decide whether the cost of a minimum terminal path decomposition is at most ℓ. This decision problem is solved by dynamic programing in a single traversal of the tree.
홀짝성 제약이 있는 k-센터 및 설비 위치 선정 문제에 대한 알고리즘의 효율적이고 강건한 구현
김강산(Kangsan Kim),안형찬(Hyung-Chan An) Korean Institute of Information Scientists and Eng 2021 정보과학회논문지 Vol.48 No.3
In this paper, we present heuristics for improving the exact and approximation algorithms for parity-constrained k -center and facility location problems, along with their computational evaluations. For the theoretical and practical relevance of these problems, constant-factor approximation algorithms are known for both problems. Unfortunately, few studies have been conducted to obtain a practically adequate implementation of exact and/or approximation algorithms for either problem. This paper fills in this gap by devising heuristics to improve the running time, solution quality, and numerical errors of the algorithms for both problems and measuring their performance. We also evaluate the known constant-factor approximation algorithms in comparison to exact algorithms.
용량 제약이 있는 설비 배치 문제에 대한 휴리스틱 및 선형계획법 완화의 계산적 분석
이승민(Seungmin Lee),안형찬(Hyung-Chan An) Korean Institute of Information Scientists and Eng 2021 정보과학회논문지 Vol.48 No.4
In this paper, we experimentally evaluate new practical heuristics based on approximation algorithms for capacitated facility location (CFL) and the linear programming (LP) relaxations used by them. Although CFL has been extensively studied in the fields of computer science and operations research, an LP-based constant-factor approximation algorithm was only discovered recently. However, the existing analysis only gives a loose upper bound of 288 on the integrality gap of the LP relaxation. By measuring the approximation ratio and the integrality gap in a concrete dataset, this paper aims at measuring the practical performance of the heuristics and the relaxation, which would also provide evidence for further theoretical exploration. Due to the highly theoretical nature of the existing approximation algorithm, its naive implementation is practically inefficient. In this paper, we propose heuristics that improve the running time without affecting the numerical stability and experimentally optimize the algorithms’ parameters, thus obtaining an efficient implementation.