2 Search Results for "Dasler, Philip"

Document
DOI: 10.4230/LIPIcs.ISAAC.2019.56
Online Algorithms for Warehouse Management

Authors: Philip Dasler and David M. Mount

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
As the prevalence of E-commerce continues to grow, the efficient operation of warehouses and fulfillment centers is becoming increasingly important. To this end, many such warehouses are adding automation in order to help streamline operations, drive down costs, and increase overall efficiency. The introduction of automation comes with the opportunity for new theoretical models and computational problems with which to better understand and optimize such systems. These systems often maintain a warehouse of standardized portable storage units, which are stored and retrieved by robotic workers. In general, there are two principal issues in optimizing such a system: where in the warehouse each storage unit should be located and how best to retrieve them. These two concerns naturally go hand-in-hand, but are further complicated by the unknown request frequencies of stored products. Analogous to virtual-memory systems, the more popular and oft-requested an item is, the more efficient its retrieval should be. In this paper, we propose a theoretical model for organizing portable storage units in a warehouse subject to an online sequence of access requests. We consider two formulations, depending on whether there is a single access point or multiple access points. We present algorithms that are O(1)-competitive with respect to an optimal algorithm. In the case of a single access point, our solution is also asymptotically optimal with respect to density.
Cite as

Philip Dasler and David M. Mount. Online Algorithms for Warehouse Management. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 56:1-56:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dasler_et_al:LIPIcs.ISAAC.2019.56,
  author =	{Dasler, Philip and Mount, David M.},
  title =	{{Online Algorithms for Warehouse Management}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{56:1--56:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.56},
  URN =		{urn:nbn:de:0030-drops-115526},
  doi =		{10.4230/LIPIcs.ISAAC.2019.56},
  annote =	{Keywords: Warehouse management, online algorithms, competitive analysis, robotics}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.1
2048 Without New Tiles Is Still Hard

Authors: Ahmed Abdelkader, Aditya Acharya, and Philip Dasler

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
We study the computational complexity of a variant of the popular 2048 game in which no new tiles are generated after each move. As usual, instances are defined on rectangular boards of arbitrary size. We consider the natural decision problems of achieving a given constant tile value, score or number of moves. We also consider approximating the maximum achievable value for these three objectives. We prove all these problems are NP-hard by a reduction from 3SAT. Furthermore, we consider potential extensions of these results to a similar variant of the Threes! game. To this end, we report on a peculiar motion pattern, that is not possible in 2048, which we found much harder to control by similar board designs.
Cite as

Ahmed Abdelkader, Aditya Acharya, and Philip Dasler. 2048 Without New Tiles Is Still Hard. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{abdelkader_et_al:LIPIcs.FUN.2016.1,
  author =	{Abdelkader, Ahmed and Acharya, Aditya and Dasler, Philip},
  title =	{{2048 Without New Tiles Is Still Hard}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.1},
  URN =		{urn:nbn:de:0030-drops-58858},
  doi =		{10.4230/LIPIcs.FUN.2016.1},
  annote =	{Keywords: Complexity of Games, 2048}
}
  • Refine by Author
  • 2 Dasler, Philip
  • 1 Abdelkader, Ahmed
  • 1 Acharya, Aditya
  • 1 Mount, David M.

  • Refine by Classification
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 2048
  • 1 Complexity of Games
  • 1 Warehouse management
  • 1 competitive analysis
  • 1 online algorithms
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2019

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 Imprint Privacy Contact