4 papers
Approximations for Allocating Indivisible Items with Concave-Additive Valuations
Nathaniel Kell, Kevin Sun
We study a general allocation setting where agent valuations are concave additive. In this model, a collection of items must be uniquely distributed among a set of agents, where ea…
Online Load Balancing for Related Machines
Sungjin Im, Nathaniel Kell, Debmalya Panigrahi +1
In the load balancing problem, introduced by Graham in the 1960s (SIAM J. of Appl. Math. 1966, 1969), jobs arriving online have to be assigned to machines so to minimize an objecti…
Online Budgeted Allocation with General Budgets
Nathaniel Kell, Debmalya Panigrahi
We study the online budgeted allocation (also called ADWORDS) problem, where a set of impressions arriving online are allocated to a set of budget-constrained advertisers to maximi…
Tight Bounds for Online Vector Scheduling
Sungjin Im, Nathaniel Kell, Janardhan Kulkarni +1
Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multi-dimensional and characterized by demand vectors…