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

Simple item page
dc.creatorLu, Yingdong
dc.creatorYao, David
dc.date2008-04-10
dc.date2008-05-09
dc.date.accessioned2026-07-07T09:37:41Z
dc.date.available2026-07-07T09:37:41Z
dc.descriptionTwo seemingly unrelated problems, scheduling a multiclass queueing system and minimizing a submodular function, share a rather deep connection via the polymatroid that is characterized by a submodular set function on the one hand and represents the performance polytope of the queueing system on the other hand. We first develop what we call a {\it grouping} algorithm that solves the queueing scheduling problem under side constraints, with a computational effort of $O(n^3LP(n))$, $n$ being the number of job classes, and LP(n) being the computational efforts of solving a linear program with no more than $n$ variables and $n$ constraints. The algorithm organizes the job classes into groups, and identifies the optimal policy to be a priority rule across the groups and a randomized rule within each group (to enforce the side constraints). We then apply the grouping algorithm to the submodular function minimization, mapping the latter to a queueing scheduling problem with side constraints. %Each time the algorithm is applied, it identifies a subset; and We show the minimizing subset can be identified by applying the grouping algorithm $n$ times. Hence, this results in a algorithm that minimizes a submodular function with an effort of $O(n^4LP(n))$.
dc.descriptionCorrected some misstatement in abstract and introduction
dc.identifierhttps://arxiv.org/abs/0804.1603
dc.identifierhttp://arxiv.org/abs/0804.1603
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/160548
dc.subjectOptimization and Control
dc.titleLinear Optimization over a Polymatroid with Side Constraints -- Scheduling Queues and Minimizing Submodular Functions
dc.typetext

Files

Collections

arXiv