The design and analysis of a modified work function algorithm for solving the on-line k-server problem

MaRDI QIDQ2970221zbMATH OpenFDO

Authors Alfonz Baumgartner, Tomislav Rudec, Robert Manger

Publication date 29 March 2017

zbMATH Keywords

\(k\)-server problemcompetitivenesscomputational complexityexperimentsimplementationmoving windowsnetwork flowsonline algorithmsonline problemsperformancework function algorithm (WFA)

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• A fast work function algorithm for solving the k-server problem
• A fast approximate implementation of the work function algorithm for solving the k-server problem
• A new upper bound on the work function algorithm for the k-server problem
• scientific article; zbMATH DE number 1500547
• A new approach to solve the k-server problem based on network flows and flow cost reduction

Cited in

(7)

• On the additive constant of the k-server work function algorithm
• The K-server problem via a modern optimization lens
• The online \(k\)-server problem with rejection
• A fast work function algorithm for solving the k-server problem
• A fast approximate implementation of the work function algorithm for solving the k-server problem
• A new approach to solve the k-server problem based on network flows and flow cost reduction
• A fast implementation of the optimal off-line algorithm for solving the k-server problem

This page was built for publication: The design and analysis of a modified work function algorithm for solving the on-line \(k\)-server problem

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