---
res:
  bibo_abstract:
  - " 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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Jannik
      foaf_name: Castenow, Jannik
      foaf_surname: Castenow
      foaf_workInfoHomepage: http://www.librecat.org/personId=38705
  - foaf_Person:
      foaf_givenName: Björn
      foaf_name: Feldkord, Björn
      foaf_surname: Feldkord
      foaf_workInfoHomepage: http://www.librecat.org/personId=22704
  - foaf_Person:
      foaf_givenName: Till
      foaf_name: Knollmann, Till
      foaf_surname: Knollmann
      foaf_workInfoHomepage: http://www.librecat.org/personId=39241
    orcid: 0000-0003-2014-4696
  - foaf_Person:
      foaf_givenName: Manuel
      foaf_name: Malatyali, Manuel
      foaf_surname: Malatyali
  - foaf_Person:
      foaf_givenName: Friedhelm
      foaf_name: Meyer auf der Heide, Friedhelm
      foaf_surname: Meyer auf der Heide
      foaf_workInfoHomepage: http://www.librecat.org/personId=15523
  bibo_doi: 10.1145/3350755.3400281
  dct_date: 2020^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/9781450369350
  dct_language: eng
  dct_subject:
  - Online Multi-Commodity Facility Location
  - Competitive Ratio
  - Online Optimization
  - Facility Location Problem
  dct_title: The Online Multi-Commodity Facility Location Problem@
...