Complexity Links Between Matrix Multiplication, Klee's Measure and Call Access Control for Satellite Constellations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2001

Complexity Links Between Matrix Multiplication, Klee's Measure and Call Access Control for Satellite Constellations

Résumé

We study the complexity of computing the maximum load of weighted rectangles (the load on a point is defined as the sum of the weights of intersecting rectangles on this point). We relate the complexity of the dynamic version of this problem (in which we want to perform insert/delete operations on the rectangles) to the complexity of the matrix multiplication problem in the \maxplus\ algebra. In particular, we show that a significant improvemen- t on the existing solutions for the first one (within $O(n^\theta/2$) per insertion/extraction with $\theta<1$) implies an improvement on the complexity of the latter one (to $O(N^2+\theta)$). Furthermore, this connectio- n makes possible to state a lower bound on a general class of algorithms that include all the most efficient previously known algorithms for the Klee's measure problem. This implies that such solutions cannot be improved by more than a logarithmic factor in their actual form. Finally, all the above results also apply to variations/restrictions of the \emphdepth problem motivated by LEO satellite constellations routing problems.
Fichier principal
Vignette du fichier
RR-4166.pdf (401.88 Ko) Télécharger le fichier

Dates et versions

inria-00072456 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00072456 , version 1

Citer

Jérôme Galtier, Paolo Penna. Complexity Links Between Matrix Multiplication, Klee's Measure and Call Access Control for Satellite Constellations. RR-4166, INRIA. 2001. ⟨inria-00072456⟩
118 Consultations
162 Téléchargements

Partager

Gmail Facebook X LinkedIn More