Publications

Detailed Information

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

DC Field Value Language
dc.contributor.author홍성필-
dc.contributor.author박범환-
dc.date.accessioned2009-07-10T07:08:13Z-
dc.date.available2009-07-10T07:08:13Z-
dc.date.issued2003-
dc.identifier.citation한국경영과학회지, 제28권, 제4호(2003). pp. 191-198en
dc.identifier.issn1225-1119-
dc.identifier.urihttp://uci.or.kr/G300-j12251119.v28n04p191-
dc.identifier.urihttps://hdl.handle.net/10371/5341-
dc.description.abstractThe 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.isoko-
dc.publisher한국경영과학회 = The Korean Operations Research and Management Science Societyen
dc.subjectGeneralized Knapsack Problemen
dc.subjectFully Polynomial Approximation Schemeen
dc.subjectScalingen
dc.subjectApproximate Binary Searchen
dc.subjectConstrained Spanning Tree Problemen
dc.title일반배낭문제의 완전다항시간근사해법군의 존재조건en
dc.title.alternativeAbout fully Polynomial Approximability of the Generalized Knapsack Problemen
dc.typeArticleen
dc.contributor.AlternativeAuthorHong, Sung-Pil-
dc.contributor.AlternativeAuthorPark, Bum Hwan-
Appears in Collections:
Files in This Item:

Altmetrics

Item View & Download Count

  • mendeley

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

Share