A Combinatorial Metrical Task System Problem Under the Uniform Metric

DOI10.1007/978-3-319-46379-7_19zbMath1478.68453OpenAlexW2522942356MaRDI QIDQ2831385

Takumi Nakazono, Ken-Ichiro Moridomi, Kohei Hatano, Eiji Takimoto

Publication date: 9 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2324/1932327

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Uses Software

• AdaBoost.MH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial bandits
• Randomized algorithms for metrical task systems
• A decision-theoretic generalization of on-line learning and an application to boosting
• Efficient algorithms for online decision problems
• Unified Algorithms for Online Learning and Competitive Analysis
• Bandit Online Optimization over the Permutahedron
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• A Polylogarithmic-Competitive Algorithm for the k -Server Problem
• An optimal on-line algorithm for metrical task system
• On the k -server conjecture
• Better Algorithms for Unfair Metrical Task Systems and Applications
• 10.1162/1532443041424328
• A Regularization Approach to Metrical Task Systems
• Changing Bases: Multistage Optimization for Matroids and Matchings