Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds: the sampled dual LP optimum converges to the stochastic-program optimum with E‖p_n − p‖² ≤ C·m log m·log log n / nResearch Paper
Online linear programming (OLP) models sequential resource allocation: orders arrive one at a time, each must be accepted or rejected on arrival, and accepted orders consume the capacities of a linear program. It covers network revenue management, online auctions, matching and the multi-secretary problem. Almost every OLP algorithm uses the same…