Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint

Official URL: https://dx.doi.org/10.1016/j.disopt.2020.100595

We consider a multi-player optimization where each player has her own optimization problem and the individual problems are connected by a cardinality constraint on their shared resources. We give distributed algorithms that allow each player to solve their own optimization problem and still achieve a global optimization solution for problems that possess a concavity property. For problems without the concavity property, we use concave approximating functions to bound the optimality error and provide empirical results on the deviations from optimality.