최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기대한산업공학회지 = Journal of the Korean Institute of Industrial Engineers, v.38 no.1, 2012년, pp.1 - 6
황학진 (조선대학교 공과대학 산업공학과) , 강장하 (조선대학교 공과대학 산업공학과)
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-
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. (1992), Proof verification and hardness of approximation problems, in Proceedings of the 33rd IEEE Symposium on the Foundations of Computer Science, 14-23.
Caprara, A. and Toth, P. (2001), Lower bounds and algorithms for the 2-dimensional vector packing problem, Discrete Applied Mathematics, 111, 231-262.
Chang, S. Y., Hwang, H.-C., and Park, S. (2005), A two-dimensional vector packing model for the efficient use of coil cassettes, Computers and Operations Research, 32, 2051-2058.
Chekuri, C. (1998), Approximation Algorithms for Scheduling Problems, PhD. Thesis, Stanford University, Department of Computer Science.
Coffman Jr., E. G., Garey, M. R., and Johnson D. S. (1997), Approximation algorithms for bin packing: A survey, in D. S. Hochbaum, eds. : Approximation Algorithms for NPhard Problems, PWS Publishing Company.
Fernandez de la Vega, W. and Lueker, G. S. (1981), Bin packing can be solved within $1+{\epsilon}$ in linear time, Combinatorics, 1, 349-355.
Garey, M. R. and Johnson, D. S. (1979), Computers and Intractability : a Guide to the Theory of NP-Completeness, Freeman, San Francisco.
Hwang, H.-C. (2007), A 4/3-Approximation Algorithm for Cassette Packing in Steel Industry, Asia-Pacific Journal of Operational Research, 24, 715-724.
Johnson, D. S. (1973), Near-Optimal Bin Packing Algorithms, PhD thesis, Massachusetts Institute of Technology, Department of Mathematics, Cambridge, MA.
Kann, V. (1991), Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, 38, 27-35.
Kellerer, H. and Kotov, V. (2003), An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing, Operations Research Letters, 31, 35- 41.
Papadimitriou, C. H. and Yannakakis, M. (1991), Optimization, approximation and complexity classes, Journal of Computer and System Sciences, 43, 425-440.
Spieksma, F. C. R. (1994), A branch-and-bound algorithm for the two dimensional vector packing problem, Computers and Operations Research, 21, 19-25.
Woeginger, G. J. (1997), There is no asymptotic PTAS for two-dimensional vector packing, Information Processing Letters, 64, 293-297.
Yao, A. C. C. (1980), New algorithms for bin packing, Journal of the ACM, 27, 207-227.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.