81 citations · 310 across the 59 of their papers we have counts for
6 papers · 1 filter
Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs
Guy E. Blelloch, Anupam Gupta, Ioannis Koutis +3
We present the design and analysis of a near linear-work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input of a SDD -by- matrix …
Welfare and Profit Maximization with Production Costs
Avrim Blum, Anupam Gupta, Yishay Mansour +1
Combinatorial Auctions are a central problem in Algorithmic Mechanism Design: pricing and allocating goods to buyers with complex preferences in order to maximize some desired obje…
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…
Iterative Constructions and Private Data Release
Anupam Gupta, Aaron Roth, Jonathan Ullman
In this paper we study the problem of approximately releasing the cut function of a graph while preserving differential privacy, and give new algorithms (and new analyses of existi…
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…