Resource-constrained geometric network optimization

Esther M. Arkin; Joseph S.B. Mitchell; Giri Narasimhan

doi:10.1145/276884.276919

Resource-constrained geometric network optimization

Applied Mathematics and Statistics

Stony Brook University

Research output: Contribution to conference › Paper › peer-review

71 Scopus citations

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.

Original language	English
Pages	307-316
Number of pages	10
DOIs	https://doi.org/10.1145/276884.276919
State	Published - 1998
Event	Proceedings of the 1998 14th Annual Symposium on Computational Geometry - Minneapolis, MN, USA Duration: Jun 7 1998 → Jun 10 1998

Conference

Conference	Proceedings of the 1998 14th Annual Symposium on Computational Geometry
City	Minneapolis, MN, USA
Period	06/7/98 → 06/10/98

Access to Document

10.1145/276884.276919

Cite this

@conference{70efc7e559dd4478a2203d14bbc84147,

title = "Resource-constrained geometric network optimization",

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.",

author = "Arkin, \{Esther M.\} and Mitchell, \{Joseph S.B.\} and Giri Narasimhan",

year = "1998",

doi = "10.1145/276884.276919",

language = "English",

pages = "307--316",

note = "Proceedings of the 1998 14th Annual Symposium on Computational Geometry ; Conference date: 07-06-1998 Through 10-06-1998",

}

TY - CONF

T1 - Resource-constrained geometric network optimization

AU - Arkin, Esther M.

AU - Mitchell, Joseph S.B.

AU - Narasimhan, Giri

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0031643999

U2 - 10.1145/276884.276919

DO - 10.1145/276884.276919

M3 - Paper

AN - SCOPUS:0031643999

SP - 307

EP - 316

T2 - Proceedings of the 1998 14th Annual Symposium on Computational Geometry

Y2 - 7 June 1998 through 10 June 1998

ER -

Resource-constrained geometric network optimization

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this