Por favor, use este identificador para citar o enlazar este ítem:
https://hdl.handle.net/20.500.12008/27047
Cómo citar
Registro completo de metadatos
| Campo DC | Valor | Lengua/Idioma |
|---|---|---|
| dc.contributor.author | Bermolen, Paola | - |
| dc.contributor.author | Jonckheere, Matthieu | - |
| dc.contributor.author | Larroca, Federico | - |
| dc.contributor.author | Saenz, Manuel | - |
| dc.date.accessioned | 2021-04-12T18:34:49Z | - |
| dc.date.available | 2021-04-12T18:34:49Z | - |
| dc.date.issued | 2020 | - |
| dc.identifier.citation | Bermolen, P., Jonckheere, M., Larroca, F. y otros. Sequential algorithms and independent sets discovering on large sparse random graphs [Preprint]. EN: Mathematics (math.PR-Probability), 2020, pp 1-.29. arXiv:2009.14574. | es |
| dc.identifier.uri | https://hdl.handle.net/20.500.12008/27047 | - |
| dc.description | Computing the size of maximum independent sets is a NP-hard problem for fixed graphs. Characterizing and designing efficient algorithms to estimate this independence number for random graphs are notoriously difficult and still largely open issues. In a companion paper, we showed that a low complexity degree-greedy exploration is actually asymptotically optimal on a large class of sparse random graphs. Encouraged by this result, we present and study two variants of sequential exploration algorithms: static and dynamic degree-aware explorations. We derive hydrodynamic limits for both of them, which in turn allow us to compute the size of the resulting independent set. Whereas the former is simpler to compute, the latter may be used to arbitrarily approximate the degree-greedy algorithm. Both can be implemented in a distributed manner. The corresponding hydrodynamic limits constitute an efficient method to compute or bound the independence number for a large class of sparse random graphs. As an application, we then show how our method may be used to estimate the capacity of a large 802.11-based wireless network. We finally consider further indicators such as the fairness of the resulting configuration, and show how an unexpected trade-off between fairness and capacity can be achieved. | en |
| dc.format.extent | 29 p. | es |
| dc.format.mimetype | application/pdf | es |
| dc.language.iso | en | es |
| dc.publisher | arXiv | es |
| dc.relation.ispartof | Mathematics (math.PR-Probability), arXiv:2009.14574, pp 1-29, Sep 2020 | es |
| dc.rights | Las obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad de la República.(Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014) | es |
| dc.title | Sequential algorithms and independent sets discovering on large sparse random graphs. | en |
| dc.type | Preprint | es |
| dc.contributor.filiacion | Bermolen Paola, Universidad de la República (Uruguay). Facultad de Ingeniería. | - |
| dc.contributor.filiacion | Jonckheere Matthieu, Instituto de Cálculo, UBA/CONICET, Buenos Aires, Argentina | - |
| dc.contributor.filiacion | Larroca Federico, Universidad de la República (Uruguay). Facultad de Ingeniería. | - |
| dc.contributor.filiacion | Saenz Manuel, Instituto de Cálculo, UBA/CONICET, Buenos Aires, Argentina | - |
| dc.rights.licence | Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0) | es |
| Aparece en las colecciones: | Publicaciones académicas y científicas - Instituto de Ingeniería Eléctrica | |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| BJLS20.pdf | Preprint | 2,12 MB | Adobe PDF | Visualizar/Abrir |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons
