---
_id: '17370'
abstract:
- lang: eng
  text: " We consider a natural extension to the metric uncapacitated Facility Location
    Problem (FLP) in which requests ask for different commodities out of a finite
    set \\( S \\) of commodities.\r\n  Ravi and Sinha (SODA 2004) introduced the model
    as the \\emph{Multi-Commodity Facility Location Problem} (MFLP) and considered
    it an offline optimization problem.\r\n  The model itself is similar to the FLP:
    i.e., requests are located at points of a finite metric space and the task of
    an algorithm is to construct facilities and assign requests to facilities while
    minimizing the construction cost and the sum over all assignment distances.\r\n
    \ In addition, requests and facilities are heterogeneous; they request or offer
    multiple commodities out of $S$.\r\n  A request has to be connected to a set of
    facilities jointly offering the commodities demanded by it.\r\n  In comparison
    to the FLP, an algorithm has to decide not only if and where to place facilities,
    but also which commodities to offer at each.\r\n\r\n  To the best of our knowledge
    we are the first to study the problem in its online variant in which requests,
    their positions and their commodities are not known beforehand but revealed over
    time.\r\n  We present results regarding the competitive ratio.\r\n  On the one
    hand, we show that heterogeneity influences the competitive ratio by developing
    a lower bound on the competitive ratio for any randomized online algorithm of
    \\( \\Omega (  \\sqrt{|S|} + \\frac{\\log n}{\\log \\log n}  ) \\) that already
    holds for simple line metrics.\r\n  Here, \\( n \\) is the number of requests.\r\n
    \ On the other side, we establish a deterministic \\( \\mathcal{O}(\\sqrt{|S|}
    \\cdot \\log n) \\)-competitive algorithm and a randomized \\( \\mathcal{O}(\\sqrt{|S|}
    \\cdot \\frac{\\log n}{\\log \\log n} ) \\)-competitive algorithm.\r\n  Further,
    we show that when considering a more special class of cost functions for the construction
    cost of a facility, the competitive ratio decreases given by our deterministic
    algorithm depending on the function."
author:
- first_name: Jannik
  full_name: Castenow, Jannik
  id: '38705'
  last_name: Castenow
- first_name: Björn
  full_name: Feldkord, Björn
  id: '22704'
  last_name: Feldkord
- first_name: Till
  full_name: Knollmann, Till
  id: '39241'
  last_name: Knollmann
  orcid: 0000-0003-2014-4696
- first_name: Manuel
  full_name: Malatyali, Manuel
  last_name: Malatyali
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: 'Castenow J, Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. The
    Online Multi-Commodity Facility Location Problem. In: <i>Proceedings of the 32nd
    ACM Symposium on Parallelism in Algorithms and Architectures</i>. ; 2020. doi:<a
    href="https://doi.org/10.1145/3350755.3400281">10.1145/3350755.3400281</a>'
  apa: Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., &#38; Meyer auf der
    Heide, F. (2020). The Online Multi-Commodity Facility Location Problem. In <i>Proceedings
    of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures</i>.
    <a href="https://doi.org/10.1145/3350755.3400281">https://doi.org/10.1145/3350755.3400281</a>
  bibtex: '@inproceedings{Castenow_Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2020,
    title={The Online Multi-Commodity Facility Location Problem}, DOI={<a href="https://doi.org/10.1145/3350755.3400281">10.1145/3350755.3400281</a>},
    booktitle={Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms
    and Architectures}, author={Castenow, Jannik and Feldkord, Björn and Knollmann,
    Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2020} }'
  chicago: Castenow, Jannik, Björn Feldkord, Till Knollmann, Manuel Malatyali, and
    Friedhelm Meyer auf der Heide. “The Online Multi-Commodity Facility Location Problem.”
    In <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures</i>,
    2020. <a href="https://doi.org/10.1145/3350755.3400281">https://doi.org/10.1145/3350755.3400281</a>.
  ieee: J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der
    Heide, “The Online Multi-Commodity Facility Location Problem,” in <i>Proceedings
    of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures</i>,
    2020.
  mla: Castenow, Jannik, et al. “The Online Multi-Commodity Facility Location Problem.”
    <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures</i>,
    2020, doi:<a href="https://doi.org/10.1145/3350755.3400281">10.1145/3350755.3400281</a>.
  short: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide,
    in: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures,
    2020.'
date_created: 2020-07-14T07:53:20Z
date_updated: 2022-01-06T06:53:10Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1145/3350755.3400281
external_id:
  arxiv:
  - '2005.08391'
file:
- access_level: closed
  content_type: application/pdf
  creator: tillk
  date_created: 2020-07-14T07:56:52Z
  date_updated: 2020-07-14T07:56:52Z
  file_id: '17373'
  file_name: 3350755.3400281.pdf
  file_size: 1271416
  relation: main_file
  success: 1
file_date_updated: 2020-07-14T07:56:52Z
has_accepted_license: '1'
keyword:
- Online Multi-Commodity Facility Location
- Competitive Ratio
- Online Optimization
- Facility Location Problem
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and
  Architectures
publication_identifier:
  isbn:
  - '9781450369350'
publication_status: published
status: public
title: The Online Multi-Commodity Facility Location Problem
type: conference
user_id: '39241'
year: '2020'
...