Online learning for min-max discrete problems

DOI10.1016/J.TCS.2022.07.024MaRDI QIDQ2166779zbMATH OpenOpenAlexFDO

Authors Evripidis Bampis, Dimitris Christou, Kim Thang Nguyen, Bruno Escoffier

Publication date 25 August 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

min-max problemsno-regret algorithmon-line learning

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Efficient online linear optimization with approximation algorithms
• The computational power of optimization in online learning
• Regret in online combinatorial optimization
• Playing Games with Approximation Algorithms
• Logarithmic Regret Algorithms for Online Convex Optimization

Cites work

• A decision-theoretic generalization of on-line learning and an application to boosting
• Algorithms for Scheduling Independent Tasks
• Algorithms for two bottleneck optimization problems
• Efficient algorithms for online decision problems
• scientific article; zbMATH DE number 3128728 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Learning in auctions: regret is hard, envy is easy
• Near-optimal algorithms for online matrix prediction
• On non-optimally expanding sets in Grassmann graphs
• Online linear optimization and adaptive routing
• Online submodular minimization
• Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations
• Oracle-efficient Online Learning and Auction Design
• Playing Games with Approximation Algorithms
• Regret Minimization for Reserve Prices in Second-Price Auctions
• The computational power of optimization in online learning
• The Min-Max Spanning Tree Problem and some extensions
• The weighted majority algorithm
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

Cited in

(1)

• The relaxed online maximum margin algorithm

This page was built for publication: Online learning for min-max discrete problems

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