Learning Packing and Covering from Samples

We consider a multiple-choice mixed packing and covering problem in the online setting: at each timestep \(t\), the algorithm faces a collection of \(K\) choices. Each choice consumes some resources, and gives some benefits; both resources and benefits are \(d\)-dimensional vectors. We would like to make a choice for each timestep, such that we use at most \(B\) units of each resource, and we get at least \(B\) units of each kind of benefit. Among its many applications, this general problem captures the question of load-balancing on unrelated machines, where the choices are allocations of jobs to machines.