The Online Multi-Commodity Facility Location Problem

摘要: We consider a natural extension to the metric uncapacitated Facility Location Problem (FLP) in which requests ask for different commodities out of finite set $S$ commodities. Ravi and Sinha (SODA'04) introduced model as Multi-Commodity (MFLP) considered it an offline optimization problem. The itself is similar FLP: i.e., are located at points space task algorithm construct facilities assign while minimizing construction cost sum over all assignment distances. In addition, heterogeneous; they request or offer multiple $S$. A has be connected jointly offering demanded by it. comparison FLP, decide not only if where place facilities, but also each. To best our knowledge we first study problem its online variant requests, their positions known beforehand revealed time. present results regarding competitive ratio. On one hand, show that heterogeneity influences ratio developing lower bound on any randomized $\Omega(\sqrt{|S|}+\frac{\log n}{\log\log n})$ already holds simple line metrics. Here, $n$ number requests. other side, establish deterministic $O(\sqrt{|S|}\cdot\log n)$-competitive $O(\sqrt{|S|}\cdot\frac{\log n})$-competitive algorithm. Further, when considering more special class functions facility, decreases given depending function.