DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2017.22

Maximum Volume Subset Selection for Anchored Boxes

Authors: Karl Bringmann, Sergio Cabello, and Michael T. M. Emmerich

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract

Let B be a set of n axis-parallel boxes in d-dimensions such that each box has a corner at the origin and the other corner in the positive quadrant, and let k be a positive integer. We study the problem of selecting k boxes in B that maximize the volume of the union of the selected boxes. The research is motivated by applications in skyline queries for databases and in multicriteria optimization, where the problem is known as the hypervolume subset selection problem. It is known that the problem can be solved in polynomial time in the plane, while the best known algorithms in any dimension d>2 enumerate all size-k subsets. We show that: * The problem is NP-hard already in 3 dimensions. * In 3 dimensions, we break the enumeration of all size-k subsets, by providing an n^O(sqrt(k)) algorithm. * For any constant dimension d, we give an efficient polynomial-time approximation scheme.

Cite as

Karl Bringmann, Sergio Cabello, and Michael T. M. Emmerich. Maximum Volume Subset Selection for Anchored Boxes. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.SoCG.2017.22,
  author =	{Bringmann, Karl and Cabello, Sergio and Emmerich, Michael T. M.},
  title =	{{Maximum Volume Subset Selection for Anchored Boxes}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.22},
  URN =		{urn:nbn:de:0030-drops-72011},
  doi =		{10.4230/LIPIcs.SoCG.2017.22},
  annote =	{Keywords: geometric optimization, subset selection, hypervolume indicator, Klee’s 23 measure problem, boxes, NP-hardness, PTAS}
}

Search Results

Documents authored by Emmerich, Michael T. M.

Maximum Volume Subset Selection for Anchored Boxes

Abstract

Cite as

Thanks for your feedback!

Could not send message