作者：Kulik, Ariel; Shachnai, Hadas; Tamir, Tami
作者单位：Technion Israel Institute of Technology; Reichman University
摘要：Submodular maximization generalizes many fundamental problems in discrete optimization, including Max-Cut in directed/undirected graphs, maximum coverage, maximum facility location, and marketing over social networks. In this paper we consider the problem of maximizing any submodular function subject to d knapsack constraints, where d is a fixed constant. We establish a strong relation between the discrete problem and its continuous relaxation, obtained through extension by expectation of the ...
作者：d'Aspremont, Alexandre; El Karoui, Noureddine
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; University of California System; University of California Berkeley
摘要：We study a weaker formulation of the nullspace property which guarantees recovery of sparse signals from linear measurements by l(1) minimization We require this condition to hold only with high probability, given a distribution on the nullspace of the coding matrix A. Under some assumptions on the distribution of the reconstruction error, we show that testing these weak conditions means bounding the optimal value of two classical graph partitioning problems: the k-Dense-Subgraph and MaxCut pr...
