Efficient online linear optimization with approximation algorithms

DOI10.1287/MOOR.2020.1053MaRDI QIDQ4991673zbMATH OpenOpenAlexFDO

Authors Dan Garber

Publication date 3 June 2021

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.03093

zbMATH Keywords

approximation algorithmsonline algorithmsonline learningonline linear optimizationregret minimization

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25)

Recommendations

• Playing Games with Approximation Algorithms
• The computational power of optimization in online learning
• Regret in online combinatorial optimization
• Oracle-efficient Online Learning and Auction Design
• Online linear optimization over permutations

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Adaptive routing with end-to-end feedback: distributed learning and geometric approaches
• Combinatorial online prediction via metarounding
• Computing correlated equilibria in multi-player games
• Convex optimization: algorithms and complexity
• Efficient algorithms for online decision problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Playing Games with Approximation Algorithms
• The ellipsoid method and its consequences in combinatorial optimization
• Volumetric spanners: an efficient exploration basis for learning

Cited in

(12)

• Online learning for min-max discrete problems
• Linear programming with online learning
• Online linear optimization over permutations
• scientific article; zbMATH DE number 1003270 (Why is no real title available?)
• Online Semidefinite Programming.
• Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
• The computational power of optimization in online learning
• Introduction to Online Convex Optimization
• The relaxed online maximum margin algorithm
• scientific article; zbMATH DE number 7765403 (Why is no real title available?)
• Online Linear Extractors for Independent Sources
• An \(\alpha \)-regret analysis of adversarial bilateral trade

This page was built for publication: Efficient online linear optimization with approximation algorithms

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