Geometric knapsack problems

Esther M. Arkin*, Samir Khuller, Joseph S.B. Mitchell

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 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 at most M connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. We also provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.

Original languageEnglish (US)
Pages (from-to)399-427
Number of pages29
JournalAlgorithmica
Volume10
Issue number5
DOIs
StatePublished - Nov 1 1993

Keywords

  • Computational geometry
  • Convexity
  • Dynamic programming
  • Knapsack problems

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Geometric knapsack problems'. Together they form a unique fingerprint.

Cite this