지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
이용수
초록· 키워드
오류제보하기
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.
목차
Abstract
1. 서 론
2. 일반배낭문제에 대한 완전다항 시간근사해법군의 존재조건
3. CST 문제의 완전다항시간 근사 가능성에 대해
4. 결 론
참 고 문 헌
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
[Session B1 생산일정/수리계획]About fully polynomial approximability of the generalized knapsack problem
한국경영과학회 학술대회논문집
2003 .11
-
FPTAS and pseudo-polynomial separability of integral hull of generalized knapsack problem
한국경영과학회 학술대회논문집
2004 .11
-
Cover Inequalities for the Robust Knapsack Problem
Management Science and Financial Engineering
2008 .05
-
[A1 최적화] 추가제약이 있는 최소 신장나무 문제에 대한 유사다항시간 알고리듬 및 근사 해법
한국경영과학회 학술대회논문집
2002 .06
-
A Solution Approach for Cardinality Constrained Knapsack Problem
한국경영과학회 학술대회논문집
2012 .05
-
On the Separation of the Rank-1 Chvatal-Gomory Inequalities for the Fixed-Charge 0-1 Knapsack Problem
한국경영과학회지
2011 .06
-
일반 다중선택 선형배낭문제에 대한 효율적인 해법 ( An Efficient Algorithm for the Generalized Multiple Choice Linear Knapsack Problem )
한국경영과학회지
1990 .12
-
Lifting Cover Inequalities for the Precedence - Constrained Knapsack Problem
한국경영과학회 학술대회논문집
1994 .01
-
일반 다중선택 선형배낭문제의 확장문제에 대한 효율적인 해법 ( An Efficient Algorithm for an Extension of the Generalized Linear Multiple Choice Knapsack Problem )
한국경영과학회지
1992 .03
-
Notes on Reducing Mixed Integer Knapsack Problems
한국경영과학회지
1992 .06
-
An Analysis of the Relationship between Problem Characteristics and Algorithm Performance : A Case Study on 0-1 Knapsack Problems
한국경영과학회지
2006 .03
-
On the Stochastic Knapsack Value Function for Random Items of Multiple Classes
한국경영과학회 학술대회논문집
1993 .01
-
Multiple Choice Knapsack-based Heuristic Algorithm for Paper Cutting Optimization
한국경영과학회 학술대회논문집
2013 .05
-
용량이 변화하는 ( 0 , 1 ) - 배낭문제에 대한 절단평면 생성방안 ( A Cut Generation Method for the ( 0 , 1 ) - Knapsack problem with a Variable Capacity )
한국경영과학회지
2000 .09
-
이분할성 우선순위제약을 갖는 배낭문제에 대한 다면체적 절단평면 ( Facets of Knapsack Polytopes with Bipartite Precedence Constraints )
한국경영과학회지
1998 .12
-
Risk-Averse Knapsack Problem with Profit Interdiction
한국경영과학회 학술대회논문집
2017 .04
-
Robust Version of the Bilevel Knapsack with Interdiction Constraints
한국경영과학회 학술대회논문집
2019 .04
-
확장된 일반상한제약을 갖는 최대최소 선형계획 배낭문제 ( The Maximin Linear Programming Knapsack Problem with Extended GUB Constraints )
한국경영과학회지
2001 .09
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-325-013714059