A dynamic learning algorithm for online matching problems with concave returns
We consider the online matching problem with concave returns. It is the core model for ad allocation. We propose a dynamic learning algorithm that achieves near-optimal performance for this problem. Our approach is primal-dual based. We overcome the difficulty that arises due to the nonlinearity. We test our algorithm using experimental data and show that it outperforms a myopic approach.
primal-dual online algorithms dynamic price update random permutation model adwords problem