Search Results

Documents authored by Khan, Arindam

Document
DOI: 10.4230/LIPIcs.ESA.2024.58
Random-Order Online Independent Set of Intervals and Hyperrectangles

Authors: Mohit Garg, Debajyoti Kar, and Arindam Khan

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
In the Maximum Independent Set of Hyperrectangles problem, we are given a set of n (possibly overlapping) d-dimensional axis-aligned hyperrectangles, and the goal is to find a subset of non-overlapping hyperrectangles of maximum cardinality. For d = 1, this corresponds to the classical Interval Scheduling problem, where a simple greedy algorithm returns an optimal solution. In the offline setting, for d-dimensional hyperrectangles, polynomial time (log n)^{O(d)}-approximation algorithms are known [Chalermsook and Chuzhoy, 2009]. However, the problem becomes notably challenging in the online setting, where the input objects (hyperrectangles) appear one by one in an adversarial order, and on the arrival of an object, the algorithm needs to make an immediate and irrevocable decision whether or not to select the object while maintaining the feasibility. Even for interval scheduling, an Ω(n) lower bound is known on the competitive ratio. To circumvent these negative results, in this work, we study the online maximum independent set of axis-aligned hyperrectangles in the random-order arrival model, where the adversary specifies the set of input objects which then arrive in a uniformly random order. Starting from the prototypical secretary problem, the random-order model has received significant attention to study algorithms beyond the worst-case competitive analysis (see the survey by Gupta and Singla [Anupam Gupta and Sahil Singla, 2020]). Surprisingly, we show that the problem in the random-order model almost matches the best-known offline approximation guarantees, up to polylogarithmic factors. In particular, we give a simple (log n)^{O(d)}-competitive algorithm for d-dimensional hyperrectangles in this model, which runs in O_d̃(n) time. Our approach also yields (log n)^{O(d)}-competitive algorithms in the random-order model for more general objects such as d-dimensional fat objects and ellipsoids. Furthermore, all our competitiveness guarantees hold with high probability, and not just in expectation.
Cite as

Mohit Garg, Debajyoti Kar, and Arindam Khan. Random-Order Online Independent Set of Intervals and Hyperrectangles. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ESA.2024.58,
  author =	{Garg, Mohit and Kar, Debajyoti and Khan, Arindam},
  title =	{{Random-Order Online Independent Set of Intervals and Hyperrectangles}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{58:1--58:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.58},
  URN =		{urn:nbn:de:0030-drops-211298},
  doi =		{10.4230/LIPIcs.ESA.2024.58},
  annote =	{Keywords: Online Algorithms, Random-Order Model, Maximum Independent Set of Rectangles, Hyperrectangles, Fat Objects, Interval Scheduling}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.8
Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects

Authors: Pritam Acharya, Sujoy Bhore, Aaryan Gupta, Arindam Khan, Bratin Mondal, and Andreas Wiese

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We study the geometric knapsack problem in which we are given a set of d-dimensional objects (each with associated profits) and the goal is to find the maximum profit subset that can be packed non-overlappingly into a given d-dimensional (unit hypercube) knapsack. Even if d = 2 and all input objects are disks, this problem is known to be NP-hard [Demaine, Fekete, Lang, 2010]. In this paper, we give polynomial time (1+ε)-approximation algorithms for the following types of input objects in any constant dimension d: - disks and hyperspheres, - a class of fat convex polygons that generalizes regular k-gons for k ≥ 5 (formally, polygons with a constant number of edges, whose lengths are in a bounded range, and in which each angle is strictly larger than π/2), - arbitrary fat convex objects that are sufficiently small compared to the knapsack. We remark that in our PTAS for disks and hyperspheres, we output the computed set of objects, but for a O_ε(1) of them we determine their coordinates only up to an exponentially small error. However, it is not clear whether there always exists a (1+ε)-approximate solution that uses only rational coordinates for the disks' centers. We leave this as an open problem which is related to well-studied geometric questions in the realm of circle packing.
Cite as

Pritam Acharya, Sujoy Bhore, Aaryan Gupta, Arindam Khan, Bratin Mondal, and Andreas Wiese. Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{acharya_et_al:LIPIcs.ICALP.2024.8,
  author =	{Acharya, Pritam and Bhore, Sujoy and Gupta, Aaryan and Khan, Arindam and Mondal, Bratin and Wiese, Andreas},
  title =	{{Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.8},
  URN =		{urn:nbn:de:0030-drops-201511},
  doi =		{10.4230/LIPIcs.ICALP.2024.8},
  annote =	{Keywords: Approximation Algorithms, Polygon Packing, Circle Packing, Sphere Packing, Geometric Knapsack, Resource Augmentation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.46
Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set

Authors: Arindam Khan, Aditya Lonkar, Saladi Rahul, Aditya Subramanian, and Andreas Wiese

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Set cover and hitting set are fundamental problems in combinatorial optimization which are well-studied in the offline, online, and dynamic settings. We study the geometric versions of these problems and present new online and dynamic algorithms for them. In the online version of set cover (resp. hitting set), m sets (resp. n points) are given and n points (resp. m sets) arrive online, one-by-one. In the dynamic versions, points (resp. sets) can arrive as well as depart. Our goal is to maintain a set cover (resp. hitting set), minimizing the size of the computed solution. For online set cover for (axis-parallel) squares of arbitrary sizes, we present a tight O(log n)-competitive algorithm. In the same setting for hitting set, we provide a tight O(log N)-competitive algorithm, assuming that all points have integral coordinates in [0,N)². No online algorithm had been known for either of these settings, not even for unit squares (apart from the known online algorithms for arbitrary set systems). For both dynamic set cover and hitting set with d-dimensional hyperrectangles, we obtain (log m)^O(d)-approximation algorithms with (log m)^O(d) worst-case update time. This partially answers an open question posed by Chan et al. [SODA'22]. Previously, no dynamic algorithms with polylogarithmic update time were known even in the setting of squares (for either of these problems). Our main technical contributions are an extended quad-tree approach and a frequency reduction technique that reduces geometric set cover instances to instances of general set cover with bounded frequency.
Cite as

Arindam Khan, Aditya Lonkar, Saladi Rahul, Aditya Subramanian, and Andreas Wiese. Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 46:1-46:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.SoCG.2023.46,
  author =	{Khan, Arindam and Lonkar, Aditya and Rahul, Saladi and Subramanian, Aditya and Wiese, Andreas},
  title =	{{Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{46:1--46:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.46},
  URN =		{urn:nbn:de:0030-drops-178967},
  doi =		{10.4230/LIPIcs.SoCG.2023.46},
  annote =	{Keywords: Geometric Set Cover, Hitting Set, Rectangles, Squares, Hyperrectangles, Online Algorithms, Dynamic Data Structures}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.23
Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing

Authors: Arindam Khan, Eklavya Sharma, and K. V. N. Sreenivas

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
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.
Cite as

Arindam Khan, Eklavya Sharma, and K. V. N. Sreenivas. Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.FSTTCS.2022.23,
  author =	{Khan, Arindam and Sharma, Eklavya and Sreenivas, K. V. N.},
  title =	{{Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.23},
  URN =		{urn:nbn:de:0030-drops-174151},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.23},
  annote =	{Keywords: Bin packing, rectangle packing, multidimensional packing, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.71
Approximation Algorithms for Round-UFP and Round-SAP

Authors: Debajyoti Kar, Arindam Khan, and Andreas Wiese

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study Round-UFP and Round-SAP, two generalizations of the classical Bin Packing problem that correspond to the unsplittable flow problem on a path (UFP) and the storage allocation problem (SAP), respectively. We are given a path with capacities on its edges and a set of jobs where for each job we are given a demand and a subpath. In Round-UFP, the goal is to find a packing of all jobs into a minimum number of copies (rounds) of the given path such that for each copy, the total demand of jobs on any edge does not exceed the capacity of the respective edge. In Round-SAP, the jobs are considered to be rectangles and the goal is to find a non-overlapping packing of these rectangles into a minimum number of rounds such that all rectangles lie completely below the capacity profile of the edges. We show that in contrast to Bin Packing, both problems do not admit an asymptotic polynomial-time approximation scheme (APTAS), even when all edge capacities are equal. However, for this setting, we obtain asymptotic (2+ε)-approximations for both problems. For the general case, we obtain an O(log log n)-approximation algorithm and an O(log log 1/δ)-approximation under (1+δ)-resource augmentation for both problems. For the intermediate setting of the no bottleneck assumption (i.e., the maximum job demand is at most the minimum edge capacity), we obtain an absolute 12- and an asymptotic (16+ε)-approximation algorithm for Round-UFP and Round-SAP, respectively.
Cite as

Debajyoti Kar, Arindam Khan, and Andreas Wiese. Approximation Algorithms for Round-UFP and Round-SAP. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kar_et_al:LIPIcs.ESA.2022.71,
  author =	{Kar, Debajyoti and Khan, Arindam and Wiese, Andreas},
  title =	{{Approximation Algorithms for Round-UFP and Round-SAP}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{71:1--71:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.71},
  URN =		{urn:nbn:de:0030-drops-170098},
  doi =		{10.4230/LIPIcs.ESA.2022.71},
  annote =	{Keywords: Approximation Algorithms, Scheduling, Rectangle Packing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.12
Near-Optimal Algorithms for Stochastic Online Bin Packing

Authors: Nikhil ^* Ayyadevara, Rajni Dabas, Arindam Khan, and K. V. N. Sreenivas

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
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 proximation algorithm and provides a polynomial-time (α + ε)-competitive algorithm for online bin packing under the i.i.d. model, where ε > 0 is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time (1+ε)-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 ≈ 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 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].
Cite as

Nikhil ^* Ayyadevara, Rajni Dabas, Arindam Khan, and K. V. N. Sreenivas. Near-Optimal Algorithms for Stochastic Online Bin Packing. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ayyadevara_et_al:LIPIcs.ICALP.2022.12,
  author =	{Ayyadevara, Nikhil ^* and Dabas, Rajni and Khan, Arindam and Sreenivas, K. V. N.},
  title =	{{Near-Optimal Algorithms for Stochastic Online Bin Packing}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.12},
  URN =		{urn:nbn:de:0030-drops-163532},
  doi =		{10.4230/LIPIcs.ICALP.2022.12},
  annote =	{Keywords: Bin Packing, 3-Partition Problem, Online Algorithms, Random Order Arrival, IID model, Best-Fit Algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.78
A PTAS for Packing Hypercubes into a Knapsack

Authors: Klaus Jansen, Arindam Khan, Marvin Lira, and K. V. N. Sreenivas

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We study the d-dimensional hypercube knapsack problem ({d}-D Hc-Knapsack) 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+ε). 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 𝒱-Boxes and 𝒩-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.
Cite as

Klaus Jansen, Arindam Khan, Marvin Lira, and K. V. N. Sreenivas. A PTAS for Packing Hypercubes into a Knapsack. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 78:1-78:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2022.78,
  author =	{Jansen, Klaus and Khan, Arindam and Lira, Marvin and Sreenivas, K. V. N.},
  title =	{{A PTAS for Packing Hypercubes into a Knapsack}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{78:1--78:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.78},
  URN =		{urn:nbn:de:0030-drops-164192},
  doi =		{10.4230/LIPIcs.ICALP.2022.78},
  annote =	{Keywords: Multidimensional knapsack, geometric packing, cube packing, strip packing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.80
Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing

Authors: Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, and Andreas Wiese

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
In the Strip Packing problem (SP), we are given a vertical half-strip [0,W]×[0,∞) and a set of n axis-aligned rectangles of width at most W. The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied and frequently used practical constraint is to allow only those packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts (guillotine cuts) that do not intersect any item of the solution. In this paper, we study approximation algorithms for the Guillotine Strip Packing problem (GSP), i.e., the Strip Packing problem where we require additionally that the packing needs to be guillotine separable. This problem generalizes the classical Bin Packing problem and also makespan minimization on identical machines, and thus it is already strongly NP-hard. Moreover, due to a reduction from the Partition problem, it is NP-hard to obtain a polynomial-time (3/2-ε)-approximation algorithm for GSP for any ε > 0 (exactly as Strip Packing). We provide a matching polynomial time (3/2+ε)-approximation algorithm for GSP. Furthermore, we present a pseudo-polynomial time (1+ε)-approximation algorithm for GSP. This is surprising as it is NP-hard to obtain a (5/4-ε)-approximation algorithm for (general) Strip Packing in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings.
Cite as

Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, and Andreas Wiese. Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 80:1-80:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.ICALP.2022.80,
  author =	{Khan, Arindam and Lonkar, Aditya and Maiti, Arnab and Sharma, Amatya and Wiese, Andreas},
  title =	{{Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{80:1--80:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.80},
  URN =		{urn:nbn:de:0030-drops-164215},
  doi =		{10.4230/LIPIcs.ICALP.2022.80},
  annote =	{Keywords: Approximation Algorithms, Two-Dimensional Packing, Rectangle Packing, Guillotine Cuts, Computational Geometry}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.21
Peak Demand Minimization via Sliced Strip Packing

Authors: Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, and Malte Tutas

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
We study the Nonpreemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Nonpreemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a (5/3+ε)-approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption (1+ε) OPT. The remaining jobs fit into a thin container of height 1. The previous best result for NPDM was a 2.7 approximation based on FFDH [Ranjan et al., 2015]. One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg’s algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above.
Cite as

Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, and Malte Tutas. Peak Demand Minimization via Sliced Strip Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{deppert_et_al:LIPIcs.APPROX/RANDOM.2021.21,
  author =	{Deppert, Max A. and Jansen, Klaus and Khan, Arindam and Rau, Malin and Tutas, Malte},
  title =	{{Peak Demand Minimization via Sliced Strip Packing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.21},
  URN =		{urn:nbn:de:0030-drops-147145},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.21},
  annote =	{Keywords: scheduling, peak demand minimization, approximation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.22
Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items

Authors: Arindam Khan and Eklavya Sharma

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
In the Two-dimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. The problem admits no APTAS and the current best approximation ratio is 1.406 by Bansal and Khan [SODA'14]. A well-studied variant of the problem is Guillotine Two-dimensional Bin Packing (G2BP), where all rectangles must be packed in such a way that every rectangle in the packing can be obtained by recursively applying a sequence of end-to-end axis-parallel cuts, also called guillotine cuts. Bansal, Lodi, and Sviridenko [FOCS'05] obtained an APTAS for this problem. Let λ be the smallest constant such that for every set I of items, the number of bins in the optimal solution to G2BP for I is upper bounded by λ opt(I) + c, where opt(I) is the number of bins in the optimal solution to 2BP for I and c is a constant. It is known that 4/3 ≤ λ ≤ 1.692. Bansal and Khan [SODA'14] conjectured that λ = 4/3. The conjecture, if true, will imply a (4/3+ε)-approximation algorithm for 2BP. According to convention, for a given constant δ > 0, a rectangle is large if both its height and width are at least δ, and otherwise it is called skewed. We make progress towards the conjecture by showing λ = 4/3 for skewed instance, i.e., when all input rectangles are skewed. Even for this case, the previous best upper bound on λ was roughly 1.692. We also give an APTAS for 2BP for skewed instance, though general 2BP does not admit an APTAS.
Cite as

Arindam Khan and Eklavya Sharma. Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.APPROX/RANDOM.2021.22,
  author =	{Khan, Arindam and Sharma, Eklavya},
  title =	{{Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{22:1--22:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.22},
  URN =		{urn:nbn:de:0030-drops-147151},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.22},
  annote =	{Keywords: Geometric bin packing, guillotine separability, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.39
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More

Authors: Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, and Andreas Wiese

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsack and a collection of n rectangular items with integer sizes and profits. Our goal is to find the most profitable subset of items that can be packed non-overlappingly into the knapsack. The currently best known polynomial-time approximation factor for 2DK is 17/9+ε < 1.89 and there is a (3/2+ε)-approximation algorithm if we are allowed to rotate items by 90 degrees [Gálvez et al., FOCS 2017]. In this paper, we give (4/3+ε)-approximation algorithms in polynomial time for both cases, assuming that all input data are integers polynomially bounded in n. Gálvez et al.’s algorithm for 2DK partitions the knapsack into a constant number of rectangular regions plus one L-shaped region and packs items into those in a structured way. We generalize this approach by allowing up to a constant number of more general regions that can have the shape of an L, a U, a Z, a spiral, and more, and therefore obtain an improved approximation ratio. In particular, we present an algorithm that computes the essentially optimal structured packing into these regions.
Cite as

Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, and Andreas Wiese. Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.SoCG.2021.39,
  author =	{G\'{a}lvez, Waldo and Grandoni, Fabrizio and Khan, Arindam and Ram{\'\i}rez-Romero, Diego and Wiese, Andreas},
  title =	{{Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.39},
  URN =		{urn:nbn:de:0030-drops-138386},
  doi =		{10.4230/LIPIcs.SoCG.2021.39},
  annote =	{Keywords: Approximation algorithms, two-dimensional knapsack, geometric packing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.48
On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem

Authors: Arindam Khan, Arnab Maiti, Amatya Sharma, and Andreas Wiese

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
In two-dimensional geometric knapsack problem, we are given a set of n axis-aligned rectangular items and an axis-aligned square-shaped knapsack. Each item has integral width, integral height and an associated integral profit. The goal is to find a (non-overlapping axis-aligned) packing of a maximum profit subset of rectangles into the knapsack. A well-studied and frequently used constraint in practice is to allow only packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts that do not intersect any item of the solution. In this paper we study approximation algorithms for the geometric knapsack problem under guillotine cut constraints. We present polynomial time (1+ε)-approximation algorithms for the cases with and without allowing rotations by 90 degrees, assuming that all input numeric data are polynomially bounded in n. In comparison, the best-known approximation factor for this setting is 3+ε [Jansen-Zhang, SODA 2004], even in the cardinality case where all items have the same profit. Our main technical contribution is a structural lemma which shows that any guillotine packing can be converted into another structured guillotine packing with almost the same profit. In this packing, each item is completely contained in one of a constant number of boxes and 𝖫-shaped regions, inside which the items are placed by a simple greedy routine. In particular, we provide a clean sufficient condition when such a packing obeys the guillotine cut constraints which might be useful for other settings where these constraints are imposed.
Cite as

Arindam Khan, Arnab Maiti, Amatya Sharma, and Andreas Wiese. On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.SoCG.2021.48,
  author =	{Khan, Arindam and Maiti, Arnab and Sharma, Amatya and Wiese, Andreas},
  title =	{{On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{48:1--48:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.48},
  URN =		{urn:nbn:de:0030-drops-138474},
  doi =		{10.4230/LIPIcs.SoCG.2021.48},
  annote =	{Keywords: Approximation Algorithms, Multidimensional Knapsack, Guillotine Cuts, Geometric Packing, Rectangle Packing}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.7
Best Fit Bin Packing with Random Order Revisited

Authors: Susanne Albers, Arindam Khan, and Leon Ladewig

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
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.
Cite as

Susanne Albers, Arindam Khan, and Leon Ladewig. Best Fit Bin Packing with Random Order Revisited. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.MFCS.2020.7,
  author =	{Albers, Susanne and Khan, Arindam and Ladewig, Leon},
  title =	{{Best Fit Bin Packing with Random Order Revisited}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.7},
  URN =		{urn:nbn:de:0030-drops-127300},
  doi =		{10.4230/LIPIcs.MFCS.2020.7},
  annote =	{Keywords: Online bin packing, random arrival order, probabilistic analysis}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.44
A Tight (3/2+ε) Approximation for Skewed Strip Packing

Authors: Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, and Malin Rau

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
In the Strip Packing problem, we are given a vertical half-strip [0,W]× [0,+∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. Strip Packing generalizes classical well-studied problems such as Makespan Minimization on identical machines (when rectangle widths are identical) and Bin Packing (when rectangle heights are identical). It has applications in manufacturing, scheduling and energy consumption in smart grids among others. It is NP-hard to approximate this problem within a factor (3/2-ε) for any constant ε > 0 by a simple reduction from the Partition problem. The current best approximation factor for Strip Packing is (5/3+ε) by Harren et al. [Computational Geometry '14], and it is achieved with a fairly complex algorithm and analysis. It seems plausible that Strip Packing admits a (3/2+ε)-approximation. We make progress in that direction by achieving such tight approximation guarantees for a special family of instances, which we call skewed instances. As standard in the area, for a given constant parameter δ > 0, we call large the rectangles with width at least δ W and height at least δ OPT, and skewed the remaining rectangles. If all the rectangles in the input are large, then one can easily compute the optimal packing in polynomial time (since the input can contain only a constant number of rectangles). We consider the complementary case where all the rectangles are skewed. This second case retains a large part of the complexity of the original problem; in particular, it is NP-hard to approximate within a factor (3/2-ε) and we provide an (almost) tight (3/2+ε)-approximation algorithm.
Cite as

Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, and Malin Rau. A Tight (3/2+ε) Approximation for Skewed Strip Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.APPROX/RANDOM.2020.44,
  author =	{G\'{a}lvez, Waldo and Grandoni, Fabrizio and Ameli, Afrouz Jabal and Jansen, Klaus and Khan, Arindam and Rau, Malin},
  title =	{{A Tight (3/2+\epsilon) Approximation for Skewed Strip Packing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.44},
  URN =		{urn:nbn:de:0030-drops-126478},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.44},
  annote =	{Keywords: strip packing, approximation algorithm}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.47
On Guillotine Separability of Squares and Rectangles

Authors: Arindam Khan and Madhusudhan Reddy Pittu

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
Guillotine separability of rectangles has recently gained prominence in combinatorial optimization, computational geometry, and combinatorics. Consider a given large stock unit (say glass or wood) and we need to cut out a set of required rectangles from it. Many cutting technologies allow only end-to-end cuts called guillotine cuts. Guillotine cuts occur in stages. Each stage consists of either only vertical cuts or only horizontal cuts. In k-stage packing, the number of cuts to obtain each rectangle from the initial packing is at most k (plus an additional trimming step to separate the rectangle itself from a waste area). Pach and Tardos [Pach and Tardos, 2000] studied the following question: Given a set of n axis-parallel rectangles (in the weighted case, each rectangle has an associated weight), cut out as many rectangles (resp. weight) as possible using a sequence of guillotine cuts. They provide a guillotine cutting sequence that recovers 1/(2 log n)-fraction of rectangles (resp. weights). Abed et al. [Fidaa Abed et al., 2015] claimed that a guillotine cutting sequence can recover a constant fraction for axis-parallel squares. They also conjectured that for any set of rectangles, there exists a sequence of axis-parallel guillotine cuts that recovers a constant fraction of rectangles. This conjecture, if true, would yield a combinatorial O(1)-approximation for Maximum Independent Set of Rectangles (MISR), a long-standing open problem. We show the conjecture is not true, if we only allow o(log log n) stages (resp. o(log n/log log n)-stages for the weighted case). On the positive side, we show a simple O(n log n)-time 2-stage cut sequence that recovers 1/(1+log n)-fraction of rectangles. We improve the extraction of squares by showing that 1/40-fraction (resp. 1/160 in the weighted case) of squares can be recovered using guillotine cuts. We also show O(1)-fraction of rectangles, even in the weighted case, can be recovered for many special cases of rectangles, e.g. fat (bounded width/height), δ-large (large in one of the dimensions), etc. We show that this implies O(1)-factor approximation for Maximum Weighted Independent Set of Rectangles, the weighted version of MISR, for these classes of rectangles.
Cite as

Arindam Khan and Madhusudhan Reddy Pittu. On Guillotine Separability of Squares and Rectangles. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.APPROX/RANDOM.2020.47,
  author =	{Khan, Arindam and Pittu, Madhusudhan Reddy},
  title =	{{On Guillotine Separability of Squares and Rectangles}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{47:1--47:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.47},
  URN =		{urn:nbn:de:0030-drops-126505},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.47},
  annote =	{Keywords: Guillotine cuts, Rectangles, Squares, Packing, k-stage packing}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.22
Improved Online Algorithms for Knapsack and GAP in the Random Order Model

Authors: Susanne Albers, Arindam Khan, and Leon Ladewig

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set. We develop a randomized (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)]. Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)].
Cite as

Susanne Albers, Arindam Khan, and Leon Ladewig. Improved Online Algorithms for Knapsack and GAP in the Random Order Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.APPROX-RANDOM.2019.22,
  author =	{Albers, Susanne and Khan, Arindam and Ladewig, Leon},
  title =	{{Improved Online Algorithms for Knapsack and GAP in the Random Order Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{22:1--22:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.22},
  URN =		{urn:nbn:de:0030-drops-112376},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.22},
  annote =	{Keywords: Online algorithms, knapsack problem, random order model}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.9
Improved Pseudo-Polynomial-Time Approximation for Strip Packing

Authors: Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
We study the strip packing problem, a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in the two-dimensional plane and the goal is to pack them in a vertical strip of fixed width such that the height of the obtained packing is minimized. The packing must be non-overlapping and the rectangles cannot be rotated. A reduction from the partition problem shows that no approximation better than 3/2 is possible for strip packing in polynomial time (assuming P!=NP). Nadiradze and Wiese [SODA16] overcame this barrier by presenting a (7/5+epsilon)-approximation algorithm in pseudo-polynomial-time (PPT). As the problem is strongly NP-hard, it does not admit an exact PPT algorithm (though a PPT approximation scheme might exist). In this paper we make further progress on the PPT approximability of strip packing, by presenting a (4/3+epsilon)-approximation algorithm. Our result is based on a non-trivial repacking of some rectangles in the "empty space" left by the construction by Nadiradze and Wiese, and in some sense pushes their approach to its limit. Our PPT algorithm can be adapted to the case where we are allowed to rotate the rectangles by 90 degrees, achieving the same approximation factor and breaking the polynomial-time approximation barrier of 3/2 for the case with rotations as well.
Cite as

Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan. Improved Pseudo-Polynomial-Time Approximation for Strip Packing. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.FSTTCS.2016.9,
  author =	{G\'{a}lvez, Waldo and Grandoni, Fabrizio and Ingala, Salvatore and Khan, Arindam},
  title =	{{Improved Pseudo-Polynomial-Time Approximation for Strip Packing}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.9},
  URN =		{urn:nbn:de:0030-drops-68445},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.9},
  annote =	{Keywords: approximation algorithms, strip packing, rectangle packing, cutting-stock problem}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.136
On Weighted Bipartite Edge Coloring

Authors: Arindam Khan and Mohit Singh

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
We study weighted bipartite edge coloring problem, which is a generalization of two classical problems: bin packing and edge coloring. This problem has been inspired from the study of Clos networks in multirate switching environment in communication networks. In weighted bipartite edge coloring problem, we are given an edge-weighted bipartite multi-graph G=(V,E) with weights w:E\rightarrow [0,1]. The goal is to find a proper weighted coloring of the edges with as few colors as possible. An edge coloring of the weighted graph is called a proper weighted coloring if the sum of the weights of the edges incident to a vertex of any color is at most one. Chung and Ross conjectured 2m-1 colors are sufficient for a proper weighted coloring, where m denotes the minimum number of unit sized bins needed to pack the weights of all edges incident at any vertex. We give an algorithm that returns a coloring with at most \lceil 2.2223m \rceil colors improving on the previous result of \frac{9m}{4} by Feige and Singh. Our algorithm is purely combinatorial and combines the König's theorem for edge coloring bipartite graphs and first-fit decreasing heuristic for bin packing. However, our analysis uses configuration linear program for the bin packing problem to give the improved result.
Cite as

Arindam Khan and Mohit Singh. On Weighted Bipartite Edge Coloring. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 136-150, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.FSTTCS.2015.136,
  author =	{Khan, Arindam and Singh, Mohit},
  title =	{{On Weighted Bipartite Edge Coloring}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{136--150},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.136},
  URN =		{urn:nbn:de:0030-drops-56437},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.136},
  annote =	{Keywords: Edge coloring, Bin packing, Clos networks, Approximation algorithms, Graph algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact