Earticle

초록

영어

Labels of clothes or shoes are produced by making templates containing a fixed number of labels of different types and printing them multiple times. The composition of label types in templates determines the production loss which is defined to be the over-produced quantities. In this paper, we formulate this into an optimization problem and prove its NP-hardness. Then we present a pseudo-polynomial time approximation algorithm. Our algorithm takes a greedy approach and each step of it solves a sub-problem using dynamic programming technique. We tested the algorithm for a variety of sample data and analysed its performance.

한국어

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

목차

요약
 Abstract
 1. 서론
 2. 관련연구 및 시간복잡도
 3. 알고리즘
  3.1 개요
  3.2 최적 템플릿 찾기
  3.3 지정된 개수 이상의 라벨 타입을 커버하는 최적 템플릿 찾기
  3.4 템플릿 별로 라벨 수의 하한값 결정하기
 4. 성능분석
 5. 결론
 참고문헌

키워드

저자

• 권오흠 [ Oh-Heum Kwon | 부경대학교 IT융합응용공학과 ]
• 송하주 [ Ha-Joo Song | 부경대학교 IT융합응용공학과 ] 교신저자

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국차세대컴퓨팅학회 논문지 [THE JOURNAL OF KOREAN INSTITUTE OF NEXT GENERATION COMPUTING]

• 간기

  격월간

• pISSN

  1975-681X

• 수록기간

  2005~2026

• 등재여부

  KCI 등재

• 십진분류

  KDC 566 DDC 004