Treffer: Improved Algorithms for Variants of Bin Packing and Knapsack.

Title:
Improved Algorithms for Variants of Bin Packing and Knapsack.
Authors:
Karnati, Venkata Naga Sreenivasulu
Contributors:
Khan, Arindam
Publication Year:
2022
Collection:
Indian Instiute of Science, Bangalore: etd@IIsc (Electronic Theses and Disserations)
Subject Terms:
Approximation Algorithms, Online Algorithms, Bin Packing, Knapsack, Research Subject Categories::TECHNOLOGY::Information technology::Computer science::Computer science
Document Type:
Dissertation thesis
File Description:
application/pdf
Language:
English
Relation:
https://etd.iisc.ac.in/handle/2005/5818
Availability:
https://etd.iisc.ac.in/handle/2005/5818
Rights:
I grant Indian Institute of Science the right to archive and to make available my thesis or dissertation in whole or in part in all forms of media, now hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part of this thesis or dissertation
Accession Number:
edsbas.82F9D44D
Database:
BASE

Weitere Informationen

We study variants of two classical optimization problems: Bin Packing and Knapsack. Both bin packing and knapsack fall under the regime of "Packing and Covering Problems". In bin packing, we are given a set of input items, each with an associated size, and the objective is to pack these into the minimum number of unit capacity bins. On the other hand, in the knapsack problem, each item has an additional profit associated with it. The objective is to find a maximum profitable subset that can be packed into a unit capacity knapsack. Both bin packing and knapsack find numerous applications; however, both turn out to be NP-Hard. Hence, it is natural to seek approximation algorithms for these problems. Lawler settled the knapsack problem by giving an FPTAS, whereas the progressive works of de la Vega and Lueker, Karmarkar and Karp, and Rothvoss have given improved approximation schemes for the bin packing problem. However, many variants of these problems (e.g., multidimensional, geometric, stochastic) also find wide applicability, but haven't been settled. We make progress on this front by providing new and improved algorithms for several such variants. First, we study bin packing under the i.i.d. model, where item sizes are sampled independently and identically from a distribution in (0,1]. Both the distribution and the total number of items are unknown. The items arrive one by one, and their sizes are revealed upon their arrival, and they must be packed immediately and irrevocably in bins of unit size. We provide a simple meta-algorithm that takes an offline \alpha-asymptotic approximation algorithm and provides a polynomial-time (\alpha+\epsilon)-competitive algorithm for online bin packing under the i.i.d. model, where \epsilon>0 is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time (1+\epsilon)-competitive algorithm for online bin packing under the i.i.d. model, thus settling the problem. Then we study a well-known geometric generalization of the knapsack problem, the ...