An approximation algorithm for k-level squared metric facility location problem with outliers

We investigate k-level squared metric facility location problem with outli-ers (k-SMFLPWO) for any constant k. In k-SMFLPWO, given k facilities set F-l , where l is an element of {1,2,& ctdot;,k} , clients set C with cardinality n and a non-negative integer q<n . The sum of opening and connection cost will be substantially increased by distant clients. To minimize the total cost, some distant clients can not be con-nected, in short, at least n-q clients in clients set C are connected to the path p=(i(1 )is an element of F-1, i(2) is an element of F-2, & ctdot;, i(k) is an element of F-k) where the facilities in path p are opened. Based on primal-dual approximation algorithm and the property of squared metric triangle inequality, we present a constant factor approximation algorithm for k-SMFLPWO.