Computer Science – Data Structures and Algorithms
Scientific paper
2011-09-27
Computer Science
Data Structures and Algorithms
Scientific paper
We reinterpret some online greedy algorithms for a class of nonlinear "load-balancing" problems as solving a mathematical program online. For example, we consider the problem of assigning jobs to (unrelated) machines to minimize the sum of the alpha^{th}-powers of the loads plus assignment costs (the online Generalized Assignment Problem); or choosing paths to connect terminal pairs to minimize the alpha^{th}-powers of the edge loads (online routing with speed-scalable routers). We give analyses of these online algorithms using the dual of the primal program as a lower bound for the optimal algorithm, much in the spirit of online primal-dual results for linear problems. We then observe that a wide class of uni-processor speed scaling problems (with essentially arbitrary scheduling objectives) can be viewed as such load balancing problems with linear assignment costs. This connection gives new algorithms for problems that had resisted solutions using the dominant potential function approaches used in the speed scaling literature, as well as alternate, cleaner proofs for other known results.
Gupta Anupam
Krishnaswamy Ravishankar
Pruhs Kirk
No associations
LandOfFree
Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-63210