MINIMUM RING LOADING

• INSTANCE: Positive integer n and a sequence $\{d_{i,j}\}_{0\le i<j<n}$ of non-negative integers denoting the pairwise demand between nodes i and j of a ring of size n.

• SOLUTION: A map $\Phi:\{(i,j): 1\le i<j\le n\}\rightarrow\{0,1\}$.

• MEASURE: $\max_{0\le k<n} c_k$, where
  
  $$c_k=\sum_{0\le i<j<n}\{d_{i,j}:\Phi(i,j)=1\wedge(i\le k<j)\}+ \sum_{0\le i<j<n}\{d_{i,j}:\Phi(i,j)=0\wedge(k<i\vee k\ge j)\}.$$
  
  

  
  

• Good News: Admits a PTAS [302].