A Fully Polynomial Time Approximation Scheme for the Smallest Diameter of Imprecise Points Abstract   Given a set    D        d    1    ,  xe2x80xa6  ,    d    n        of imprecise points modeled as disks, the minimum diameter problem is to locate a set    P        p    1    ,  xe2x80xa6  ,    p    n        of fixed points, where      p    i    xe2x88x88    d    i     , such that the furthest distance between any pair of points in P is as small as possible. This introduces a tight lower bound on the size of the diameter of any instance P. In this paper, we present a fully polynomial time approximation scheme (FPTAS) for computing the minimum diameter of a set of disjoint disks that runs in    O  (    n    2      xcfxb5    xe2x88x92  1    )    time. Then we relax the disjointness assumption and provide a    O  (    n    2      xcfxb5    xe2x88x92  2    )    randomize algorithm. We also show that our results can be generalized in      R    d      when the dimension  d  is an arbitrary fixed constant.

Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems Some of the most fundamental and wellstudied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a center node can reach all other nodes). The natural and important STvariant considers two subsets S and T of the vertex set and lets the STdiameter be the maximum distance between a node in S and a node in T, and the STradius be the minimum distance for a node of S to reach all nodes of T. The bichromatic variant is the special case in which S and T partition the vertex set.  :99,this paper we present a comprehensive study of the approximability of ST and Bichromatic Diameter, Radius, and Eccentricities, and variants, in graphs with and without directions and weights. We give the first nontrivial approximation algorithms for most of these problems, including timeaccuracy tradeoff upper and lower bounds. We show that nearly all of our obtained bounds are tight under the Strong Exponential Time Hypothesis (SETH), or the related Hitting Set Hypothesis.  :171,instance, for Bichromatic Diameter in undirected weighted graphs with m edges, we present an tildeO(m32) time 53approximation algorithm, and show that under SETH, neither the running time, nor the approximation factor can be significantly improved while keeping the other unchanged.