Search Results

Documents authored by Sharma, Amatya

Document
DOI: 10.4230/LIPIcs.FSTTCS.2024.6
A Decomposition Approach to the Weighted k-Server Problem

Authors: Nikhil Ayyadevara, Ashish Chiplunkar, and Amatya Sharma

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
A natural variant of the classical online k-server problem is the weighted k-server problem, where the cost of moving a server is its weight times the distance through which it moves. Despite its apparent simplicity, the weighted k-server problem is extremely poorly understood. Specifically, even on uniform metric spaces, finding the optimum competitive ratio of randomized algorithms remains an open problem - the best upper bound known is 2^{2^{k+O(1)}} due to a deterministic algorithm (Bansal et al., 2018), and the best lower bound known is Ω(2^k) (Ayyadevara and Chiplunkar, 2021). With the aim of closing this exponential gap between the upper and lower bounds, we propose a decomposition approach for designing a randomized algorithm for weighted k-server on uniform metrics. Our first contribution includes two relaxed versions of the problem and a technique to obtain an algorithm for weighted k-server from algorithms for the two relaxed versions. Specifically, we prove that if there exists an α₁-competitive algorithm for one version (which we call Weighted k-Server - Service Pattern Construction) and there exists an α₂-competitive algorithm for the other version (which we call Weighted k-server - Revealed Service Pattern), then there exists an (α₁α₂)-competitive algorithm for weighted k-server on uniform metric spaces. Our second contribution is a 2^O(k²)-competitive randomized algorithm for Weighted k-server - Revealed Service Pattern. As a consequence, the task of designing a 2^poly(k)-competitive randomized algorithm for weighted k-server on uniform metrics reduces to designing a 2^poly(k)-competitive randomized algorithm for Weighted k-Server - Service Pattern Construction. Finally, we also prove that the Ω(2^k) lower bound for weighted k-server, in fact, holds for Weighted k-server - Revealed Service Pattern.
Cite as

Nikhil Ayyadevara, Ashish Chiplunkar, and Amatya Sharma. A Decomposition Approach to the Weighted k-Server Problem. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ayyadevara_et_al:LIPIcs.FSTTCS.2024.6,
  author =	{Ayyadevara, Nikhil and Chiplunkar, Ashish and Sharma, Amatya},
  title =	{{A Decomposition Approach to the Weighted k-Server Problem}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.6},
  URN =		{urn:nbn:de:0030-drops-221954},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.6},
  annote =	{Keywords: Online Algorithms, k-server, paging}
}
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.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}
}
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