Weighted Depth: Difference between revisions

From Algorithm Wiki
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
Line 10: Line 10:
== Parameters ==  
== Parameters ==  


<pre>n: number of boxes
n: number of boxes
d: dimensionality of space</pre>
 
d: dimensionality of space


== Table of Algorithms ==  
== Table of Algorithms ==  

Revision as of 12:04, 15 February 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

https://arxiv.org/pdf/1602.05837.pdf