33 citations · 122 across the 14 of their papers we have counts for
3 papers · 1 filter
Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling
Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs
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 as…
Scalably Scheduling Power-Heterogeneous Processors
Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs
We show that a natural online algorithm for scheduling jobs on a heterogeneous multiprocessor, with arbitrary power functions, is scalable for the objective function of weighted fl…
Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro +1
In the stochastic knapsack problem, we are given a knapsack of size B, and a set of jobs whose sizes and rewards are drawn from a known probability distribution. However, we know t…