التفاصيل البيبلوغرافية
| العنوان: |
Maximum Box Problem on Stochastic Points |
| المؤلفون: |
Caraballo de la Cruz, Luis Evaristo, Pérez Lantero, Pablo, Seara, Carlos, Ventura Molina, Inmaculada |
| المساهمون: |
Universidad de Sevilla. Departamento de Matemática Aplicada II, Universidad de Sevilla. FQM241: Grupo de Investigación en Localización |
| بيانات النشر: |
Springer |
| سنة النشر: |
2022 |
| المجموعة: |
idUS - Deposito de Investigación Universidad de Sevilla |
| مصطلحات موضوعية: |
Random weighted points, Boxes, Red and blue points, #P-hardness |
| الوصف: |
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. ; Unión Europea 734922 ; Agencia Estatal de Investigación MTM2016-76272-R ; Ministerio de Ciencia e Innovación PID2019-104129GB-I00 ; Generalitat de Catalunya 2017SGR1640 |
| نوع الوثيقة: |
article in journal/newspaper |
| اللغة: |
English |
| Relation: |
Algorithmica, 83, 3741-3765.; 734922; MTM2016-76272-R; FPU14/04705; PID2019-104129GB-I00; 2017SGR1640; https://link.springer.com/article/10.1007/s00453-021-00882-z; https://idus.us.es/handle//11441/130127 |
| الاتاحة: |
https://idus.us.es/handle//11441/130127 |
| Rights: |
Attribution-NonCommercial-NoDerivatives 4.0 Internacional ; http://creativecommons.org/licenses/by-nc-nd/4.0/ ; info:eu-repo/semantics/openAccess |
| رقم الانضمام: |
edsbas.517302A8 |
| قاعدة البيانات: |
BASE |