Polytime Decomposition of Generalized Submodular Base Polytopes with Efficient Sampling

We consider the problem of efficient decomposition of a given point $x$ in an $n$-dimensional convex polytope into convex combination of its extreme points. Besides the widespread scopes of the problem in theory of convex polytopes in mathematics, the problem also has applications in online combinatorial optimization problems. Towards this we first propose a general class of convex polytopes–Generalized Submodular Base Polytopes (GSBPs)–that includes several well known convex polytopes as its special case including permutahedron, $k$-forest, spanning tree, combinatorial subset choice polytopes. We next propose a general decomposition algorithm for above class of GSBPs that uses the novel idea of first decomposing the given point into at most $n$ \emph{face centers}, and further decomposing each face center into \emph{extreme points} of their corresponding faces. In addition, we discover a few special class of \emph{partition-respecting} and \emph{symmetric} GSBPs for which the above two steps could be performed in respectively $O(n^2 + nT(f))$ and $O(n^2T(f))$ time. We also give a complete characterization of the underlying submodular function $f$, for which the associated GSBP satisfies the above properties. One interesting fact is we show that the support of the resulting decomposition with our proposed algorithm is only $poly(n)$ in the number of extreme points which respects \emph{efficient sampling} from the resulting distribution. Finally we corroborate our theoretical results with empirical evaluations.