Author | Conference | Journal | Organization | Year | DOI
Look for results that meet for the following criteria:
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

Edit
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.
Conference: Conference on Combinatorial Optimization and Applications - COCOA , pp. 155-165, 2009
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.
More »
    • ...Strip packing was extended to the case where the rectangles must be packed into a finite number of strips [2], [3]...

    Daniel Cordeiro, et 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 Bougeret, et 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 Cohen, et 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 Bougeret, et 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 Bougeret, et al. Scheduling Jobs on Heterogeneous Platforms

Sort by:

Citations (6)

Share this on