Constant-Factor Greedy Algorithms for the Asymmetric p-Center Problem in Parameterized Complete Digraphs

摘要

This paper studies the asymmetric p-center problem (ApCP) and the vertex-weighted asymmetric p-center problem (WApCP) in complete digraphs (CD) satisfying the triangle inequality. First, we propose two classes of parameterized complete digraphs, α-CD and (α, β)-CD from the angle of the parameterized upper bound on the ratio of two asymmetric edge-weights between two different vertices and on the ratio of two vertex-weights, respectively. Using the greedy method, we design a (1 + α)-approximation algorithm for the ApCP in α-CD's and a (1 + αβ)-approximation algorithm for the WApCP in (α,β)-CD's, respectively.