3 papers
cs.DS2021
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…
cs.DS2017
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…
cs.DS2016
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…