Resource-constrained geometric network optimization
Esther M. Arkin, Joseph S. B. Mitchell, Giri Narasimhan · 1998
WC study a variety of geometric network optimization prob lcms on a set of points, in which we are given a resource bound, a, on the total length of the network, and our ob jcctivc is to maximize the number of points visited (or the total "value" of points visited), In particular, we resolve the well-publicized open problem on the approximabiity of the rooted "orienteering problem" for the case in which the sites are given as points in the plane and the network required is a cycle.We obtain a 2approximation for this problem, We also obtain approximation algorithms for variants of this problem in which the network required is a tree (S-approximation) or a path Q-approximation).No prior approximation bounds were known for any of these problems,We also obtain improved approximation algorithms for geometric instances of the unrooted orienteering problem, where we obtain a 2-approximation for both the cycle and tree versions of the problem on points in the plane, as well as a G-approximation for the tree version in edge-weighted graphs, E'urther, we study generalizations of the basic orienteering problem, to the case of multiple roots, sites that are polygonnl regions, etc., where we again give the first known approximation results.Our methods are based on some new tools which may be of interest in their own right: ( 1) some new results on m-'Department of Applied Mathematics and Statistics, State Univcrsitv of New York.Stonv Brook.NY 11794-3600: aat~o6smb .ounyob.