S-Space College of Engineering/Engineering Practice School (공과대학/대학원) Dept. of Industrial Engineering (산업공학과) Journal Papers (저널논문_산업공학과)
일반배낭문제의 완전다항시간근사해법군의 존재조건
About fully Polynomial Approximability of the Generalized Knapsack Problem
- 홍성필; 박범환
- Issue Date
- 한국경영과학회지, 제28권, 제4호(2003). pp. 191-198
- Generalized Knapsack Problem; Fully Polynomial Approximation Scheme; Scaling; Approximate Binary Search; Constrained Spanning Tree Problem
- The generalized knapsack problem or gknap is the combinatorial optimization problem of optimizing a nonnegative linear function over the integral hull of the intersection of a polynomially separable 0-1 polytope and a knapsack constraint. The knapsack, the restricted shortest path, and the constrained spanning tree problem are a partial list of gknap. More interestingly, all the problem that are known to have a fully polynomial approximation scheme, or FPTAS are gknap. We establish some necessary and sufficient conditions for a gknap to admit an FPTAS. To do so, we recapture the standard scaling and approximate binary search techniques in the framework of gknap. This also enables us to find a weaker sufficient condition than the strong NP-hardness that a gknap does not have an FPTAS. Finally, we apply the conditions to explore the fully polynomial approximability of the constrained spanning problem whose fully polynomial approximability is still open.