Academic
Publications
On-Line Multiple-Strip Packing

On-Line Multiple-Strip Packing,10.1007/978-3-642-02026-1_14,Deshi Ye,Xin Han,Guochuan Zhang

On-Line Multiple-Strip Packing   (Citations: 6)
BibTex | RIS | RefWorks Download
We study the multiple-strip packing problem, in which the goal is to pack all the rectangles into m vertical strips of unit widths such that the maximum height among strips used is minimized. A number of on-line algorithms for this problem are proposed, in which the decision of delivering the rectangles to strips as well as packing the rectangles in strips must be done on-line. Both randomized and deterministic on-line algorithms are investigated, and all of them are guaranteed to have constant competitive ratios.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Strip packing was extended to the case where the rectangles must be packed into a finite number of strips [2], [3]...

    Daniel Cordeiroet al. Tight Analysis of Relaxed Multi-Organization Scheduling Algorithms

    • ...The main related positive results for MSP are a 2+ ε-approximation in [4] whose cost is doubly exponential in 1 , a (costly)...
    • ...Finally, (as we will see in remark 4), it is possible to derive a better approximation ratio using the remark in [4] that leads to a 2 + � ratio (in time polynomial in 1 ) for the regular case...
    • ...This result is an extension of the result in [4] that was established for the regular case...
    • ...Proof. We follow here the same idea as in [4]...

    Marin Bougeretet al. A Fast 5/2Approximation Algorithm for Hierarchical Scheduling

    • ...Then, this problem was extended to the case where the rectangles were packed into a finite number of strips [16, 15]...

    Johanne Cohenet al. Analysis of Multi-Organization Scheduling Algorithms

    • ...Known Results. Multiple Strip Packing was first considered by Zhuk [16], who showed that there is no approximation algorithm with abolute ratio better than 2, and later by Ye et. al. [15]...
    • ...Additonally an approximation algorithm for the offline case with ratio 2 + ε was achieved in [15]...
    • ...Our Results. In this paper we present an approximation algorithm with absolute ratio 2, which is an improvement of the former result of 2 + ε by Ye et al. [15] and best possible, unless P = NP . We also introduce an AFPTAS for Mutiple Strip Packing, which is a generalization of the algorithm of Kenyon and R´ emila [9]...

    Marin Bougeretet al. Approximation Algorithms for Multiple Strip Packing

    • ...For MSP, Zhuk [25] showed that there is no polynomial time approximation algorithm with absolute ratio better than 2 (unless P = NP ). Later, Ye et al. [24] Scheduling Jobs on Heterogeneous Platforms 273...

    Marin Bougeretet al. Scheduling Jobs on Heterogeneous Platforms

Sort by: