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

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

来源：Journal of Combinatorial Optimization, 2017, 34(4): 1084-1095.

DOI：10.1007/s10878-017-0130-4

• Vertex-weighted graph
• Generalized absolute 1-center
• FPTAS

Given a vertex-weighted undirected connected graph G = (V, E, l, p), where each edge e is an element of E has a length l (e) > 0 and each vertex v is an element of V has a weight.(v) > 0, a subset T subset of V of vertices and a set S containing all the points on edges in a subset E ' subset of 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 ' using a positive real number as step size. The FPTAS takes O(|E||V| + |V| (2) log log | V|+1/epsilon | E ' || T | R) time, whereRis an input parameter size of the problem instance, for any given epsilon > 0. For instances with a small input parameter size R, applying the FPTAS with is an element of = Theta (1) to the classic vertex-weighted A1CP can produce a (1 + Theta(1))-approximation in at most O(|E||V|) time when the distance matrix is known and 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|)-time algorithm and O(|E||V| log |V| + |V|(3))-time algorithm, respectively.

• 出版日期2017-11
• 单位浙江大学