Resource-constrained geometric network optimization Conference

Arkin, EM, Mitchell, JSB, Narasimhan, G. (1998). Resource-constrained geometric network optimization . 307-316. 10.1145/276884.276919

cited authors

  • Arkin, EM; Mitchell, JSB; Narasimhan, G

abstract

  • A variety of geometric network optimization problems on a set of points is presented, in which a resource bound on the total length of the network and how to maximize the number of points visited are discussed. The open problem on the approximability of the rooted `orienteering problem' is solved for the case in which the sites are given as points in the plane and the network required is a cycle. Approximation algorithms for variants of this problem in which the network required is a tree (3-approximation) or a path (2-approximation) are obtained.

publication date

  • January 1, 1998

Digital Object Identifier (DOI)

start page

  • 307

end page

  • 316