Show simple item record

Article

dc.creatorCaraballo de la Cruz, Luis Evaristoes
dc.creatorPérez Lantero, Pabloes
dc.creatorSeara, Carloses
dc.creatorVentura Molina, Inmaculadaes
dc.date.accessioned2022-02-21T18:59:21Z
dc.date.available2022-02-21T18:59:21Z
dc.date.issued2021-10
dc.identifier.citationCaraballo 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.issn0178-4617es
dc.identifier.urihttps://hdl.handle.net/11441/130127
dc.description.abstractGiven 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.sponsorshipUnión Europea 734922es
dc.description.sponsorshipAgencia Estatal de Investigación MTM2016-76272-Res
dc.description.sponsorshipMinisterio de Ciencia e Innovación PID2019-104129GB-I00es
dc.description.sponsorshipGeneralitat de Catalunya 2017SGR1640es
dc.formatapplication/pdfes
dc.format.extent25 p.es
dc.language.isoenges
dc.publisherSpringeres
dc.relation.ispartofAlgorithmica, 83, 3741-3765.
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectRandom weighted pointses
dc.subjectBoxeses
dc.subjectRed and blue pointses
dc.subject#P-hardnesses
dc.titleMaximum Box Problem on Stochastic Pointses
dc.typeinfo:eu-repo/semantics/articlees
dc.type.versioninfo:eu-repo/semantics/publishedVersiones
dc.rights.accessrightsinfo:eu-repo/semantics/openAccesses
dc.contributor.affiliationUniversidad de Sevilla. Departamento de Matemática Aplicada IIes
dc.relation.projectID734922es
dc.relation.projectIDMTM2016-76272-Res
dc.relation.projectIDFPU14/04705es
dc.relation.projectIDPID2019-104129GB-I00es
dc.relation.projectID2017SGR1640es
dc.relation.publisherversionhttps://link.springer.com/article/10.1007/s00453-021-00882-zes
dc.identifier.doi10.1007/s00453-021-00882-zes
dc.contributor.groupUniversidad de Sevilla. FQM241: Grupo de Investigación en Localizaciónes
dc.journaltitleAlgorithmicaes
dc.publication.volumen83es
dc.publication.initialPage3741es
dc.publication.endPage3765es

FilesSizeFormatViewDescription
A_2021_Ventura_Maximum box.pdf533.5KbIcon   [PDF] View/Open  

This item appears in the following collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Except where otherwise noted, this item's license is described as: Attribution-NonCommercial-NoDerivatives 4.0 Internacional