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

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

MINIMUM K-SUPPLIER

• INSTANCE: Complete graph $G=\left(V,E\right)$, distances $d(v_i,v_j)\in N$ satisfying the triangle inequality, center construction cost $c(v)\in N$ and usage weight w(v) for each $v\in V$, cost bound $L\in N$.

• SOLUTION: A supplier set of legal cost, i.e., a subset $S\subseteq V$ such that $\sum_{v\in S} c(v)\le L$.

• MEASURE: The maximum weighted distance from a vertex to its nearest supplier, i.e.,
  
  $$\max\limits_{v\in V} \min\limits_{s\in S} w(v)d(v,s).$$
  
  

  
  

• Good News: Approximable within 3 [463].

• Bad News: Not approximable within 3$-\varepsilon$ for any $\varepsilon >0$ [254].