검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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 두 가지 품목 크기를 사용한 온라인 빈 포장의 하한 분석

Hiroshi FUJIWARA, Ken ENDO, Hiroaki YAMAMOTO

  • 조회수

    0

  • 이것을 인용

요약 :

상자 포장 문제에서는 크기가 1에서 2 사이인 주어진 항목을 용량 1의 상자에 넣어야 합니다. 목표는 하나 이상의 항목이 포함된 저장소 수를 최소화하는 것입니다. 빈 포장 문제에 대한 온라인 알고리즘은 각 품목이 도착할 때 하나씩 배치할 위치를 결정합니다. 빈 패킹 문제의 점근적 근사 비율은 문제에 대한 최적의 온라인 알고리즘의 성능으로 정의됩니다. 이 값은 빈 포장 문제의 본질적인 경도를 나타냅니다. 본 논문에서는 모든 품목의 크기가 α 또는 β(≤ α)인 빈 포장 문제를 연구합니다. $alpha > rac{2}{1}$에 대한 점근 근사 비율은 이미 식별되었지만 $alpha leq rac{2}{XNUMX}$에 대한 점근 근사 비율은 부분적으로만 알려져 있습니다. 이 논문은 선형 최적화 문제를 공식화하여 모든 $alpha leq rac{XNUMX}{XNUMX}$에 대한 점근 근사 비율의 하한을 제공하는 최초의 논문입니다. 또한, 이중 실현 가능한 솔루션을 구성하여 닫힌 형태의 또 다른 하한을 도출합니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1127-1133
발행일
2021/09/01
공개일
2021/03/09
온라인 ISSN
1745-1337
DOI
10.1587/transfun.2020DMP0007
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주
알고리즘 및 데이터 구조

작성자

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

키워드