# Refined Shapley-Folkman Lemma and Its Application in Duality Gap Estimation

arXiv: https://arxiv.org/abs/1610.05416 · HTML: https://mlsanity.com/paper/1610.05416/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2016.

## Built on by (most cited first, 1 of 1)

- [The Nonconvex Geometry of Linear Inverse Problems](https://mlsanity.com/paper/2101.02776/) (2021)

## Abstract (arXiv)

Based on concepts like kth convex hull and finer characterization of nonconvexity of a function, we propose a refinement of the Shapley-Folkman lemma and derive a new estimate for the duality gap of nonconvex optimization problems with separable objective functions. We apply our result to a network flow problem and the dynamic spectrum management problem in communication systems as examples to demonstrate that the new bound can be qualitatively tighter than the existing ones. The idea is also applicable to cases with general nonconvex constraints.