Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
From MaRDI portal
Publication:1331949
DOI10.1016/0304-3975(94)90158-9zbMath0834.68042OpenAlexW2010671846MaRDI QIDQ1331949
Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer
Publication date: 29 August 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)90158-9
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed algorithms (68W15)
Related Items (9)
Bounds on Distance Distributions in Codes of Given Size ⋮ Load balanced distributed directories ⋮ Randomly colouring graphs (a combinatorial view) ⋮ Fourier analysis and large independent sets in powers of complete graphs ⋮ Optimal nearest neighbor queries in sensor networks ⋮ Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality ⋮ Distributed transactional memory for general networks ⋮ Distributed Corruption Detection in Networks ⋮ An analysis framework for distributed hierarchical directories
Cites Work
- Unnamed Item
- Unnamed Item
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Ramanujan graphs
- Eigenvalues and expanders
- Inequalities in Fourier analysis
- Complexity of network synchronization
- Graph spanners
- The Token Distribution Problem
- Online tracking of mobile users
- Optimal numberings and isoperimetric problems on graphs
This page was built for publication: Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
