English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Maximum Volume Subset Selection for Anchored Boxes

Bringmann, K., Cabello, S., & Emmerich, M. T. M. (2018). Maximum Volume Subset Selection for Anchored Boxes. doi:Bringmann_arXiv1803.00849.

Item is

Files

show Files
hide Files
:
arXiv:1803.00849.pdf (Preprint), 643KB
Name:
arXiv:1803.00849.pdf
Description:
File downloaded from arXiv at 2018-05-03 09:05 Presented at SoCG'17. Full Version. 24 pages
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Bringmann, Karl1, Author           
Cabello, Sergio2, Author
Emmerich, Michael T. M.2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS
 Abstract: Let $B$ be a set of $n$ axis-parallel boxes in $\mathbb{R}^d$ such that each box has a corner at the origin and the other corner in the positive quadrant of $\mathbb{R}^d$, 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. This 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 running time in any dimension $d \ge 3$ is $\Omega\big(\binom{n}{k}\big)$. We show that: - The problem is NP-hard already in 3 dimensions. - In 3 dimensions, we break the bound $\Omega\big(\binom{n}{k}\big)$, by providing an $n^{O(\sqrt{k})}$ algorithm. - For any constant dimension $d$, we present an efficient polynomial-time approximation scheme.

Details

show
hide
Language(s): eng - English
 Dates: 2018-03-022018
 Publication Status: Published online
 Pages: 25 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show