A dynamic near-optimal algorithm for online linear programming
From MaRDI portal
Abstract: A natural optimization model that formulates many online resource allocation and revenue management problems is the online linear program (LP) in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In such a model, a decision variable has to be set each time a column is revealed without observing the future inputs and the goal is to maximize the overall objective function. In this paper, we provide a near-optimal algorithm for this general class of online problems under the assumption of random order of arrival and some mild conditions on the size of the LP right-hand-side input. Specifically, our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from the revealed columns in the previous period are used to determine the sequential decisions in the current period. Due to the feature of dynamic learning, the competitiveness of our algorithm improves over the past study of the same problem. We also present a worst-case example showing that the performance of our algorithm is near-optimal.
Recommendations
- Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
- Near optimal online algorithms and fast approximation algorithms for resource allocation problems
- Primal beats dual on online packing LPs in the random-order model
- Primal beats dual on online packing LPs in the random-order model
- Simple and fast algorithm for binary integer and online linear programming
Cites work
- A Knapsack Secretary Problem with Applications
- A multiple-choice secretary algorithm with applications to online auctions
- A Multiproduct Dynamic Pricing Problem and Its Applications to Network Yield Management
- AdWords and generalized online matching
- An analysis of bid-price controls for network revenue management
- Asymptotic Behavior of an Allocation Policy for Revenue Management
- Dynamic pricing in the presence of inventory considerations: research overview, current practices, and future directions
- scientific article; zbMATH DE number 5764830 (Why is no real title available?)
- scientific article; zbMATH DE number 52944 (Why is no real title available?)
- Improved Bounds for Online Stochastic Matching
- Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
- Online bipartite matching with unknown distributions
- Online primal-dual algorithms for covering and packing
- Online Stochastic Matching: Beating 1-1/e
- Online stochastic packing applied to display ad allocation
- Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons
- Prediction, Learning, and Games
- The Design of Competitive Online Algorithms via a Primal—Dual Approach
- Weak convergence and empirical processes. With applications to statistics
Cited in
(51)- Competitive online algorithms for resource allocation over the positive semidefinite cone
- Railway delay management with passenger rerouting considering train capacity constraints
- Improved online algorithms for knapsack and GAP in the random order model
- Provably training overparameterized neural network classifiers with non-convex constraints
- Online generalized assignment problem with historical information
- Primal-dual analysis for online interval scheduling problems
- Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
- Iterative computation of security strategies of matrix games with growing action set
- Linear programming with online learning
- New results for the \(k\)-secretary problem
- Close the gaps: a learning-while-doing algorithm for single-product revenue management problems
- Approximation algorithms for stochastic combinatorial optimization problems
- Model predictive control for dynamic resource allocation
- Bicriteria online matching: maximizing weight and cardinality
- scientific article; zbMATH DE number 1003270 (Why is no real title available?)
- A dynamic learning algorithm for online matching problems with concave returns
- A stochastic algorithm for online bipartite resource allocation problems
- Online appointment scheduling in the random order model
- Primal beats dual on online packing LPs in the random-order model
- Near optimal online algorithms and fast approximation algorithms for resource allocation problems
- Sequential interdiction with incomplete information and learning
- Maximizing profit with convex costs in the random-order model
- Online resource allocation under partially predictable demand
- Fair resource allocation in a volatile marketplace
- Deals or no deals: contract design for online advertising
- Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
- Submodular secretary problem with shortlists
- Online resource allocation with personalized learning
- Bandits with global convex constraints and objective
- An approximation algorithm for network revenue management under nonstationary arrivals
- Nonstationary bandits with habituation and recovery dynamics
- Online stochastic matching: new algorithms with better bounds
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- scientific article; zbMATH DE number 7053386 (Why is no real title available?)
- Online stochastic weighted matching algorithm for real‐time shared parking
- Configuration balancing for stochastic requests
- scientific article; zbMATH DE number 7765403 (Why is no real title available?)
- Online allocation and display ads optimization with surplus supply
- Simple and fast algorithm for binary integer and online linear programming
- The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems
- A truthful near-optimal mechanism for online linear packing-covering problem in the random order model
- Adversarial bandits with knapsacks
- Knapsack secretary with bursty adversary
- Generalized assignment and knapsack problems in the random-order model
- Near-optimal algorithm for supporting small and medium-sized enterprises in ad systems
- Configuration balancing for stochastic requests
- Near-optimal algorithm for supporting small and medium-sized enterprises in ad systems
- Online alternating direction method of multipliers for online composite optimization
- LP-based control for network revenue management under Markovian demands
- From offline to online: sequentially distributing points on a sphere
- On the resolution of misspecified convex optimization and monotone variational inequality problems
This page was built for publication: A dynamic near-optimal algorithm for online linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931707)
