Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Quad-kd trees: A general framework for kd trees and quad trees

  • Bereczky, Nikolett
  • Duch Brown, Amalia
  • Németh, Krisztián
  • Roura Ferret, Salvador
We introduce the quad-kd tree: a general purpose and hierarchical data structure for the storage of multidimensional points. Quad-kd trees include point quad trees and kd trees as particular cases and therefore they could constitute a general framework for the study of fundamental properties of trees similar to them. Besides, quad-kd trees can be tuned by means of insertion heuristics and bucketing techniques to obtain trade-offs between their costs in time and space. We propose three such heuristics and we show analytically and experimentally their competitive performance. Our analytical results back the experimental outcomes and suggest that the quad-kd tree is a flexible data structure that can be tailored to the resource requirements of a given application., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The social cost of congestion games by imposing variable delays

  • Díaz Cort, Josep
  • Giotis, Ioannis
  • Kirousis, Lefteris
  • Mourtos, Ioannis
  • Serna Iglesias, María José
© <year>. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, In this study, we describe a new coordination mechanism for non-atomic congestion games that leads to a (selfish) social cost which is arbitrarily close to the non-selfish optimal. This mechanism incurs no additional cost, in contrast to tolls that typically differ from the social cost as expressed in terms of delays., Peer Reviewed, Postprint (author's final draft)