Weighted Depth: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Weighted Depth (Geometric Covering Problems)}} == Description == Given a set of $n$ weighted axis-parallel boxes in $d$-dimensional space $\mathbb{R}^d$, find a point $p \in \mathbb{R}^d$ that maximizes the sum of the weights of the boxes containing $p$. == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Hole in Union, Triangle Measure, Point Covering, Max-Weight Rectangle == Parameters == <pre>n: nu...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
$n$: number of boxes | |||
d: dimensionality of space | |||
$d$: dimensionality of space | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 08:27, 10 April 2023
Description
Given a set of $n$ weighted axis-parallel boxes in $d$-dimensional space $\mathbb{R}^d$, find a point $p \in \mathbb{R}^d$ that maximizes the sum of the weights of the boxes containing $p$.
Related Problems
Related: Strips Cover Box, Triangles Cover Triangle, Hole in Union, Triangle Measure, Point Covering, Max-Weight Rectangle
Parameters
$n$: number of boxes
$d$: dimensionality of space
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Max-Weight K-Clique | if: to-time: $O(n^{\lfloor d/{2}\rfloor-\epsilon})$ for $N$ weighted axis-parallel boxes in $\mathbb{R}^d$ then: from-time: $O(n^{k-{2}\epsilon})$ on $n$ vertex graphs for $k=d$ |
2016 | https://arxiv.org/pdf/1602.05837.pdf | link |
References/Citation
https://doi-org.ezproxy.canberra.edu.au/10.1109/FOCS.2013.51