Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
作者： Niv Buchbinder , Kamal Jain , Joseph (Seffi) Naor
DOI: 10.1007/978-3-540-75520-3_24
关键词: Matching (graph theory) 、 Competitive analysis 、 Weak duality 、 Mathematical optimization 、 Algorithm 、 Bipartite graph 、 Common value auction 、 Online algorithm 、 Function (mathematics) 、 Mathematics 、 Bounded function
摘要: … We show that this approach is useful for analyzing other classical online algorithms … the primal-dual method will prove useful in other online scenarios as well. The primal-dual approach …
springer.com
springerlink.com
stanford.edu 
columbia.edu 
acm.org 参考文章(17)
Nir Andelman, Yishay Mansour, Auctions with Budget Constraints Algorithm Theory - SWAT 2004. pp. 26- 38 ,(2004) , 10.1007/978-3-540-27810-8_4
A. Mehta, A. Saberi, U. Vazirani, V. Vazirani, AdWords and generalized on-line matching foundations of computer science. pp. 264- 273 ,(2005) , 10.1109/SFCS.2005.12
Niv Buchbinder, Joseph Naor, Online Primal-Dual Algorithms for Covering and Packing Problems Algorithms – ESA 2005. pp. 689- 701 ,(2005) , 10.1007/11561071_61
Anna R. Karlin, Claire Kenyon, Dana Randall, Dynamic TCP acknowledgement and other stories about e/(e-1) Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01. pp. 502- 509 ,(2001) , 10.1145/380752.380845
Niv Buchbinder, Joseph Naor, Improved bounds for online routing and packing via a primal-dual approach foundations of computer science. pp. 293- 304 ,(2006) , 10.1109/FOCS.2006.39
Daniel R. Dooly, Sally A. Goldman, Stephen D. Scott, On-line analysis of the TCP acknowledgment delay problem Journal of the ACM. ,vol. 48, pp. 243- 273 ,(2001) , 10.1145/375827.375843
Jason D. Hartline, Avrim Blum, Near-optimal online auctions symposium on discrete algorithms. pp. 1156- 1163 ,(2005) , 10.5555/1070432.1070597
Noga Alon, Baruch Awerbuch, Yossi Azar, None, The online set cover problem symposium on the theory of computing. pp. 100- 105 ,(2003) , 10.1145/780542.780558
Ashish Goel, Adam Meyerson, Serge Plotkin, Combining Fairness with Throughput Journal of Computer and System Sciences. ,vol. 63, pp. 62- 79 ,(2001) , 10.1006/JCSS.2001.1755
Bala Kalyanasundaram, Kirk R. Pruhs, An optimal deterministic algorithm for online b -matching Theoretical Computer Science. ,vol. 233, pp. 319- 325 ,(2000) , 10.1016/S0304-3975(99)00140-1