7 Search Results for "Maiti, Arnab"

Document
DOI: 10.4230/LIPIcs.IPEC.2025.9
An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange

Authors: Bart M. P. Jansen, Jeroen S. K. Lamme, and Ruben F. A. Verhaegh

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We study the parameterized complexity of a recently introduced multi-agent variant of the Kidney Exchange problem. Given a directed graph G and integers d and k, the standard problem asks whether G contains a packing of vertex-disjoint cycles, each of length ≤ d, covering at least k vertices in total. In the multi-agent setting we consider, the vertex set is partitioned over several agents who reject a cycle packing as solution if it can be modified into an alternative packing that covers more of their own vertices. A cycle packing is called rejection-proof if no agent rejects it and the problem asks whether such a packing exists that covers at least k vertices. We exploit the sunflower lemma on a set packing formulation of the problem to give a kernel for this Σ₂^P-complete problem that is polynomial in k for all constant values of d. We also provide a 2^𝒪(k log k) + n^𝒪(1) algorithm based on it and show that this FPT algorithm is asymptotically optimal under the ETH. Further, we generalize the problem by including an additional positive integer c in the input that naturally captures how much agents can modify a given cycle packing to reject it. For every constant c, the resulting problem simplifies from being Σ₂^P-complete to NP-complete. The super-exponential lower bound already holds for c = 2, though. We present an ad-hoc single-exponential algorithm for c = 1. These results reveal an interesting discrepancy between the classical and parameterized complexity of the problem and give a good view of what makes it hard.
Cite as

Bart M. P. Jansen, Jeroen S. K. Lamme, and Ruben F. A. Verhaegh. An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2025.9,
  author =	{Jansen, Bart M. P. and Lamme, Jeroen S. K. and Verhaegh, Ruben F. A.},
  title =	{{An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.9},
  URN =		{urn:nbn:de:0030-drops-251414},
  doi =		{10.4230/LIPIcs.IPEC.2025.9},
  annote =	{Keywords: Parameterized complexity, Multi-agent kidney exchange, Kernelization, Set packing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.98
The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization

Authors: Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the online allocation of divisible items to n agents with additive valuations for p-mean welfare maximization, a problem introduced by Barman, Khan, and Maiti (2022). Our algorithmic and hardness results characterize the optimal competitive ratios for the entire spectrum of -∞ ≤ p ≤ 1. Surprisingly, our improved algorithms for all p ≤ (1)/(log n) are simply the greedy algorithm for the Nash welfare, supplemented with two auxiliary components to ensure all agents have non-zero utilities and to help a small number of agents with low utilities. In this sense, the long arm of Nashian allocation achieves near-optimal competitive ratios not only for Nash welfare but also all the way to egalitarian welfare.
Cite as

Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang. The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 98:1-98:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ICALP.2025.98,
  author =	{Huang, Zhiyi and Lee, Chui Shan and Shu, Xinkai and Wang, Zhaozi},
  title =	{{The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{98:1--98:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.98},
  URN =		{urn:nbn:de:0030-drops-234754},
  doi =		{10.4230/LIPIcs.ICALP.2025.98},
  annote =	{Keywords: Online Algorithms, Fair Division, Nash Welfare}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.60
Improved Approximation Algorithms for Three-Dimensional Knapsack

Authors: Klaus Jansen, Debajyoti Kar, Arindam Khan, K. V. N. Sreenivas, and Malte Tutas

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective is to find a non-overlapping axis-aligned packing (by translation) of the maximum profit subset of cuboids into the cube. The previous best approximation algorithm is due to Diedrich, Harren, Jansen, Thöle, and Thomas (2008), who gave a (7+ε)-approximation algorithm for 3DK and a (5+ε)-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant ε > 0. Chlebík and Chlebíková (2009) showed that the problem does not admit an asymptotic polynomial-time approximation scheme. We provide an improved polynomial-time (139/29+ε) ≈ 4.794-approximation algorithm for 3DK and (30/7+ε) ≈ 4.286-approximation when rotations by 90 degrees are allowed. We also provide improved approximation algorithms for several variants such as the cardinality case (when all items have the same profit) and uniform profit-density case (when the profit of an item is equal to its volume). Our key technical contribution is container packing - a structured packing in 3D such that all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. We first show the existence of highly profitable container packings. Thereafter, we show that one can find near-optimal container packing efficiently using a variant of the Generalized Assignment Problem (GAP).
Cite as

Klaus Jansen, Debajyoti Kar, Arindam Khan, K. V. N. Sreenivas, and Malte Tutas. Improved Approximation Algorithms for Three-Dimensional Knapsack. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.SoCG.2025.60,
  author =	{Jansen, Klaus and Kar, Debajyoti and Khan, Arindam and Sreenivas, K. V. N. and Tutas, Malte},
  title =	{{Improved Approximation Algorithms for Three-Dimensional Knapsack}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{60:1--60:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.60},
  URN =		{urn:nbn:de:0030-drops-232126},
  doi =		{10.4230/LIPIcs.SoCG.2025.60},
  annote =	{Keywords: Approximation Algorithms, Hyperrectangle Packing, Multidimensional Knapsack, Three-dimensional 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
DOI: 10.4230/LIPIcs.STACS.2022.49
One-Way Communication Complexity and Non-Adaptive Decision Trees

Authors: Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. More generally, we show the following when the gadget is Inner Product on 2b input bits for all b ≥ 2, denoted IP. - If f is a total Boolean function that depends on all of its n input bits, then the bounded-error one-way quantum communication complexity of f∘IP equals Ω(n(b-1)). - If f is a partial Boolean function, then the deterministic one-way communication complexity of f∘IP is at least Ω(b ⋅ 𝖣_{dt}^ → (f)), where 𝖣_{dt}^ → (f) denotes non-adaptive decision tree complexity of f. To prove our quantum lower bound, we first show a lower bound on the VC-dimension of f∘IP. We then appeal to a result of Klauck [STOC'00], which immediately yields our quantum lower bound. Our deterministic lower bound relies on a combinatorial result independently proven by Ahlswede and Khachatrian [Adv. Appl. Math.'98], and Frankl and Tokushige [Comb.'99]. It is known due to a result of Montanaro and Osborne [arXiv'09] that the deterministic one-way communication complexity of f∘XOR equals the non-adaptive parity decision tree complexity of f. In contrast, we show the following when the inner gadget is the AND function on 2 input bits. - There exists a function for which even the quantum non-adaptive AND decision tree complexity of f is exponentially large in the deterministic one-way communication complexity of f∘AND. - However, for symmetric functions f, the non-adaptive AND decision tree complexity of f is at most quadratic in the (even two-way) communication complexity of f∘AND. In view of the first bullet, a lower bound on non-adaptive AND decision tree complexity of f does not lift to a lower bound on one-way communication complexity of f∘AND. The proof of the first bullet above uses the well-studied Odd-Max-Bit function. For the second bullet, we first observe a connection between the one-way communication complexity of f and the Möbius sparsity of f, and then give a lower bound on the Möbius sparsity of symmetric functions. An upper bound on the non-adaptive AND decision tree complexity of symmetric functions follows implicitly from prior work on combinatorial group testing; for the sake of completeness, we include a proof of this result. It is well known that the rank of the communication matrix of a function F is an upper bound on its deterministic one-way communication complexity. This bound is known to be tight for some F. However, in our final result we show that this is not the case when F = f∘AND. More precisely we show that for all f, the deterministic one-way communication complexity of F = f∘AND is at most (rank(M_{F}))(1 - Ω(1)), where M_{F} denotes the communication matrix of F.
Cite as

Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif. One-Way Communication Complexity and Non-Adaptive Decision Trees. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.STACS.2022.49,
  author =	{Mande, Nikhil S. and Sanyal, Swagato and Sherif, Suhail},
  title =	{{One-Way Communication Complexity and Non-Adaptive Decision Trees}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{49:1--49:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.49},
  URN =		{urn:nbn:de:0030-drops-158598},
  doi =		{10.4230/LIPIcs.STACS.2022.49},
  annote =	{Keywords: Decision trees, communication complexity, composed Boolean functions}
}
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
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}
}
  • Refine by Type
  • 7 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 2 2022
  • 1 2021
  • 1 2020

  • Refine by Author
  • 4 Khan, Arindam
  • 2 Maiti, Arnab
  • 2 Sharma, Amatya
  • 2 Wiese, Andreas
  • 1 Huang, Zhiyi
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Packing and covering problems
  • 1 Applied computing → Health informatics
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Approximation algorithms analysis
  • Show More...

  • Refine by Keyword
  • 3 Approximation Algorithms
  • 2 Guillotine Cuts
  • 2 Multidimensional Knapsack
  • 2 Rectangle Packing
  • 1 Computational Geometry
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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