Geometric knapsack problems

Esther M. Arkin; Sarnir Khufler; Joseph S.B. Mitchell

doi:10.1007/BFb0028259

Geometric knapsack problems

Applied Mathematics and Statistics

University of Maryland, College Park

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following "fence enclosure" problem: Given a set S of n points in the plane with values vi ≥ 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the "value" of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowing S to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of up to K connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. Additionally we provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.

Original language	English
Title of host publication	Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Nicola Santoro
Publisher	Springer Verlag
Pages	165-176
Number of pages	12
ISBN (Print)	9783540475668
DOIs	https://doi.org/10.1007/BFb0028259
State	Published - 1991
Event	2nd Workshop on Algorithms and Data Structures, WADS 1991 - Ottawa, Canada Duration: Aug 14 1991 → Aug 16 1991

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	519 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd Workshop on Algorithms and Data Structures, WADS 1991
Country/Territory	Canada
City	Ottawa
Period	08/14/91 → 08/16/91

Access to Document

10.1007/BFb0028259

Cite this

Arkin, E. M., Khufler, S., & Mitchell, J. S. B. (1991). Geometric knapsack problems. In F. Dehne, J.-R. Sack, & N. Santoro (Eds.), Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings (pp. 165-176). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 519 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0028259

Arkin, Esther M. ; Khufler, Sarnir ; Mitchell, Joseph S.B. / Geometric knapsack problems. Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Nicola Santoro. Springer Verlag, 1991. pp. 165-176 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e1f87338f015427abd4bdea5577af406,

title = "Geometric knapsack problems",

abstract = "We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following {"}fence enclosure{"} problem: Given a set S of n points in the plane with values vi ≥ 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the {"}value{"} of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowing S to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of up to K connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. Additionally we provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.",

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

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; 2nd Workshop on Algorithms and Data Structures, WADS 1991 ; Conference date: 14-08-1991 Through 16-08-1991",

year = "1991",

doi = "10.1007/BFb0028259",

language = "English",

isbn = "9783540475668",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "165--176",

editor = "Frank Dehne and Jorg-Rudiger Sack and Nicola Santoro",

booktitle = "Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings",

}

Arkin, EM, Khufler, S & Mitchell, JSB 1991, Geometric knapsack problems. in F Dehne, J-R Sack & N Santoro (eds), Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 519 LNCS, Springer Verlag, pp. 165-176, 2nd Workshop on Algorithms and Data Structures, WADS 1991, Ottawa, Canada, 08/14/91. https://doi.org/10.1007/BFb0028259

Geometric knapsack problems. / Arkin, Esther M.; Khufler, Sarnir; Mitchell, Joseph S.B.
Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Nicola Santoro. Springer Verlag, 1991. p. 165-176 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 519 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Geometric knapsack problems

AU - Arkin, Esther M.

AU - Khufler, Sarnir

AU - Mitchell, Joseph S.B.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1991.

PY - 1991

Y1 - 1991

N2 - We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following "fence enclosure" problem: Given a set S of n points in the plane with values vi ≥ 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the "value" of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowing S to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of up to K connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. Additionally we provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.

AB - We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following "fence enclosure" problem: Given a set S of n points in the plane with values vi ≥ 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the "value" of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowing S to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of up to K connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. Additionally we provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.

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

U2 - 10.1007/BFb0028259

DO - 10.1007/BFb0028259

M3 - Conference contribution

AN - SCOPUS:85032019554

SN - 9783540475668

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 165

EP - 176

BT - Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Santoro, Nicola

PB - Springer Verlag

T2 - 2nd Workshop on Algorithms and Data Structures, WADS 1991

Y2 - 14 August 1991 through 16 August 1991

ER -

Arkin EM, Khufler S, Mitchell JSB. Geometric knapsack problems. In Dehne F, Sack JR, Santoro N, editors, Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. Springer Verlag. 1991. p. 165-176. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0028259

Geometric knapsack problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this