Efficient Submodular Function Maximization under Linear Packing Constraints

DOI10.1007/978-3-642-31594-7_4zbMATH Open1272.90063arXiv1007.3604OpenAlexW1930571140MaRDI QIDQ2843232FDOQ2843232

Yossi Azar, Iftah Gamzu

Publication date: 12 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: We study the problem of maximizing a monotone submodular set function subject to linear packing constraints. An instance of this problem consists of a matrix $Ain[0,1{]}^{mimesn}$, a vector $bin[1,infty{)}^m$, and a monotone submodular set function $$. The objective is to find a set $S$ that maximizes $f(S)$ subject to $A{x}_{S}leqb$, where $x_S$ stands for the characteristic vector of the set $S$. A well-studied special case of this problem is when $f$ is linear. This special case captures the class of packing integer programs. Our main contribution is an efficient combinatorial algorithm that achieves an approximation ratio of $Omega(1/m^{1/W})$, where $W=min{b}_i/A_{ij}:A_{ij}>0$ is the width of the packing constraints. This result matches the best known performance guarantee for the linear case. One immediate corollary of this result is that the algorithm under consideration achieves constant factor approximation when the number of constraints is constant or when the width of the constraints is sufficiently large. This motivates us to study the large width setting, trying to determine its exact approximability. We develop an algorithm that has an approximation ratio of $(1-epsilon)(1-1/e)$ when $W=Omega(lnm/epsilo{n}^2)$. This result essentially matches the theoretical lower bound of $1-1/e$. We also study the special setting in which the matrix $A$ is binary and $k$-column sparse. A $k$-column sparse matrix has at most $k$ non-zero entries in each of its column. We design a fast combinatorial algorithm that achieves an approximation ratio of $Omega(1/(W{k}^{1/W}))$, that is, its performance guarantee only depends on the sparsity and width parameters.

Full work available at URL: https://arxiv.org/abs/1007.3604

Recommendations

• A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
• Submodular Maximization Through the Lens of Linear Programming
• Submodular maximization with matroid and packing constraints in parallel
• Maximizing submodular set functions subject to multiple linear constraints
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Fast algorithms for maximizing submodular functions
• Submodular functions: optimization and approximation
• Maximizing \(k\)-submodular functions and beyond

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (7)

• Improved deterministic algorithms for non-monotone submodular maximization
• Online Submodular Maximization Problem with Vector Packing Constraint.
• Costly circuits, submodular schedules and approximate Carathéodory theorems
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Title not available (Why is that?)
• Submodular Maximization Through the Lens of Linear Programming
• Algorithms for influence maximization in socio-physical networks

This page was built for publication: Efficient Submodular Function Maximization under Linear Packing Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843232)