지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술대회자료
- 저자정보
- 발행연도
- 2003.11
- 수록면
- 93 - 96 (4page)
이용수
이 논문의 연구 히스토리 (2)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
The generalized knapsack problem, or gknap is the combinatorial optimization problem of optimizing a nonnegative linear functional over the integral hull of the intersection of a polynomially separable 0 - 1 polytope and a knapsack constraint. Among many potential applications, the knapsack, the restricted shortest path, and the restricted spanning tree problem are such examples.
We establish some necessary and sufficient conditions for a gknap to admit a fully polynomial approximation scheme, or FPTAS, To do so, we recapture the scaling and approximate binary search techniques in the framework of gknap. This also enables us to find a condition that a gknap does not have an FPTAS. This condition is more general than the strong N P-hardness.
We establish some necessary and sufficient conditions for a gknap to admit a fully polynomial approximation scheme, or FPTAS, To do so, we recapture the scaling and approximate binary search techniques in the framework of gknap. This also enables us to find a condition that a gknap does not have an FPTAS. This condition is more general than the strong N P-hardness.
목차
Abstract
1. Introduction
2. Definitions and notation
3. Scaling and approximate binary search
References
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
일반배낭문제의 완전다항시간근사해법군의 존재조건
한국경영과학회지
2003 .12
-
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
-
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 Separation of the Rank-1 Chvatal-Gomory Inequalities for the Fixed-Charge 0-1 Knapsack Problem
한국경영과학회지
2011 .06
-
Multiple Choice Knapsack-based Heuristic Algorithm for Paper Cutting Optimization
한국경영과학회 학술대회논문집
2013 .05
-
On the Stochastic Knapsack Value Function for Random Items of Multiple Classes
한국경영과학회 학술대회논문집
1993 .01
-
A Solution Approach for Cardinality Constrained Knapsack Problem
한국경영과학회 학술대회논문집
2012 .05
-
Lifting Cover Inequalities for the Precedence - Constrained Knapsack Problem
한국경영과학회 학술대회논문집
1994 .01
-
Risk-Averse Knapsack Problem with Profit Interdiction
한국경영과학회 학술대회논문집
2017 .04
-
Robust Version of the Bilevel Knapsack with Interdiction Constraints
한국경영과학회 학술대회논문집
2019 .04
-
An AI Approach with Tabu Search to Solve Multi-level Knapsack Problems : Using Cycle Detection , Short-term and Long-term Memory
한국경영과학회지
1997 .09
-
Optimization Algorithms for Knapsack Problem with Queuing Delays under Uncertainty
한국경영과학회 학술대회논문집
2017 .04
-
일반 다중선택 선형배낭문제에 대한 효율적인 해법 ( An Efficient Algorithm for the Generalized Multiple Choice Linear Knapsack Problem )
한국경영과학회지
1990 .12
-
용량이 변화하는 ( 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
-
일반 다중선택 선형배낭문제의 확장문제에 대한 효율적인 해법 ( An Efficient Algorithm for an Extension of the Generalized Linear Multiple Choice Knapsack Problem )
한국경영과학회지
1992 .03
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-325-013778626