지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
초록· 키워드
오류제보하기
We consider a two-dimensional vector packing problem in which each item has size in x- and y-coordinates. The purpose of this paper is to provide a ground work on how hard two-dimensional vector packing problems are for large items. We prove that the problem with each item greater than 1/2-ε either in x- or y-coordinates for 0 < ε ≤ 1/6 has no APTAS unless P = NP.
목차
1. Introduction
2. Polynomial Solvability for Large Items
3. Nonapproximability for Large Items
4. Conclusions
References
참고문헌 (15)
참고문헌 신청
Arora, S. / 1992 / Proof verification and hardness of approximationproblems / Proceedings of the 33rd IEEE Symposium onthe Foundations of Computer Science :14~23
Caprara, A. / 2001 / Lower bounds and algorithms for the 2-dimensional vector packing problem / Discrete Applied Mathematics 111:231~262
장수영 / 200501 / A two-dimensional vector packing model for the efficient use of coil cassettes / COMPUTERS & OPERATIONS RESEARCH 32(8):2051~2058
Chekuri, C. / 1998 / Algorithms for Scheduling Problems
Coffman Jr., E. G. / 1997 / Approximation algorithms for bin packing: A survey, In Approximation Algorithms for NPhard Problems / PWS Publishing Company
Caprara, A. / 2001 / Lower bounds and algorithms for the 2-dimensional vector packing problem / Discrete Applied Mathematics 111:231~262
장수영 / 200501 / A two-dimensional vector packing model for the efficient use of coil cassettes / COMPUTERS & OPERATIONS RESEARCH 32(8):2051~2058
Chekuri, C. / 1998 / Algorithms for Scheduling Problems
Coffman Jr., E. G. / 1997 / Approximation algorithms for bin packing: A survey, In Approximation Algorithms for NPhard Problems / PWS Publishing Company
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2013-530-003629269