트리의 최적 경로 분할을 위한 다항시간 알고리즘

안형찬 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.5

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 -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. 최소단말경로분할이란 트리를 에지가 서로 소인 단말 노드 간 경로들로 분할하되, 가장 긴 경로의 길이를 최소화하는 문제이다. 본 논문에서는 트리의 최소단말경로분할을 시간에 구하는 알고리즘을 제시한다. 이 알고리즘은 주어진 최적화 문제를 이에 대응하는 결정 문제, 즉 최소단말경로분할의 비용이 이하인지를 결정하는 문제를 이용한 이진 탐색으로 환원한다. 결정 문제는 트리를 한 차례 순회하는 동안 동적 계획법에 의해 해결된다.

알고리즘을 활용한 데이터 보존 계획과 비용 최적화

안형찬 전북대학교 문화융복합아카이빙연구소 2021 디지털문화아카이브지 Vol.4 No.1

In this paper, we propose to optimize the cost of data archiving via algorithmic planning. First, we present algorithmic methods to determine the distribution of data over multiple backup medias and sites. By formulating this distribution task as a concrete mathematical problem, we can apply approximation algorithms, heuristics, or exact algorithms for the problem. We then consider using data compression techniques to reduce the size of archived data. In particular, we focus on lossy compression algorithms and propose to establish a standard that enables a quality-time trade-off in multimedia data decoding. In light of the recent growth of graph data, we remark that graph sparsification and graph summarization algorithms can serve as lossy compression algorithms for graph data. 본 논문에서는 알고리즘을 활용한 계획으로 데이터 보존 비용을 최적화하는 기법을 제안한다. 먼저, 다수의 백업 미디어나 사이트에 데이터가 분산되는 방식을 알고리즘을 통해 결정하는 방안을 제시한다. 이 분산 작업을 잘 정의된 수학적 문제의 형태로 나타내고 나면, 이에 대해 근사 알고리즘이나 휴리스틱, 혹은 정확한 알고리즘을 적용할 수 있게 된다. 이어서, 데이터 압축 기법을 활용해 보존할 데이터의 양을 줄이는 방법을 고려한다. 특히, 손실 압축 알고리즘에 초점을 맞추어, 멀티미디어 데이터를 압축 해제함에 있어 질과 시간 사이의 교환을 가능하게 하는 표준을 정립할 것을 제안한다. 최근 그래프 데이터가 증가하고 있음을 감안할 때, 그래프 희소화나 그래프 요약 알고리즘이 그래프 데이터에 대한 손실 압축 알고리즘으로 기능할 수 있음에 주목하고자 한다.

트리의 최적 경로 분할을 위한 다항시간 알고리즘

안형찬(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.

그래프 채색 알고리즘의 GPGPU 상 구현 및 최적화

윤인섭,안형찬 한국정보과학회 2022 정보과학회 컴퓨팅의 실제 논문지 Vol.28 No.12

In this paper, we propose a new heuristic that optimizes implementations of graph coloring algorithms on GPGPUs by selecting efficient graph representations depending on the input graphs. Previously, Alabandi et al. gave a graph coloring algorithm suitable for GPGPU implementation; however, limitations due to its monolithic use of a single data structure restricted using the full power of GPGPUs. We adopted multiple graph representations that work better with GPGPUs and experimentally measured the resulting performance improvements. These experiments were conducted on RTX 2060 and GTX 1050Ti using graphs from public repositories as the benchmark set. Based on the results, we devised a heuristic that considers the input graph's properties, such as its degree, to automatically select the most suitable graph representation. This led to an average improvement of 8.01% (RTX 2060) - 10.43% (GTX 1050Ti) in running time compared to the previous algorithm. Lastly, we investigated individual cases for which the heuristic showed little improvement. 본 논문에서는 그래프 채색 알고리즘의 GPGPU상 구현을 최적화하는 새로운 기법으로서, 입력에 따라 최적의 그래프 표현방식을 선택하는 휴리스틱을 제시한다. 기존에 Alabandi et al.이 GPGPU에 적합한 그래프 채색 알고리즘을 제시한 바 있으나, 단일한 자료 구조만을 사용한다는 제한으로 인해 GPGPU의 최대 성능을 이끌어 내는 것에는 한계가 있었다. 본 논문에서는 GPGPU에 알맞은 복수의 자료 구조를 채택하고, 이로써 개선된 성능을 실험적으로 측정하였다. 실험은 공개 리파지터리들의 그래프를 벤치마크로 사용해 RTX 2060과 GTX 1050Ti에서 수행하였다. 이 결과를 바탕으로, 입력 그래프의 차수 등을 토대로 적합한 그래프 표현방식을 자동으로 선택해주는 휴리스틱을 개발하였고, 이는 기존 대비 평균 8.01%(RTX 2060)~10.43%(GTX 1050Ti)의 수행 속도 개선 효과를 나타내었다. 끝으로, 휴리스틱의 효과가 저조한 경우에 대한 개별 분석을 수행하였다.

시스템 활성화 오버헤드를 고려한 멀티코어 시스템의 에너지 최적화

이국렬,안형찬 한국정보과학회 2024 정보과학회논문지 Vol.51 No.1

This paper presents heuristics to optimize the energy consumption of multicore systems with wake-up overhead. A multicore system can optimize its energy consumption by strategically (de)activating itself. Given the task information of the system, OSPAL algorithm was previously known to find a schedule that maximizes the common idle time. However, this schedule does not necessarily minimize energy consumption because of the wake-up overhead associated with the storage of memory footprint to non-volatile memory. Previous research proposed to address this issue by modifying their algorithm so that it does not keep common idle times shorter than a threshold. We observe that their choice of threshold is not optimal and propose a randomized heuristic to improve the energy consumption. We also present a dynamic-programming-based postprocessing heuristic to adjust common idle times. We conducted computational experiments to measure the performance of the proposed heuristics, which indicated an average improvement of 37.69% in energy consumption compared to the previous algorithm.

호텔 식음료 부문의 선택속성에 따른 관계 지향 요인에 관한 연구

정광석,원홍석,안형찬 국제관광학회 2007 국제관광연구 Vol.4 No.2

홀짝성 제약이 있는 k-센터 및 설비 위치 선정 문제에 대한 알고리즘의 효율적이고 강건한 구현

김강산(Kangsan Kim),안형찬(Hyung-Chan An) 한국정보과학회 2019 한국정보과학회 학술발표논문집 Vol.2019 No.12

용량 제약이 있는 설비 배치 문제에 대한 휴리스틱 및 선형계획법 완화의 계산적 분석

이승민(Seungmin Lee),안형찬(Hyung-Chan An) 한국정보과학회 2021 정보과학회논문지 Vol.48 No.4

본 논문에서는 용량 제약이 있는 설비 배치 문제(CFL)에 대한 근사 알고리즘을 실용적으로 변형한 새로운 휴리스틱과 이것이 이용하는 선형계획법 완화를 실험적으로 평가·분석한다. CFL은 컴퓨터과학 및 운용과학 분야에서 널리 연구되어온 문제이나, 선형계획법에 기반한 상수 인자 근사 알고리즘은 최근에야 발견되었다. 그러나, 기존의 느슨한 분석으로는 해당 선형계획법 완화의 정수격차(integrality gap)를 288로 상한할 수 있을 뿐이었다. 본 논문은 실제 데이터셋에서의 근사율과 정수격차를 측정함으로써, 휴리스틱 및 여기에 사용된 선형계획의 실질적인 성능을 평가함과 동시에 이론적인 추측을 위한 근거를 마련하고자 한다. 기존의 근사 알고리즘은 이론적인 것이어서 실제로 구현하기에는 지나치게 느린 수행시간을 갖는다. 본 논문에서는 수치적 안정성을 해치지 않으면서도 수행시간을 개선할 수 있는 휴리스틱들을 제안하고 알고리즘의 파라미터를 실험적으로 최적화하여 고속의 구현을 얻는다. 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.

홀짝성 제약이 있는 k-센터 및 설비 위치 선정 문제에 대한 알고리즘의 효율적이고 강건한 구현

김강산(Kangsan Kim),안형찬(Hyung-Chan An) 한국정보과학회 2021 정보과학회논문지 Vol.48 No.3

본 논문에서는 홀짝성 제약이 있는 k -센터 및 설비 위치 선정 문제에 대한 정확한 알고리즘과 근사 알고리즘을 개선하기 위한 휴리스틱을 제안하고, 이들을 실험적으로 평가한다. 이들 두 문제는 이론적인 면에서뿐만 아니라 실용적으로도 중요한 문제로서, 상수 인자 근사 알고리즘이 알려져 있다. 그러나 실제로 이들 문제에 대한 최적해 혹은 근사해를 찾는, 실용적으로 적합한 구현을 얻기 위한 연구는 거의 이루어지지 못하였다. 본 논문에서는 이를 보완하기 위해 알고리즘의 수행 속도, 해의 질, 수치 에러를 개선하는 휴리스틱을 설계하고 실제 데이터셋에서의 성능을 측정한다. 이외에도, 기존에 알려진 상수 인자 근사 알고리즘이 정확한 알고리즘에 비해 성능에 있어 어떠한 차이를 보이는지 검증한다. 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) 한국정보과학회 2018 한국정보과학회 학술발표논문집 Vol.2018 No.6