dc.creator | Caraballo de la Cruz, Luis Evaristo | es |
dc.creator | Pérez Lantero, Pablo | es |
dc.creator | Seara, Carlos | es |
dc.creator | Ventura Molina, Inmaculada | es |
dc.date.accessioned | 2022-02-21T18:59:21Z | |
dc.date.available | 2022-02-21T18:59:21Z | |
dc.date.issued | 2021-10 | |
dc.identifier.citation | 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. | |
dc.identifier.issn | 0178-4617 | es |
dc.identifier.uri | https://hdl.handle.net/11441/130127 | |
dc.description.abstract | 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. | es |
dc.description.sponsorship | Unión Europea 734922 | es |
dc.description.sponsorship | Agencia Estatal de Investigación MTM2016-76272-R | es |
dc.description.sponsorship | Ministerio de Ciencia e Innovación PID2019-104129GB-I00 | es |
dc.description.sponsorship | Generalitat de Catalunya 2017SGR1640 | es |
dc.format | application/pdf | es |
dc.format.extent | 25 p. | es |
dc.language.iso | eng | es |
dc.publisher | Springer | es |
dc.relation.ispartof | Algorithmica, 83, 3741-3765. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Random weighted points | es |
dc.subject | Boxes | es |
dc.subject | Red and blue points | es |
dc.subject | #P-hardness | es |
dc.title | Maximum Box Problem on Stochastic Points | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada II | es |
dc.relation.projectID | 734922 | es |
dc.relation.projectID | MTM2016-76272-R | es |
dc.relation.projectID | FPU14/04705 | es |
dc.relation.projectID | PID2019-104129GB-I00 | es |
dc.relation.projectID | 2017SGR1640 | es |
dc.relation.publisherversion | https://link.springer.com/article/10.1007/s00453-021-00882-z | es |
dc.identifier.doi | 10.1007/s00453-021-00882-z | es |
dc.contributor.group | Universidad de Sevilla. FQM241: Grupo de Investigación en Localización | es |
dc.journaltitle | Algorithmica | es |
dc.publication.volumen | 83 | es |
dc.publication.initialPage | 3741 | es |
dc.publication.endPage | 3765 | es |