We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given n items with sizes in \((0,1]\) and the goal is to pack them into the minimum number of unit-sized bins. 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 size 1. We provide a simple meta-algorithm that takes an offline \(\alpha\) -asymptotic approximation algorithm and provides a polynomial-time \((\alpha+\varepsilon)\) -competitive algorithm for online bin packing under the i.i.d. model, where \(\varepsilon > 0\) is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time \((1+\varepsilon)\) -competitive algorithm for online bin packing under i.i.d. model, thus settling the problem. We then study the random-order model, where an adversary chooses the instance, but the order of arrival of items in the instance is drawn uniformly at random from the set of all permutations of the items. Kenyon’s seminal result (1996) showed that the Best-Fit algorithm has a competitive ratio of at most \(3/2\) in the random-order model, and conjectured the ratio to be \(\approx 1.15\) . However, it has been a long-standing open problem to break the barrier of \(3/2\) even for special cases. Recently, Albers et al. (2021) showed an improvement by proving that in the special case when all the item sizes are greater than \(1/3\) , Best-Fit has a competitive ratio of at most \(5/4\) in the random-order model. In this work, we settle this special case by showing that Best-Fit has a competitive ratio of exactly 1, i.e., Best-Fit performs almost optimally in this special case in the random-order model. We also make further progress by breaking the barrier of \(3/2\) for the 3-Partition problem, a notoriously hard special case of bin packing, where all item sizes lie in \((1/4,1/2]\) .

Best-Fit is one of the most prominent and practically used algorithms for the bin packing problem, where a set of items with associated sizes needs to be packed in the minimum number of unit-capacity bins. Kenyon [SODA ‘96] studied online bin packing under random-order arrival, where the adversary chooses the list of items, but the items arrive one by one according to an arrival order drawn uniformly at random from the set of all permutations of the items. Kenyon's seminal result established an upper bound of 1.5 and a lower bound of 1.08 on the random-order ratio of Best-Fit, and it was conjectured that the true ratio is ≍ 1.15. The conjecture, if true, will also imply that Best-Fit (on randomly permuted input) has the best performance guarantee among all the widely-used simple algorithms for (offline) bin packing. This conjecture has remained one of the major open problems in the area, as highlighted in the recent survey on random-order models by Gupta and Singla [Beyond the Worst-Case Analysis of Algorithms ‘20]. Recently, Albers et al. [Algorithmica ‘21] improved the upper bound to 1.25 for the special case when all the item sizes are greater than 1/3, and they improve the lower bound to 1.1. Ayyadevara et al. [ICALP ‘22] obtained an improved result for the special case when all the item sizes lie in (1/4,1/2], which corresponds to the 3-partition problem. The upper bound of 3/2 for the general case, however, has remained unimproved. This also has remained the best random-order ratio among all polynomial-time algorithms for online bin packing.

We study the fair allocation of indivisible goods among agents with identical, additive valuations but individual budget constraints. Here, the indivisible goods--each with a specific size and value--need to be allocated such that the bundle assigned to each agent is of total size at most the agent's budget. Since envy-free allocations do not necessarily exist in the indivisible goods context, compelling relaxations--in particular, the notion of envy-freeness up to k goods (EFk)--have received significant attention in recent years. In an EFk allocation, each agent prefers its own bundle over that of any other agent, up to the removal of k goods, and the agents have similarly bounded envy against the charity (which corresponds to the set of all unallocated goods). It has been shown in prior work that an allocation that satisfies the budget constraints and maximizes the Nash social welfare is 1/4-approximately EF1. However, the computation (or even existence) of exact EFk allocations remained an intriguing open problem. We make notable progress towards this by proposing a simple, greedy, polynomial-time algorithm that computes EF2 allocations under budget constraints. Our algorithmic result implies the universal existence of EF2 allocations in this fair division context. The analysis of the algorithm exploits intricate structural properties of envy-freeness. Interestingly, the same algorithm also provides EF1 guarantees for important special cases. Specifically, we settle the existence of EF1 allocations for instances in which: (i) the value of each good is proportional to its size, (ii) all the goods have the same size, or (iii) all the goods have the same value. Our EF2 result even extends to the setting wherein the goods' sizes are agent specific.

We study fair division of goods under the broad class of generalized assignment constraints. In this constraint framework, the sizes and values of the goods are agent-specific, and one needs to allocate the goods among the agents fairly while further ensuring that each agent receives a bundle of total size at most the corresponding budget of the agent. Since, in such a constraint setting, it may not always be feasible to partition all the goods among the agents, we conform---as in recent works---to the construct of charity to designate the set of unassigned goods. For this allocation framework, we obtain existential and computational guarantees for envy-free (appropriately defined) allocation of divisible and indivisible goods, respectively, among agents with individual, additive valuations for the goods.

We study the generalized multidimensional bin packing problem (GVBP) that generalizes both geometric packing and vector packing. Here, we are given n rectangular items where the i-th item has width w(i), height h(i), and d nonnegative weights v₁(i), v₂(i), …, v_d(i). Our goal is to get an axis-parallel non-overlapping packing of the items into square bins so that for all j ∈ [d], the sum of the j-th weight of items in each bin is at most 1. This is a natural problem arising in logistics, resource allocation, and scheduling. Despite being well-studied in practice, approximation algorithms for this problem have rarely been explored. We first obtain two simple algorithms for GVBP having asymptotic approximation ratios 6(d+1) and 3(1 + ln(d+1) + ε). We then extend the Round-and-Approx (R&A) framework [Bansal et al., 2009; Bansal and Khan, 2014] to wider classes of algorithms, and show how it can be adapted to GVBP. Using more sophisticated techniques, we obtain better approximation algorithms for GVBP, and we get further improvement by combining them with the R&A framework. This gives us an asymptotic approximation ratio of 2(1 + ln((d+4)/2)) + ε for GVBP, which improves to 2.919+ε for the special case of d = 1. We obtain further improvement when the items are allowed to be rotated. We also present algorithms for a generalization of GVBP where the items are high dimensional cuboids.

We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given n items with sizes in (0,1] and the goal is to pack them into the minimum number of unit-sized bins. 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 size 1. We provide a simple meta-algorithm that takes an offline $α$-asymptotic approximation algorithm and provides a polynomial-time $(α+ \varepsilon)$-competitive algorithm for online bin packing under the i.i.d. model, where $\varepsilon$>0 is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time $(1+\varepsilon)$-competitive algorithm for online bin packing under i.i.d. model, thus settling the problem. We then study the random-order model, where an adversary specifies the items, but the order of arrival of items is drawn uniformly at random from the set of all permutations of the items. Kenyon's seminal result [SODA'96] showed that the Best-Fit algorithm has a competitive ratio of at most 3/2 in the random-order model, and conjectured the ratio to be around 1.15. However, it has been a long-standing open problem to break the barrier of 3/2 even for special cases. Recently, Albers et al. [Algorithmica'21] showed an improvement to 5/4 competitive ratio in the special case when all the item sizes are greater than 1/3. For this special case, we settle the analysis by showing that Best-Fit has a competitive ratio of 1. We make further progress by breaking the barrier of 3/2 for the 3-Partition problem, a notoriously hard special case of bin packing, where all item sizes lie in (1/4,1/2].

We study the d-dimensional hypercube knapsack problem where we are given a set of d-dimensional hypercubes with associated profits, and a knapsack which is a unit d-dimensional hypercube. The goal is to find an axis-aligned non-overlapping packing of a subset of hypercubes such that the profit of the packed hypercubes is maximized. For this problem, Harren (ICALP'06) gave an algorithm with an approximation ratio of (1+1/2^d+epsilon). For d=2, Jansen and Solis-Oba (IPCO'08) showed that the problem admits a polynomial-time approximation scheme (PTAS); Heydrich and Wiese (SODA'17) further improved the running time and gave an efficient polynomial-time approximation scheme (EPTAS). Both the results use structural properties of 2-D packing, which do not generalize to higher dimensions. For d>2, it remains open to obtain a PTAS, and in fact, there has been no improvement since Harren's result. We settle the problem by providing a PTAS. Our main technical contribution is a structural lemma which shows that any packing of hypercubes can be converted into another structured packing such that a high profitable subset of hypercubes is packed into a constant number of special hypercuboids, called V-Boxes and N-Boxes. As a side result, we give an almost optimal algorithm for a variant of the strip packing problem in higher dimensions. This might have applications for other multidimensional geometric packing problems.