라벨 패킹 문제를 위한 분기한정법에 기반한 개선된 근사 알고리즘

권오흠,송하주 한국차세대컴퓨팅학회 2014 한국차세대컴퓨팅학회 논문지 Vol.10 No.5

라벨 패킹 문제는 고정된 개수의 라벨이 배치된 하나 혹은 그 이상의 템플릿을 반복 인쇄함으로써 라벨들을 생산할 때 초과 생산량이 최소가 되도록 템플릿을 구성하는 최적화 문제이다. 선행연구에서 이 문제가 NP-hard임이 밝혀 졌으며, 탐욕적 기법에 기반한 의사 다항시간의 근사알고리즘이 제안되었다[6]. 본 논문에서는 이 문제를 해결하기 위한 또 다른 근사 알고리즘을 제시한다. 먼저 3~4개 정도의 소수의 템플릿을 사용하는 경우에 대해서 최적 해를 찾는 분기한정법 탐색 알고리즘을 제시하고, 템플릿의 개수가 많을 경우 문제를 작은 규모의 부분 문제들로 분할하 여 해결하는 휴리스틱을 제시한다. 다양한 실험 데이터를 통해 제시한 알고리즘의 성능을 평가하였으며 선행 연구에 서 제시된 알고리즘과 비교하였다. The label packing problem is to compose one or more templates each of which consists of a fixed number of labels of different types and print them multiple times to produce the required amount of labels. The goal is to minimize the over-produced quantities. In our earlier work [6], we proved that this problem is NP-hard and proposed an approximation algorithm based on greedy approach. In this paper, we present an improved approximation algorithm. We first give an optimal algorithm based on branch-and-bound search technique that is applicable when the number of template is a small constant. For the general cases where the number of templates is large, we partition the problem into small subproblems, solve each subproblem using the optimal algorithm, and then merge the results. We tested the algorithm for a variety of sample data and analyse its performance.

일반화된 병렬 작업 스케쥴링

권오흠 釜慶大學校 2000 釜慶大學校 論文集 Vol.5 No.-

A general parallel job scheduling problem is considered. A job can be processed in parallel on one of several alternative subsets of processors. The processing time of the job depends on the subset of processors assigned to the job. We first show the hardness of approximating the problem in the general setting. Next we focus on linear array network of processors. We give an approximation algorithm of ratio for nonpreemptive scheduling, and another algorithm of ratio 2 for preemptive scheduling. Finally, we give a nonpreemptive scheduling algorithm of ratio for two dimensional meshes.

일반화된 병렬 작업 스케쥴링

권오흠 부경대학교 2000 釜慶大學校 論文集 Vol.5 No.-

라벨 패킹 문제를 위한 근사 알고리즘

권오흠,송하주 한국차세대컴퓨팅학회 2014 한국차세대컴퓨팅학회 논문지 Vol.10 No.3

신발이나 의류 등에 부착되는 라벨(label)은 먼저 고정 개수의 라벨이 배치된 템플릿(template)을 제작한 후 각각의 템플릿을 필요한 수량만큼 인쇄하여 생산한다. 이때 템플릿 내의 레이블 조합 방법에 따라 불필요한 초과생산이 발생하게 된다. 본 논문에서는 이 과정을 하나의 최적화 문제로 정형화하고, NP-hard임을 증명한 후, 의사 다항시간(pseudo-polynomial time)의 근사(approximation) 알고리즘을 제시한다. 알고리즘은 기본적으로 탐욕적(greedy) 기법을 따르며 알고리즘의 각 단계에서 동적 계획법(dynamic programming)을 이용한다. 다양한 실험 데이터를 통해 제시한 알고리즘의 성능을 평가하였다.

템플릿 패킹 문제에 대한 최적-적합 전략을 사용한 근사 알고리즘

권오흠,송하주 한국차세대컴퓨팅학회 2016 한국차세대컴퓨팅학회 논문지 Vol.12 No.3

이 논문에서는 서로 다른 종류의 아이템들을 생산하기 위해서 필요한 템플릿을 구성하는 것과 관련된 일종의 패킹문제를 다룬다. 고정된 개수의 아이템이 배치된 하나 혹은 그 이상의 템플릿을 반복 인쇄함으로써 요구된 수량의 아이템들을 생산한다. 문제의 목적은 초과 생산량이 최소가 되도록 아이템들을 템플릿에 배치하는 것이다. 이 문제는NP-hard임이 밝혀져 있으며, 탐욕적 기법과 분기한정법에 기반한 근사 알고리즘이 알려져 있다. 본 논문에서는 이문제를 해결하기 위하여 잘 알려진 최적-적합 전략을 이용한 또 다른 다항시간 근사 알고리즘을 제시한다. 다양한실험 데이터를 통해 제시한 알고리즘의 성능을 평가하였으며 선행 연구에서 제시된 알고리즘과 비교하였다. This paper deals with a kind of packing problem of which the goal is to compose one or more templates which will be used to produce the items of different types. Each template consists of a fixed number of slots which are assigned to the item types and the production of the items is accomplished by printing the template repeatedly. The objective is to minimize the total number of produced items. This problem is known to be NP-hard. Approximation algorithms based on either greedy approach or branch-and-bound technique have been proposed. We present another polynomial time approximation algorithm based on the well-known best-fit strategy. We perform experiments to compare the performance of the proposed algorithm with the previous ones.

결함 허용 순열 라우팅

권오흠 釜慶大學校 2002 釜慶大學校 論文集 Vol.7 No.-

결함 허용 순열 라우팅

권오흠 釜慶大學校 2002 釜慶大學校 論文集 Vol.7 No.-

In this paper, we consider the problem of -fault tolerant permutation routing, in which each node is the source of one packet and, at the same time, is the destination of one packet. For each packet, identical copies of it must be delivered to the destination, along the node-disjoint paths, respectively. We consider the wrap-arounded -way Benes networks and present a randomized -fault tolerant permutation routing algorithm in which, for any link within the network, the number of packets that pass the link is bounded by with high probability.

유방암 면역조직화학 이미지의 가상 염색 변환

권오흠,권기룡,송하주 한국정보과학회 2022 데이타베이스 연구 Vol.38 No.3

Histological staining provides color discrimination between different tissue components and is an essential process in the diagnosis of diseases such as cancer. In addition to H&E, which is the representative staining method, there are various special stains used to better highlight other tissue components. Special stains often require more cost and time and can be a burden to the health care system and patients when a diagnosis is urgent. Instead of chemical tissue staining, converting an already stained tissue image into another stain using deep learning technology is called stain transformation. In this paper, we address the problem of converting H&E-stained tissue images to IHC-stained images for breast cancer screening. The method proposed in this paper is to additionally apply two techniques to compensate for the difference between the source image and the target image to the pix2pix network. First, the difference between the underlying structure of the source and the target is evaluated and used as a weight for the loss function of the network. Second, affine transformation is performed on the generated image patches using STN, In order to evaluate the performance of the proposed network, extensive experiments were conducted and the performance improvement was confirmed by comparing the results with previous studies. 조직학적 염색은 서로 다른 조직 구성요소 간의 색채 구별을 제공하며 암 등의 질병 진단에 있어서 필수적인 과정이다. 대표적인 염색 방법인 H&E 외에도 특정 조직 구성요소를 더 잘 강조하기 위해 사용하는 다양한 특수 염색들이 있다. 특수 염색은 종종 더 큰 비용과 시간이 필요하며 진단이 긴급한 경우 의료 시스템과 환자에게 부담이 될 수 있다. 화학적인 조직 염색 대신 이미 염색된 조직의 이미지를 딥러닝 기술을 이용하여 다른 염색으로 변환하는 것을 염색 변환(stain transformation)이라고 한다. 본 논문에서는 유방암 검사를 위해 H&E 염색된 조직 이미지를 IHC 염색 이미지로 변환하는 문제를 다룬다. 본 논문에서 제안하는 방법은 pix2pix 네트워크에 변환 대상 이미지와 타겟 이미지의 형태상의 차이를 보완하기 위한 2가지 기법을 추가 적용하는 것이다. 첫째는 대상 이미지와 타겟 이미지의 근저(underlying) 구조의 차이를 평가하여 이를 네트워크의 손실함수에 대한 가중치로 사용하고, 둘째로 STN을 이용하여 생성된 이미지에 대해 어핀(affine) 변환을 수행하고 그 결과를 타겟 이미지와 비교한다. 본 논문에서 제안한 네트워크의 성능을 평가하기 위해서 광범위한 실험을 수행하고 그 결과를 선행 연구와 비교하여 성능의 개선을 확인하였다.

무선 센서 네트워크에서 연결성 정보만을 이용하여 노드 위치를 추정하는 분산 알고리즘

권오흠,송하주,김숙연,Kwon Oh-Heum,Song Ha-Joo,Kim Sook-Yeon 한국정보처리학회 2005 정보처리학회논문지 C : 정보통신,정보보안 Vol.12 No.4

본 논문에서는 무선 센서 네트워크 상에서 노드들 간의 연결성만을 이용하여 노드의 위치를 추정하는 분산 알고리즘을 제안한다. 본 논문에서 제안하는 알고리즘들은 기본적으로 공통 인접 노드의 개수를 이용하여 인접한 두 노드간의 거리를 추정하는 기법에 기반하고 있다. 제안된 알고리즘들의 위치 추정 성능을 모의실험을 통하여 분석 비교하였다. We present several distributed algorithms for localizing nodes of a wireless sensor network. Our algorithms determine locations of nodes based on the connectivity between nodes. The basic idea behind our algorithms is to estimate distances between nearby nodes by counting their common neighbors. We analyze the performance of our algorithms experimentally. The results of experiments show that our algorithms achieve performance improvements upon the existing algorithms

이종의 OCT 기기로부터 생성된 볼륨 데이터로부터 심층 컨볼루션 신경망을 이용한 AMD 진단

권오흠,정유진,권기룡,송하주 한국정보과학회 2018 데이타베이스 연구 Vol.34 No.3

There have been active research activities to use neural networks to analyze OCT images and make medical decisions. One requirement for these approaches to be promising solutions is that the trained network must be generalized to new devices without a substantial loss of performance. In this paper, we use a deep convolutional neural network to distinguish AMD from normal patients. The network was trained using a data set generated from an OCT device. We observed a significant performance degradation when it was applied to a new data set obtained from a different OCT device. To overcome this performance degradation, we propose an image normalization method which performs segmentation of OCT images to identify the retina area and aligns images so that the retina region lies horizontally in the image. We experimentally evaluated the performance of the proposed method. The experiment confirmed a significant performance improvement of our approach. 신경망을 이용하여 OCT 영상을 분석하고 다양한 망막 질환을 자동 진단하는 것에 관한 연구들이 활발하게 이루어지고 있다. 이러한 연구가 현실에 적용되기 위한 하나의 중요한 요건은 학습된 신경망이 학습에 사용된 데이터와는 다른 기기에서 생성된 데이터에 대해서도 성능의 큰 하락 없이 일반화될 수 있어야 한다는 것이다. 본 논문에서는 심층 CNN을 이용하여 OCT 영상으로부터 노년기황반변성(AMD)을 자동 진단하는 것을 다룬다. 하나의 OCT 기기로부터 획득한 데이터 셋을 이용하여 신경망을 학습시킨 후 다른 OCT 기기로부터 생산된 이미지를 테스트한 결과 상당한 성능의 하락을 관찰할 수 있었다. 이러한 성능의 하락을 방지하기 위해서 OCT 이미지를 정규화 하는 기법을 제안하고 실험을 통해 그 효과를 분석하였다. 제안한 기법은 OCT 이미지를 분할하여 망막에 해당하는 영역을 찾아낸 후 이미지 내에서 망막 영역이 수평에 가까운 기울기를 가지도록 정렬(align)하여 형태적인 측면에서 OCT 이미지를 정규화 하는 것을 목적으로 한다. 실험을 통하여 제안한 기법이 이종의 기기에서 생성된 OCT 이미지로부터 AMD를 자동진단 하는데 있어서 상당한 성능의 향상을 달성함을 보였다.