How the Experts Algorithm Can Help Solve LPs Online

DOI10.1287/moor.2016.0782zbMath1349.90604arXiv1407.5298OpenAlexW1569599893MaRDI QIDQ2833109

Marco Molinaro, Anupam Gupta

Publication date: 16 November 2016

Published in: Mathematics of Operations Research, Algorithms - ESA 2014 (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingonline algorithmssecretary problemexperts algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (9)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds ⋮ Primal Beats Dual on Online Packing LPs in the Random-Order Model ⋮ Competitive online algorithms for resource allocation over the positive semidefinite cone ⋮ Online Assortment and Market Segmentation under Bertrand Competition with Set-Dependent Revenues ⋮ Configuration balancing for stochastic requests ⋮ Simple and fast algorithm for binary integer and online linear programming ⋮ Unnamed Item ⋮ Interior-Point-Based Online Stochastic Bin Packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite exchangeable sequences
• On tail probabilities for martingales
• Weak convergence and empirical processes. With applications to statistics
• Efficient algorithms for online decision problems
• An Analysis of Bid-Price Controls for Network Revenue Management
• Geometry of Online Packing Linear Programs
• A Dynamic Near-Optimal Algorithm for Online Linear Programming
• Online Learning and Online Convex Optimization
• AdWords and generalized online matching
• Online Stochastic Packing Applied to Display Ad Allocation
• A Knapsack Secretary Problem with Applications
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• A maximal inequality for partial sums of finite exchangeable sequences of random variables
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Fast Algorithms for Online Stochastic Convex Programming
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems

This page was built for publication: How the Experts Algorithm Can Help Solve LPs Online