Approximation algorithms for the ring loading problem with penalty cost

The ring loading problem and its variants have been extensively studied in the last fifteen years, under the assumption that all requests have to be satisfied. However, in many practical cases, one may wish to reject some requests, which results in a penalty cost. We introduce the ring loading problem with penalty cost, which generalizes the well-known ring loading problem (Schrijver et al., 1999 [14]). We prove that this problem is NP-hard even if the demand can be split, and design a 1.58-approximation algorithm for the integer demand splittable case and a (1.58+ϵ)-approximation algorithm for the demand unsplittable case, for any given number ϵ>0.