HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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

Jérôme Galtier 1 Paolo Penna
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:00:38 AM
Last modification on : Friday, February 4, 2022 - 3:11:30 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:13:29 PM


  • HAL Id : inria-00072456, version 1



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⟩



Record views


Files downloads