SHERP

일반배낭문제의 완전다항시간근사해법군의 존재조건
About fully Polynomial Approximability of the Generalized Knapsack Problem

Cited 0 time in webofscience Cited 0 time in scopus
Authors
홍성필; 박범환
Issue Date
2003
Publisher
한국경영과학회 = The Korean Operations Research and Management Science Society
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
URI
http://uci.or.kr/G300-j12251119.v28n04p191
http://hdl.handle.net/10371/5341
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse