2 Search Results for "Markarian, Christine"

Document
DOI: 10.4230/LIPIcs.STACS.2021.14
A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location

Authors: Marcin Bienkowski, Björn Feldkord, and Paweł Schmidt

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
In the online non-metric variant of the facility location problem, there is a given graph consisting of a set F of facilities (each with a certain opening cost), a set C of potential clients, and weighted connections between them. The online part of the input is a sequence of clients from C, and in response to any requested client, an online algorithm may open an additional subset of facilities and must connect the given client to an open facility. We give an online, polynomial-time deterministic algorithm for this problem, with a competitive ratio of O(log |F| ⋅ (log |C| + log log |F|)). The result is optimal up to loglog factors. Our algorithm improves over the O((log |C| + log |F|) ⋅ (log |C| + log log |F|))-competitive construction that first reduces the facility location instance to a set cover one and then later solves such instance using the deterministic algorithm by Alon et al. [TALG 2006]. This is an asymptotic improvement in a typical scenario where |F| ≪ |C|. We achieve this by a more direct approach: we design an algorithm for a fractional relaxation of the non-metric facility location problem with clustered facilities. To handle the constraints of such non-covering LP, we combine the dual fitting and multiplicative weight updates approach. By maintaining certain additional monotonicity properties of the created fractional solution, we can handle the dependencies between facilities and connections in a rounding routine. Our result, combined with the algorithm by Naor et al. [FOCS 2011] yields the first deterministic algorithm for the online node-weighted Steiner tree problem. The resulting competitive ratio is O(log k ⋅ log² 𝓁) on graphs of 𝓁 nodes and k terminals.
Cite as

Marcin Bienkowski, Björn Feldkord, and Paweł Schmidt. A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.STACS.2021.14,
  author =	{Bienkowski, Marcin and Feldkord, Bj\"{o}rn and Schmidt, Pawe{\l}},
  title =	{{A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.14},
  URN =		{urn:nbn:de:0030-drops-136598},
  doi =		{10.4230/LIPIcs.STACS.2021.14},
  annote =	{Keywords: Online algorithms, deterministic rounding, linear programming, facility location, set cover}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.22
Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets

Authors: Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, and Mostafa Wahby

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
The modern warehouse is partially automated by robots. Instead of letting human workers walk into shelfs and pick up the required stock, big groups of autonomous mobile robots transport the inventory to the workers. Typically, these robots have an electric drive and need to recharge frequently during the day. When we scale this approach up, it is essential to place recharging stations strategically and as soon as needed so that all robots can survive. In this work, we represent a warehouse topology by a graph and address this challenge with the Online Connected Dominating Set problem (OCDS), an online variant of the classical Connected Dominating Set problem [Guha and Khuller, 1998]. We are given an undirected connected graph G = (V, E) and a sequence of subsets of V arriving over time. The goal is to grow a connected subgraph that dominates all arriving nodes and contains as few nodes as possible. We propose an O(log^2 n)-competitive randomized algorithm for OCDS in general graphs, where n is the number of nodes in the input graph. This is the best one can achieve due to Korman's randomized lower bound of Omega(log n log m) [Korman, 2005] for the related Online Set Cover problem [Alon et al., 2003], where n is the number of elements and m is the number of subsets. We also run extensive simulations to show that our algorithm performs well in a simulated warehouse, where the topology of a warehouse is modeled as a randomly generated geometric graph.
Cite as

Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, and Mostafa Wahby. Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hamann_et_al:LIPIcs.FUN.2018.22,
  author =	{Hamann, Heiko and Markarian, Christine and Meyer auf der Heide, Friedhelm and Wahby, Mostafa},
  title =	{{Pick, Pack, \& Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.22},
  URN =		{urn:nbn:de:0030-drops-88136},
  doi =		{10.4230/LIPIcs.FUN.2018.22},
  annote =	{Keywords: connected dominating set, online algorithm, competitive analysis, geometric graph, robot warehouse, recharging stations}
}
  • Refine by Author
  • 1 Bienkowski, Marcin
  • 1 Feldkord, Björn
  • 1 Hamann, Heiko
  • 1 Markarian, Christine
  • 1 Meyer auf der Heide, Friedhelm
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Online algorithms
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 1 Online algorithms
  • 1 competitive analysis
  • 1 connected dominating set
  • 1 deterministic rounding
  • 1 facility location
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2021

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