DISTRIBUTED RESOURCE ALLOCATION

Disclosed methods, systems, and apparatus, include computer programs encoded on computer storage media, for performing allocation of M resources among N users into K pools by solving a knapsack problem (KP) using a distributed computing system. The method includes: receiving data representing K global constraints and L local constraints of the KP; transforming the KP into a dual problem using K dual multipliers; decomposing the dual problem into N sub-problems; performing two or more iterations in solving the dual problem, wherein in one iteration, for each dual multiplier corresponding to a global constraint corresponding to a pool: determining an updated dual multiplier for the global constraint corresponding to the pool to be a non-negative threshold; and computing M decision variables of each of the N users corresponding to the updated dual multiplier in solving each of the N sub-problems corresponding to the each of the N users.