Approximating the restricted 1-center in graphs

作者：Ding, Wei^*; Qiu, Ke

来源：Theoretical Computer Science, 2019, 774: 31-43.

DOI：10.1016/j.tcs.2016.04.044

• Restricted 1-center
• Restricted shortest path
• Saddle point
• FPTAS

This paper studies the restricted vertex 1-center problem (RV1CP) and restricted absolute 1-center problem (RA1CP) in general undirected graphs with each edge having two weights, cost and delay. First, we devise a simple FPTAS for RV1CP with O (mn(3)(1/epsilon + loglogn)) running time, based on FPTAS proposed by Lorenz and Raz (1999) [11] for computing end-to--end restricted shortest path (RSP). During the computation of the FPTAS for RV1CP, we derive a RSP distance matrix. Next, we discuss RA1CP in such graphs where the delay is a separable (e.g., linear) function of the cost on edge. We investigate an important property that the FPTAS for RV1CP can find a (1+epsilon)-approximation of RA1CP when the RSP distance matrix has a saddle point. In addition, we show that it is harder to find an approximation of RA1CP when the matrix has no saddle point. This paper develops a scaling algorithm with at most O (mn(3) K(log/eta + loglogn)) running time where K is a step-size parameter and eta is a given positive number, to find a (1 + eta)-approximation of RA1CP.

• 出版日期2019-6-25
• 单位浙江大学