On Two Dimensional Orthogonal Knapsack Problem

Simple item page
dc.creatorHan, Xin
dc.creatorIwama, Kazuo
dc.creatorZhang, Guochuan
dc.date2008-03-29
dc.date.accessioned2026-07-07T12:17:57Z
dc.date.available2026-07-07T12:17:57Z
dc.descriptionIn this paper, we study the following knapsack problem: Given a list of squares with profits, we are requested to pack a sublist of them into a rectangular bin (not a unit square bin) to make profits in the bin as large as possible. We first observe there is a Polynomial Time Approximation Scheme (PTAS) for the problem of packing weighted squares into rectangular bins with large resources, then apply the PTAS to the problem of packing squares with profits into a rectangular bin and get a $\frac65+ε$ approximation algorithm.
dc.identifierhttps://arxiv.org/abs/0803.4260
dc.identifierhttp://arxiv.org/abs/0803.4260
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/212253
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.titleOn Two Dimensional Orthogonal Knapsack Problem
dc.typetext

Files

Collections

arXiv