An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs

Given a vertex-weighted undirected connected graph $$G = (V, E, \ell , \rho )$$ G = ( V , E , ℓ , ρ ) , where each edge $$e \in E$$ e ∈ E has a length $$\ell (e) > 0$$ ℓ ( e ) > 0 and each vertex $$v \in V$$ v ∈ V has a weight $$\rho (v) > 0$$ ρ ( v ) > 0 , a subset $$T \subseteq V$$ T ⊆ V of vertices and a set S containing all the points on edges in a subset $$E' \subseteq E$$ E ′ ⊆ E of edges, the generalized absolute 1-center problem (GA1CP), an extension of the classic vertex-weighted absolute 1-center problem (A1CP), asks to find a point from S such that the longest weighted shortest path distance in G from it to T is minimized. This paper presents a simple FPTAS for GA1CP by traversing the edges in $$E'$$ E ′ using a positive real number as step size. The FPTAS takes $$O( |E| |V| + |V|^2 \log \log |V| + \frac{1}{\epsilon } |E'| |T| {\mathcal {R}})$$ O ( | E | | V | + | V | 2 log log | V | + 1 ϵ | E ′ | | T | R ) time, where $${\mathcal {R}}$$ R is an input parameter size of the problem instance, for any given $$\epsilon > 0$$ ϵ > 0 . For instances with a small input parameter size $${\mathcal {R}}$$ R , applying the FPTAS with $$\epsilon = \Theta (1)$$ ϵ = Θ ( 1 ) to the classic vertex-weighted A1CP can produce a $$(1 + \Theta (1))$$ ( 1 + Θ ( 1 ) ) -approximation in at most O(|E| |V|) time when the distance matrix is known and $$O(|E| |V| + |V|^2 \log \log |V|)$$ O ( | E | | V | + | V | 2 log log | V | ) time when the distance matrix is unknown, which are smaller than Kariv and Hakimi’s $$O(|E| |V| \log |V|)$$ O ( | E | | V | log | V | ) -time algorithm and $$O(|E| |V| \log |V| + |V|^3)$$ O ( | E | | V | log | V | + | V | 3 ) -time algorithm, respectively.