La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Analysis of Lower Bounds for Online Bin Packing with Two Item Sizes Analyse des limites inférieures pour le conditionnement en bacs en ligne avec deux tailles d'articles

Hiroshi FUJIWARA, Ken ENDO, Hiroaki YAMAMOTO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans le problème de l'emballage des bacs, il nous est demandé de placer des articles donnés, chacun ayant une taille comprise entre zéro et un, dans des bacs d'une capacité de un. L’objectif est de minimiser le nombre de bacs contenant au moins un article. Un algorithme en ligne pour le problème de l'emballage des bacs décide où placer chaque article un par un à son arrivée. Le rapport d'approximation asymptotique du problème de bin packaging est défini comme la performance d'un algorithme en ligne optimal pour le problème. Cette valeur indique la dureté intrinsèque du problème d’emballage des bacs. Dans cet article, nous étudions le problème du bin packaging dans lequel chaque article est soit de taille α, soit de taille β (≤ α). Alors que le rapport d'approximation asymptotique pour $alpha > rac{1}{2}$ était déjà identifié, celui de $alpha leq rac{1}{2}$ n'est que partiellement connu. Cet article est le premier à donner une limite inférieure au rapport d'approximation asymptotique pour tout $alpha leq rac{1}{2}$, en formulant des problèmes d'optimisation linéaire. De plus, nous dérivons une autre borne inférieure sous une forme fermée en construisant des solutions duales réalisables.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1127-1133
Date de publication
2021/09/01
Publicisé
2021/03/09
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2020DMP0007
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
Algorithmes et Structures de Données

Auteurs

Hiroshi FUJIWARA
  Shinshu University
Ken ENDO
  Shinshu University
Hiroaki YAMAMOTO
  Shinshu University

Mots-clés

Table des matières