Self-adjusting linear networks

DOI10.1007/978-3-030-34992-9_29MaRDI QIDQ6536343zbMATH OpenFDO

Authors Chen Avin, Ingo van Duijn, Stefan Schmid

Publication date 19 April 2024

Full work available at URL https://doi.org/10.1007/978-3-030-34992-9_29

zbMATH Keywords

communication networkscompetitive analysisdistributed algorithmsself-adjusting data structures

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Data structures (68P05) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27)

Recommendations

• Self-adjusting linear networks
• Dynamically optimal self-adjusting single-source tree networks
• Self-adjusting grid networks to minimize expected path length
• Self-adjusting grid networks to minimize expected path length
• Analysis and experimentation on list update algorithms

Cites work

• A combined BIT and TIMESTAMP algorithm for the list update problem
• A competitive analysis of the list update problem with lookahead
• A lower bound for randomized list update algorithms
• Improved Randomized On-Line Algorithms for the List Update Problem
• Off-line algorithms for the list update problem
• Offline list update is NP-hard
• Online balanced repartitioning
• Randomized competitive algorithms for the list update problem
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems

Cited in

(2)

• Dynamically optimal self-adjusting single-source tree networks
• Self-adjusting linear networks

This page was built for publication: Self-adjusting linear networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6536343)