Abstract
We present an unified approach to study online scheduling problems in the resource augmentation/speed scaling models. Potential function method is extensively used for analyzing algorithms in these models; however, they yields little insight on how to construct potential functions and how to design algorithms for related problems. In the paper, we generalize and strengthen the dual-fitting technique proposed by Anand et al. [1]. The approach consists of considering a possibly non-convex relaxation and its Lagrangian dual; then constructing dual variables such that the Lagrangian dual has objective value within a desired factor of the primal optimum. The competitive ratio follows by the standard Lagrangian weak duality. This approach is simple yet powerful and it is seemingly a right tool to study problems with resource augmentation or speed scaling. We illustrate the approach through the following results.
-
1
We revisit algorithms EQUI and LAPS in Non-clairvoyant Scheduling to minimize total flow-time. We give simple analyses to prove known facts on the competitiveness of such algorithms. Not only are the analyses much simpler than the previous ones, they also explain why LAPS is a natural extension of EQUI to design a scalable algorithm for the problem.
-
2
We consider the online scheduling problem to minimize total weighted flow-time plus energy where the energy power f(s) is a function of speed s and is given by s α for α ≥ 1. For a single machine, we showed an improved competitive ratio for a non-clairvoyant memoryless algorithm. For unrelated machines, we give an O(α/logα)-competitive algorithm. The currently best algorithm for unrelated machines is O(α 2)-competitive.
-
3
We consider the online scheduling problem on unrelated machines with the objective of minimizing ∑ i,j w ij f(F j ) where F j is the flow-time of job j and f is an arbitrary non-decreasing cost function with some nice properties. We present an algorithm which is \(\frac{1}{1-3\epsilon}\)-speed, \(\frac{2K(\epsilon)}{\epsilon}\)-competitive where K(ε) is a function depending on f and ε. The algorithm does not need to know the speed (1 + ε) a priori. A corollary is a (1 + ε)-speed, \(\frac{k}{\epsilon^{1+1/k}}\)-competitive algorithm (which does not know ε a priori) for the objective of minimizing the weighted ℓ k -norm of flow-time.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Anand, S., Garg, N., Kumar, A.: Resource augmentation for weighted flow-time explained by dual fitting. In: Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, pp. 1228–1241 (2012)
Azar, Y., Epstein, L., Richter, Y., Woeginger, G.J.: All-norm approximation algorithms. J. Algorithms 52(2), 120–133 (2004)
Bansal, N., Chan, H.-L.: Weighted flow time does not admit o(1)-competitive algorithms. In: Proc. 20th ACM-SIAM Symposium on Discrete Algorithms, pp. 1238–1244 (2009)
Bansal, N., Chan, H.-L., Lam, T.-W., Lee, L.-K.: Scheduling for speed bounded processors. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 409–420. Springer, Heidelberg (2008)
Bansal, N., Chan, H.-L., Pruhs, K.: Speed scaling with an arbitrary power function. In: Proc. 20th ACM-SIAM Symposium on Discrete Algorithms, pp. 693–701 (2009)
Bansal, N., Pruhs, K.R.: Server scheduling in the weighted ℓ p norm. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 434–443. Springer, Heidelberg (2004)
Bansal, N., Pruhs, K.: The geometry of scheduling. In: Proc. 51th Symposium on Foundations of Computer Science, pp. 407–414 (2010)
Bansal, N., Pruhs, K.: Weighted geometric set multi-cover via quasi-uniform sampling. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 145–156. Springer, Heidelberg (2012)
Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science 3(2-3), 93–263 (2009)
Chadha, J.S., Garg, N., Kumar, A., Muralidhara, V.N.: A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. In: Proc. 41st ACM Symposium on Theory of Computing, pp. 679–684 (2009)
Chan, H.-L., Edmonds, J., Lam, T.W., Lee, L.-K., Marchetti-Spaccamela, A., Pruhs, K.: Nonclairvoyant speed scaling for flow and energy. Algorithmica 61(3), 507–517 (2011)
Chan, S.-H., Lam, T.W., Lee, L.-K., Ting, H.-F., Zhang, P.: Non-clairvoyant scheduling for weighted flow time and energy on speed bounded processors. Chicago J. Theor. Comput. Sci. (2011)
Chekuri, C., Khanna, S., Zhu, A.: Algorithms for minimizing weighted flow time. In: Proc. 33rd ACM Symposium on Theory of Computing, pp. 84–93 (2001)
Edmonds, J.: Scheduling in the dark. Theor. Comput. Sci. 235(1), 109–141 (2000)
Edmonds, J., Pruhs, K.: Scalably scheduling processes with arbitrary speedup curves. ACM Transactions on Algorithms 8(3), 28 (2012)
Fox, K., Korupolu, M.: Weighted flowtime on capacitated machines. In: Proc. 24th ACM-SIAM Symposium on Discrete Algorithms, pp. 129–143 (2013)
Garg, N., Kumar, A.: Minimizing average flow-time: Upper and lower bounds. In: Proc. 48th Symposium on Foundations of Computer Science, pp. 603–613 (2007)
Gupta, A., Krishnaswamy, R., Pruhs, K.: Online primal-dual for non-linear optimization with applications to speed scaling. In: Proc. 10th Workshop on Approximation and Online Algorithms, pp. 173–186 (2012)
Im, S.: Online Scheduling Algorithms for Average Flow Time and its Variants. PhD thesis, University of Illinois at Urbana-Champaign (2012)
Im, S., Moseley, B., Pruhs, K.: A tutorial on amortized local competitiveness in online scheduling. SIGACT News 42(2), 83–97 (2011)
Im, S., Moseley, B., Pruhs, K.: Online scheduling with general cost functions. In: Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, pp. 1254–1265 (2012)
Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617–643 (2000)
Kling, P., Pietrzyk, P.: Profitable scheduling on multiple speed-scalable processors. In: Proc. 25th Symposium on Parallelism in Algorithms and Architectures (2013)
Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: A unified approach to scheduling on unrelated parallel machines. J. ACM 56(5) (2009)
Lam, T.W., Lee, L.-K., To, I.K., Wong, P.W.H.: Online speed scaling based on active job count to minimize flow plus energy. Algorithmica 65(3), 605–633 (2013)
Motwani, R., Phillips, S., Torng, E.: Non-clairvoyant scheduling. Theor. Comput. Sci. 130(1), 17–47 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nguyen, K.T. (2013). Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling. In: Bodlaender, H.L., Italiano, G.F. (eds) Algorithms – ESA 2013. ESA 2013. Lecture Notes in Computer Science, vol 8125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40450-4_64
Download citation
DOI: https://doi.org/10.1007/978-3-642-40450-4_64
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40449-8
Online ISBN: 978-3-642-40450-4
eBook Packages: Computer ScienceComputer Science (R0)