Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM FACILITY LOCATION

• INSTANCE: Complete graph $G=\left(V,E\right)$, costs $c(v_i,v_j)\in N$ that are symmetric and satisfy the triangle inequality, $F\subseteq V$ set of locations where a facility may be built, for each $v\in F$ a nonnegative cost f(v) of building a facility at v, for each location $v\in V$ a nonnegative demand d(v).

• SOLUTION: Locations for the facilities to be built, i.e., $F'\subseteq F$.

• MEASURE:
  
  $$\sum_{v\in F'} f(v)+\sum_{u\in F'}\sum_{v\in V} d(v)\cdot c(u,v).$$
  
  

  
  

• Good News: Approximable within 2.408 [209].

• Bad News: APX-complete [209].

• Comment: Transformation from MINIMUM VERTEX COVER in bounded degree graphs. Not approximable within 1.463 unless NP $\subset\mbox{\sc Dtime}(n^{\log\log n})$. If f(v)=1 for every $v\in F$ the same hardness results are valid, but the problem is approximable within 2.225. If F=V and f(v)=1 then the problem is approximable within 2.104 but not within 1.278 unless NP $\subset\mbox{\sc Dtime}(n^{\log\log n})$ [209]. The generalization to unrestricted cost functions c is approximable within $O(\log \vert V\vert)$ [247].