Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00072456
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 10:00:38 AM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:13:29 PM

Identifiers

  • HAL Id : inria-00072456, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

294

Files downloads

337