Online Primal-Dual Algorithms for Covering and Packing

References

• Alon N., Awerbuch B., Azar Y., Buchbinder N., Naor J. The online set cover problem. Proc. 35th Annual ACM Sympos. Theory Comput. (2003) San Diego, CA(ACM, New York) 100–105Google Scholar
• Alon N., Awerbuch B., Azar Y., Buchbinder N., Naor J. A general approach to online network optimization problems. ACM Trans. Algorithms (2006) 2(4):640–660Crossref, Google Scholar
• Aspnes J., Azar Y., Fiat A., Plotkin S. A., Waarts O. On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM (1997) 44(3):486–504Crossref, Google Scholar
• Awerbuch B., Azar Y., Bartal Y. On-line generalized Steiner problem. Theoret. Comput. Sci. (2004) 324(2–3):313–324Crossref, Google Scholar
• Awerbuch B., Azar Y., Plotkin S. Throughput-competitive on-line routing. Proc. 34th Annual IEEE Sympos. Foundations Comput. Sci. (1993) (IEEE)32–40Google Scholar
• Bansal N., Buchbinder N., Naor J. A primal-dual randomized algorithm for weighted paging. Proc. 48th Annual IEEE Sympos. Foundations Comput. Sci. (2007) (IEEE)507–517Google Scholar
• Berman P., Coulston C. On-line algorithms for Steiner tree problems. Proc. 29th Annual ACM Sympos. Theory Comput. (1997) (ACM)344–353Google Scholar
• Borodin A., El-Yaniv R.Online Computation and Competitive Analysis (1998) (Cambridge University Press, New York) Google Scholar
• Buchbinder N., Naor J. Online primal-dual algorithms for covering and packing problems. 13th Annual Eur. Sympos. Algorithms (2005) (Springer)689–701Google Scholar
• Buchbinder N., Naor J. Improved bounds for online routing and packing via a primal-dual approach. Proc. 47th Annual IEEE Sympos. Foundations Comput. Sci. (2006) (IEEE)293–304Google Scholar
• Buchbinder N., Jain K., Naor J. Online primal-dual algorithms for maximizing ad-auctions revenue. Proc. 15th Annual Eur. Sympos. (2007) 253–264Crossref, Google Scholar
• Fleischer L. K. Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math. (2000) 13(4):505–520Crossref, Google Scholar
• Fleischer L. K. A fast approximation scheme for fractional covering problems with variable upper bounds. Proc. 15th Annual ACM-SIAM Sympos. Discrete Algorithms (2004) (ACM-SIAM)1001–1010Google Scholar
• Garg N., Khandekar R. Fractional covering with upper bounds on the variables: Solving LPs with negative entries. Proc. 12th Annual Eur. Sympos. Algorithms (2004) 371–382Google Scholar
• Garg N., Könemann J. Faster and simpler algorithms for multicommodity flow and other packing problems. SIAM J. Comput. (2007) 37(2):630–652Crossref, Google Scholar
• Garg N., Young N. E. On-line end-to-end congestion control. Proc. 43rd Sympos. Foundations Comput. Sci. (2002) (ACM-SIAM)303–312Google Scholar
• Goel A., Meyerson A., Plotkin S. A. Combining fairness with throughput: Online routing with multiple objectives. J. Comput. Syst. Sci. (2001) 63(1):62–79Crossref, Google Scholar
• Goemans M. X., Williamson D. P. A general approximation technique for constrained forest problems. SIAM J. Comput. (1995) 24:296–317Crossref, Google Scholar
• Imase M., Waxman B. M. Dynamic Steiner tree problem. SIAM J. Discrete Math. (1991) 4:369–384Crossref, Google Scholar
• Karlin A. R., Kenyon C., Randall D. Dynamic TCP acknowledgement and other stories about e/(e−1). Proc. 33rd Annual ACM Sympos. Theory Comput. (2001) (ACM)502–509Google Scholar
• Karp R. M., Vazirani U. V., Vazirani V. V. An optimal algorithm for online bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput. (1990) (ACM)352–358Google Scholar
• Kolliopoulos S. G., Young N. E. Tight approximation results for general covering integer programs. Proc. 42nd Sympos. Foundations Comput. Sci. (2001) 522–528Google Scholar
• Luby M., Nisan N. A parallel approximation algorithm for positive linear programming. Proc. 25th Annual ACM Sympos. Theory Comput. (1993) (ACM)448–457Google Scholar
• Mehta A., Saberi A., Vazirani U., Vazirani V. Adwords and generalized on-line matching. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (2005) (IEEE)264–273Google Scholar
• Meyerson A. The parking permit problem. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (2005) (IEEE)274–284Google Scholar
• Plotkin S., Shmoys D., Tardos É. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. (1995) 20:257–301Link, Google Scholar
• Raghavan P. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. Syst. Sci. (1988) 37(2):130–143Crossref, Google Scholar
• Raghavan P., Thompson C. D. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica (1987) 7:365–374Crossref, Google Scholar
• Srinivasan A. Improved approximation guarantees for packing and covering integer programs. SIAM J. Comput. (1999) 29(2):648–670Crossref, Google Scholar
• Young N. E. Randomized rounding without solving the linear program. Proc. 6th Annual ACM-SIAM Sympos. Discrete Algorithms (1995) (ACM-SIAM)170–178Google Scholar