Publications
Detailed Information
일반배낭문제의 완전다항시간근사해법군의 존재조건 : About fully Polynomial Approximability of the Generalized Knapsack Problem
DC Field | Value | Language |
---|---|---|
dc.contributor.author | 홍성필 | - |
dc.contributor.author | 박범환 | - |
dc.date.accessioned | 2009-07-10T07:08:13Z | - |
dc.date.available | 2009-07-10T07:08:13Z | - |
dc.date.issued | 2003 | - |
dc.identifier.citation | 한국경영과학회지, 제28권, 제4호(2003). pp. 191-198 | en |
dc.identifier.issn | 1225-1119 | - |
dc.identifier.uri | http://uci.or.kr/G300-j12251119.v28n04p191 | - |
dc.identifier.uri | https://hdl.handle.net/10371/5341 | - |
dc.description.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. | en |
dc.description.sponsorship | 이 논문은 2000년도 중앙대학교 학술연구비 지원에 의한 것임. | en |
dc.language.iso | ko | - |
dc.publisher | 한국경영과학회 = The Korean Operations Research and Management Science Society | en |
dc.subject | Generalized Knapsack Problem | en |
dc.subject | Fully Polynomial Approximation Scheme | en |
dc.subject | Scaling | en |
dc.subject | Approximate Binary Search | en |
dc.subject | Constrained Spanning Tree Problem | en |
dc.title | 일반배낭문제의 완전다항시간근사해법군의 존재조건 | en |
dc.title.alternative | About fully Polynomial Approximability of the Generalized Knapsack Problem | en |
dc.type | Article | en |
dc.contributor.AlternativeAuthor | Hong, Sung-Pil | - |
dc.contributor.AlternativeAuthor | Park, Bum Hwan | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.