A Primal Dual Approach for Dynamic Bid Optimization
Linfei Yu, Kun She, Changyuan Yu · 2010
We study the dynamic bid optimization problem via a primal dual approach. In the case we have no information about the distribution of queries, we reconstruct the ln(U=L) + 1 competitive algorithm proposed in [ZCL08] through a systematic way and showed the intuition behind this algorithm. In the case of random permutation model, we showed that the learning technique used in [DH09] can give us a (1 ¡ O(²)) competitive algorithm for any small constant ² > 0 as long as the optimum is large enough.