Worst-Case Analysis of Fast Heuristics for Packing Squares into a Square

C.Picouleau

IBP-Litp 1995/10: Rapport de Recherche Litp / Litp research reports
11 pages - Février/February 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Worst-Case Analysis of Fast Heuristics for Packing Squares into a Square

Résumé : Soit S={S0,...,Sn-1} un ensemble donné de carrés. Placer les carrés dans un carré de coté minimum est un problème NP-difficile. Nous analysons la performance dans le pire des cas d'heuristiques pour ce problème. Les heuristiques construisent un placement en procédant couche par couche. Il n'existe de borne pour le rapport entre la valeur d'une solution obtenue par notre première heuristique et la solution optimale, alors que lorsque les carrés sont triés par taille décroissante ce rapport est borné par ÷2. Nous construisons une instance du problème pour laquelle ce rapport est 1083/ 770@ 1.4065, ainsi la borne ÷2@1.4142 est presque atteinte. La troisième heuristique est plus compliquée que la deuxième, elle admet la même borne dans le pire des cas. Nous construisons une instance pour laquelle ce rapport est 67/48@1.3958

Abstract : Let S={S0,...,Sn-1} be a given set of squares. To pack the squares into a square with minimal edge is a NP-hard problem. We analyze the relative worst-case ratio of fast heuristics for this problem. The heuristics build a packing using a layer by layer strategy. The first heuristic has no bounded worst-case ratio even when the squares are sorted by nonincreasing size, the worst-case ratio of the second heuristic is bounded by ÷2. We show an instance for which the ratio is 1083/ 770 @ 1.4065 so the bound ÷2@1.4142 is almost reached. The third heuristic is more sophisticated than the second and it has the same bound for its worst-case ratio. We build an instance for which the ratio is 67/ 48@1.3958.

Publications internes Litp 1995 / Litp research reports 1995