Linear Optimization over a Polymatroid with Side Constraints -- Scheduling Queues and Minimizing Submodular Functions

Yingdong Lu, David Yao

Two seemingly unrelated problems, scheduling a multiclass queueing system and minimizing a submodular function, share a rather deep connection via the polymatroid that is character…