0/1 Knapsack에 대한 서브-지수 함수 알고리즘

국문 초록 (Abstract)

이 논문에서는 고정된 개수를 가진 bin들을 이용하여 실행 복잡도가 p(n).2o() 인 알고리즘을 제시한다, 여기서 x는 ⑤n개의 객체들에 대한 리스트의 길이에 대한 총 비트 수를 나타낸다. 이러한 방법은 수치적 크기나 비중의 합 의 리스트를 이용하는 여러 가지 최적화 알고리즘이나 결정 문제등에 적용할 수 있다. 이 논문에서 제시한 알고리즘은 의사-다항식(pseudo-polynomial) 시간을 갖는 NP-Complete의 많은 문제들을 결정적인 서브-지수 시간에 해결할 수 있은 가능성을 제시한다. 여기서 제시한 알고리즘을 이용하여 생명공학의 유전자 분석에 적용하려고 한다.

다국어 초록 (Multilingual Abstract)

We investigate p(n).2o() algorithm for 0/1 knapsack problem where x is the total bit length of a list of sizes of n objects. The algorithm is adaptable of method that achieves a similar complexity for the partition and Subset Sum problem. The method can be applied to other optimization or decision problem based on a list of numerics sizes or weights. 0/1 knapsack problem can be used to solve NP-Complete Problems with pseudo-polynomial time algorithm. We try to apply this technique to bio-informatics problem which has pseudo-polynomial time complexity.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 분할과 부분 집합의 합
• 3. 일반화된 동적 할당에 의한 동적 프로그래밍
• 4. 배낭-등(Knapsack) 문제
• 5.. Bio-Brick과 Minimum Genome의 설계
• 6. 결론
• 참고문헌

참고문헌 (Reference)

• 1 R. Impagliazzo, "Which Problems have Strongly Exponential Complexity?" Elsevier Science 63 : 512-530, 2001
• 2 M. Alehnovich, "Toward a Model for Backtracking and Dynamic Programming" 308-322, 2005
• 3 R. Stearns, "Power indices and Easier Hard Problems" 23 : 209-225, 1990
• 4 G. J. Woeginger, "Exact Algorithms for NP-Hard Problems: A Survey" Spring-Verlaugh 2570 : 185-207, 2003
• 5 M Garey, "Computers and Intractability : A Guide to the Theory of NP Completenes" Freeman Press 1979
• 6 S. Martello, "A mixture of Dynamic programming and branch-and-bound for subset sum problem" 30 (30): 765-771, 1984