Publications
Detailed Information
일반배낭문제의 완전다항시간근사해법군의 존재조건 : About fully Polynomial Approximability of the Generalized Knapsack Problem
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Issue Date
- 2003
- Citation
- 한국경영과학회지, 제28권, 제4호(2003). pp. 191-198
- Keywords
- Generalized Knapsack Problem ; Fully Polynomial Approximation Scheme ; Scaling ; Approximate Binary Search ; Constrained Spanning Tree Problem
- Abstract
- 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.
- ISSN
- 1225-1119
- Language
- Korean
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.