coupes de guillotine contre coupes générales

Les problèmes de coupe sont des problèmes où un certain grand objet doit être coupé en plusieurs petits objets. Par exemple, imaginez que vous avez une usine qui fonctionne avec de grandes feuilles de verre brut, de largeur et de la longueur L . Il y a plusieurs acheteurs, chacun souhaitant un nombre illimité de petites feuilles de verre. L'acheteur i veut des feuilles de longueur l i et de largeur w i . Votre objectif est de couper les petites feuilles de la grande, de sorte que le total utilisé soit maximisé et les déchets minimisés (il existe également d' autres types de problèmes de découpe et d'emballage ).$W$$L$$i$$l_i$$w_i$

Une restriction courante dans les problèmes de découpe est que les découpes doivent être des découpes à guillotine , c'est-à-dire que chaque rectangle existant ne peut être découpé qu'en deux rectangles plus petits; il est impossible de faire des formes en L, etc. De toute évidence, la zone maximale utilisée avec des coupes à guillotine peut être plus petite que la zone maximale utilisée sans restriction.

Ma question est la suivante: existe-t-il des limites supérieures et inférieures sur le rapport entre la coupe guillotine optimale et la coupe générale optimale?

Travaux connexes: Song et al. (2009) décrivent un algorithme qui utilise un type restreint de coupes à guillotine - coupes à deux guillotines . Ils prouvent, à l'aide de contraintes géométriques, que le rapport entre la coupe maximale à double guillotine et la coupe maximale à guillotine est limité par . Je recherche un résultat comparable sur le rapport entre la coupe guillotine maximale et la coupe générale maximale.$\frac{6}{7}$

Bien que ce soit pas serré, je peux offrir de bornes inférieures et supérieures de et 3 / 4 sur le pire rapport de cas entre les coupes guillotine et coupes générales.$1/4$$3/4$

Commençons par la limite supérieure et supposons que l'on nous donne un morceau de verre carré avec une longueur de côté de . De plus, nous avons exactement un acheteur qui s'intéresse aux feuilles de verre rectangulaires de largeur 1 - ε et de longueur 1 + ε . En utilisant des coupes générales, la solution optimale ressemble à l'image suivante, avec quatre des rectangles souhaités placés autour d'un petit carré de longueur de côté ε au milieu.$2$$1-\varepsilon$$1+\varepsilon$$\varepsilon$

$3/4$

$W$$L$$i$$w_i \leq W$$l_i \leq L$$i$

$i$$1/4$

Je suis conscient que la limite inférieure est assez faible et qu'elle peut probablement être améliorée avec un peu plus de travail. Mais c'est un début.