Online Primal-Dual Algorithms for Covering and Packing Problems
作者： Niv Buchbinder , Joseph Naor
DOI: 10.1007/11561071_61
关键词: Set packing 、 Range (mathematics) 、 Packing problems 、 Computer science 、 Algorithm 、 Function (mathematics) 、 Space (mathematics) 、 Profit (accounting) 、 Optimization problem 、 Mathematical optimization 、 Covering problems
摘要: We study a wide range of online covering and packing optimization problems. In an problem linear cost function is known in advance, but the constraints that define feasible solution space are given one by fashion. profit as well exact not fully advance. each round additional information about revealed. provide general deterministic schemes for fractional also algorithms couple integral
springer.com
sci-hub.se 参考文章(27)
Naveen Garg, Rohit Khandekar, Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries european symposium on algorithms. pp. 371- 382 ,(2004) , 10.1007/978-3-540-30140-0_34
A.M. Meyerson, The parking permit problem foundations of computer science. pp. 274- 284 ,(2005) , 10.1109/SFCS.2005.72
Ran El-Yaniv, Allan Borodin, Online Computation and Competitive Analysis ,(1998)
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
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (Seffi) Naor, A general approach to online network optimization problems ACM Transactions on Algorithms. ,vol. 2, pp. 640- 660 ,(2006) , 10.1145/1198513.1198522
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
Baruch Awerbuch, Yossi Azar, Yair Bartal, On-line generalized Steiner problem Theoretical Computer Science. ,vol. 324, pp. 313- 324 ,(2004) , 10.1016/J.TCS.2004.05.021
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
Aravind Srinivasan, Improved Approximation Guarantees for Packing and Covering Integer Programs SIAM Journal on Computing. ,vol. 29, pp. 648- 670 ,(1999) , 10.1137/S0097539796314240
Michel X. Goemans, David P. Williamson, A General Approximation Technique for Constrained Forest Problems SIAM Journal on Computing. ,vol. 24, pp. 296- 317 ,(1995) , 10.1137/S0097539793242618