Artículo
Maximum Box Problem on Stochastic Points
Autor/es | Caraballo de la Cruz, Luis Evaristo
Pérez Lantero, Pablo Seara, Carlos Ventura Molina, Inmaculada |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Fecha de publicación | 2021-10 |
Fecha de depósito | 2022-02-21 |
Publicado en |
|
Resumen | 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 ... 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 #P-hard, 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. |
Identificador del proyecto | 734922
MTM2016-76272-R FPU14/04705 PID2019-104129GB-I00 2017SGR1640 |
Cita | Caraballo de la Cruz, L.E., Pérez-Lantero, P., Seara, C. y Ventura Molina, I. (2021). Maximum Box Problem on Stochastic Points. Algorithmica, 83, 3741-3765. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
A_2021_Ventura_Maximum box.pdf | 533.5Kb | [PDF] | Ver/ | |