| dc.creator | Pérez-Lantero, Pablo | |
| dc.date | 2022-05-20T20:45:20Z | |
| dc.date | 2022-06-18T20:37:48Z | |
| dc.date | 2022-05-20T20:45:20Z | |
| dc.date | 2022-06-18T20:37:48Z | |
| dc.date | November4 | |
| dc.date | 2017 | |
| dc.date | 2017 | |
| dc.date | November2 | |
| dc.date.accessioned | 2023-08-23T00:14:44Z | |
| dc.date.available | 2023-08-23T00:14:44Z | |
| dc.identifier | 1160543 | |
| dc.identifier | https://hdl.handle.net/10533/253921 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/8354370 | |
| dc.description | Given a finite set of weighted points in Rd (where there can be negative weights), the
maximum box problem asks for an axis-aligned rectangle (i.e., box) such that the sum
of the weights of the points that it contains is maximized. We consider that each point
of the input has a probability of being present in the final random point set, and these
events are mutually independent; then, the total weight of a maximum box is a random
variable. We aim to compute both the probability that this variable is at least a given
parameter, and its expectation. We show that even in d = 1 these computations are
#P-hard, and give pseudo polynomial-time algorithms in the case where the weights
are integers in a bounded interval. For d = 2, we consider that each point is colored
red or blue, where red points have weight +1 and blue points weight −∞. The random
variable is the maximum number of red points that can be covered with a box not
containing any blue point. We prove that the above two computations are also #Phard,
and give a polynomial-time algorithm for computing the probability that there is
a box containing exactly two red points, no blue point, and a given point of the plane.
This is a joint work with L. E. Caraballo, C. Seara, and I. Ventura. | |
| dc.description | FONDECYT | |
| dc.description | FONDECYT | |
| dc.language | eng | |
| dc.relation | instname: ANID | |
| dc.relation | reponame: Repositorio Digital RI2.0 | |
| dc.relation | Encuentro Anual de la Sociedad de Matemática de Chile | |
| dc.relation | 86° | |
| dc.rights | http://creativecommons.org/licenses/by/3.0/cl/ | |
| dc.title | Maximum Box Problem on Stochastic Points | |
| dc.type | info:eu-repo/semantics/lecture | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
| dc.coverage | Talca | |
