Abstract
We survey some recent progress on the design and the analysis of online algorithms for optimization problems with non-linear, usually convex, objectives. We focus on an extension of the online primal dual technique, and highlight its application in a number of applications, including an online matching problem with concave returns, an online scheduling problem with speed-scalable machines subjective to convex power functions, and a family of online covering and packing problems with convex objectives.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Some applications of the online primal dual technique maintain an alternative set of invariants, e.g., one may consider kee** primal and dual objectives equal and guaranteeing primal feasibility, while showing approximate dual feasibility. However, such variants can be easily rewritten to fit into the framework in this chapter.
References
Agrawal, S., Devanur, N.R.: Fast algorithms for online stochastic convex programming. In: Proceedings of the 26th Annual Symposium on Discrete Algorithms. SIAM, Philadelphia (2015)
Anand, S., Garg, N., Kumar, A.: Resource augmentation for weighted flow-time explained by dual fitting. In: Proceedings of the 23rd Annual Symposium on Discrete Algorithms, pp. 1228–1241. SIAM, Philadelphia (2012)
Azar, Y., Buchbinder, N., Chan, T.H., Chen, S., Cohen, I.R., Gupta, A., Huang, Z., Kang, N., Nagarajan, V., Naor, J., Panigrahi, D.: Online algorithms for covering and packing problems with convex objectives. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 148–157. IEEE, Piscataway (2016)
Bansal, N., Chan, H.L., Pruhs, K.: Speed scaling with an arbitrary power function. In: Proceedings of the 20th Annual symposium on discrete algorithms, pp. 693–701. SIAM, Philadelphia (2009)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal: dual approach. Found. Trends Theor. Comput. Sci. 3(2–3), 93–263 (2009)
Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270–286 (2009)
Buchbinder, N., Jain, K., Naor, J.S.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: Algorithms–ESA, pp. 253–264. Springer, Berlin (2007)
Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1998)
Devanur, N.R., Huang, Z.: Primal dual gives almost optimal energy efficient online algorithms. In: Proceedings of the 25th Annual Symposium on Discrete Algorithms, pp. 1123–1140. SIAM, Philadelphia (2014)
Devanur, N.R., Jain, K.: Online matching with concave returns. In: Proceedings of the 44th Annual Symposium on Theory of Computing, pp. 137–144. ACM, New York (2012)
Gupta, A., Krishnaswamy, R., Pruhs, K.: Online primal-dual for non-linear optimization with applications to speed scaling. In: Approximation and Online Algorithms, pp. 173–186. Springer, Berlin (2013)
Huang, Z., Kim, A.: Welfare maximization with production costs: a primal dual approach. In: Proceedings of the 26th Annual Symposium on Discrete Algorithms. SIAM, Philadelphia (2015)
Karush, W.: Minima of functions of several variables with inequalities as side constraints. PhD thesis, Master’s Thesis, Department of Mathematics, University of Chicago (1939)
Kuhn, H.W., Tucker, A.W.: Nonlinear programming. In: Proceedings of 2nd Berkeley Symposium (1951)
Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. J. ACM 54(5), 22 (2007)
Nguyen, K.T.: Lagrangian duality in online scheduling with resource augmentation and speed scaling. In: Algorithms–ESA, pp. 755–766. Springer, Berlin (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Huang, Z. (2019). Online Combinatorial Optimization Problems with Non-linear Objectives. In: Du, DZ., Pardalos, P., Zhang, Z. (eds) Nonlinear Combinatorial Optimization. Springer Optimization and Its Applications, vol 147. Springer, Cham. https://doi.org/10.1007/978-3-030-16194-1_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-16194-1_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-16193-4
Online ISBN: 978-3-030-16194-1
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)