Author name cluster

Arindam Khan 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

SODA Conference 2024 Conference Paper

Bin Packing under Random-Order: Breaking the Barrier of 3/2

Anish Hebbar
Arindam Khan 0001
K. V. N. Sreenivas

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. In this paper, we make the first progress towards the conjecture, by showing that Best-Fit achieves a random-order ratio of at most 1. 5 — ɛ, for a small constant ɛ > 0. Furthermore, we establish an improved lower bound of 1. 144 on the random-order ratio of Best-Fit, nearly reaching the conjectured ratio.

Details

SODA Conference 2022 Conference Paper

A 3-Approximation Algorithm for Maximum Independent Set of Rectangles

Waldo Gálvez
Arindam Khan 0001
Mathieu Mari
Tobias Mömke
Madhusudhan Reddy Pittu
Andreas Wiese

We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell [46] obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles (CCRs ), without intersecting certain special horizontal line segments called fences. In this paper, we present a 3-approximation algorithm for MISR which is also based on a recursive partitioning scheme. First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than CCRs. This allows us to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 6. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to 3. In particular, we construct a recursive partitioning based on more general fences which can be sequences of up to O (1) line segments each. This partitioning routine and our other new ideas may be useful for future work towards a PTAS for MISR.

Details

MFCS Conference 2020 Conference Paper

Best Fit Bin Packing with Random Order Revisited

Susanne Albers
Arindam Khan 0001
Leon Ladewig

Best Fit is a well known online algorithm for the bin packing problem, where a collection of one-dimensional items has to be packed into a minimum number of unit-sized bins. In a seminal work, Kenyon [SODA 1996] introduced the (asymptotic) random order ratio as an alternative performance measure for online algorithms. Here, an adversary specifies the items, but the order of arrival is drawn uniformly at random. Kenyon’s result establishes lower and upper bounds of 1. 08 and 1. 5, respectively, for the random order ratio of Best Fit. Although this type of analysis model became increasingly popular in the field of online algorithms, no progress has been made for the Best Fit algorithm after the result of Kenyon. We study the random order ratio of Best Fit and tighten the long-standing gap by establishing an improved lower bound of 1. 10. For the case where all items are larger than 1/3, we show that the random order ratio converges quickly to 1. 25. It is the existence of such large items that crucially determines the performance of Best Fit in the general case. Moreover, this case is closely related to the classical maximum-cardinality matching problem in the fully online model. As a side product, we show that Best Fit satisfies a monotonicity property on such instances, unlike in the general case. In addition, we initiate the study of the absolute random order ratio for this problem. In contrast to asymptotic ratios, absolute ratios must hold even for instances that can be packed into a small number of bins. We show that the absolute random order ratio of Best Fit is at least 1. 3. For the case where all items are larger than 1/3, we derive upper and lower bounds of 21/16 and 1. 2, respectively.

Details

FOCS Conference 2017 Conference Paper

Approximating Geometric Knapsack via L-Packings

Waldo Gálvez
Fabrizio Grandoni 0001
Sandy Heydrich
Salvatore Ingala
Arindam Khan 0001
Andreas Wiese

We study the two-dimensional geometric knapsack problem (2DK) in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack (without rotating items). The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is 2+ ε [Jansen and Zhang, SODA 2004]. In this paper we break the 2 approximation barrier, achieving a polynomialtime 17/9 + ε <; 1. 89 approximation, which improves to 558/325 + ε <; 1. 72 in the cardinality case. Essentially all prior work on 2DK approximation packs items inside a constant number of rectangular containers, where items inside each container are packed using a simple greedy strategy. We deviate for the first time from this setting: we show that there exists a large profit solution where items are packed inside a constant number of containers plus one L-shaped region at the boundary of the knapsack which contains items that are high and narrow and items that are wide and thin. The items of these two types possibly interact in a complex manner at the corner of the L. The above structural result is not enough however: the best-known approximation ratio for the subproblem in the L-shaped region is 2 + ε (obtained via a trivial reduction to one-dimensional knapsack by considering tall or wide items only). Indeed this is one of the simplest special settings of the problem for which this is the best known approximation factor. As a second major, and the main algorithmic contribution of this paper, we present a PTAS for this case. We believe that this will turn out to be useful in future work in geometric packing problems. We also consider the variant of the problem with rotations (2DKR), where items can be rotated by 90 degrees. Also in this case the best-known polynomial-time approximation factor (even for the cardinality case) is 2+ε[Jansen and Zhang, SODA 2004]. Exploiting part of the machinery developed for 2DK plus a few additional ideas, we obtain a polynomial-time 3/2 + ε-approximation for 2DKR, which improves to 4/3 + ε in the cardinality case.

Details

SODA Conference 2016 Conference Paper

Improved Approximation for Vector Bin Packing

Nikhil Bansal 0001
Marek Eliás 0001
Arindam Khan 0001

We study the d -dimensional vector bin packing problem, a well-studied generalization of bin packing arising in resource allocation and scheduling problems. Here we are given a set of d -dimensional vectors v 1, …, v n in [0, 1] d, and the goal is to pack them into the least number of bins so that for each bin B, the sum of the vectors in it is at most 1 in every dimension, i. e. ,. For the 2-dimensional case we give an asymptotic approximation guarantee of 1 + ln(1. 5) + ∊ ≈ (1. 405 + ∊), improving upon the previous bound of 1 + ln 2 + ∊ ≈ (1. 693 + ∊). We also give an almost tight (1. 5+ ∊) absolute approximation guarantee, improving upon the previous bound of 2 [23]. For the d -dimensional case, we get a guarantee, improving upon the previous (1 + ln d + ∊) guarantee [2]. Here (1 + ln d ) was a natural barrier as rounding-based algorithms can not achieve better than d approximation. We get around this by exploiting various structural properties of (near)-optimal packings, and using multi-objective multi-budget matching based techniques and expanding the Round & Approx framework to go beyond rounding-based algorithms. Along the way we also prove several results that could be of independent interest.

Details

SODA Conference 2014 Conference Paper

Improved Approximation Algorithm for Two-Dimensional Bin Packing

Nikhil Bansal 0001
Arindam Khan 0001

We study the two-dimensional bin packing problem with and without rotations. Here we are given a set of two-dimensional rectangular items I and the goal is to pack these into a minimum number of unit square bins. We consider the orthogonal packing case where the edges of the items must be aligned parallel to the edges of the bin. Our main result is a 1. 405-approximation for two-dimensional bin packing with and without rotation, which improves upon a recent 1. 5 approximation due to Jansen and Prädel. We also show that a wide class of rounding based algorithms cannot improve upon the factor of 1. 5.

Details