NDLI: Symmetry and Approximability of Submodular Maximization Problems

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Vondrák, Jan
Copyright Year	2013
Abstract	A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box returning $f(S)$ for a given $S$. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of symmetry gap. Our main result is that for any fixed instance that exhibits a certain symmetry gap in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, e.g., the optimality of $(1-1/e)$-approximation for monotone submodular maximization under a cardinality constraint and the impossibility of $(\frac12+\epsilon)$-approximation for unconstrained (nonmonotone) submodular maximization. As a new application, we consider the problem of maximizing a nonmonotone submodular function over the bases of a matroid. A $(\frac16-o(1))$-approximation has been developed for this problem, assuming that the matroid contains two disjoint bases. We show that the best approximation one can achieve is indeed related to packings of bases in the matroid. Specifically, for any $k \geq 2$, there is a class of matroids of fractional base packing number $\nu = \frac{k}{k-1}$ such that any algorithm achieving a better than $(1-\frac{1}{\nu}) = \frac{1}{k}$-approximation for this class would require exponentially many value queries. In particular, there is no constant factor approximation for maximizing a nonmonotone submodular function over the bases of a general matroid. On the positive side, we present a $\frac12 (1-\frac{1}{\nu}-o(1))$-approximation algorithm assuming fractional base packing number at least $\nu$, where $\nu \in (1,2]$. We also present an improved $0.309$-approximation for maximization of a nonmonotone submodular function subject to a matroid independence constraint, improving the previously known factor of $\frac14-\epsilon$. For this problem, we obtain a hardness of $(\frac12 + \epsilon)$-approximation for any fixed $\epsilon>0$.
Starting Page	265
Ending Page	304
Page Count	40
File Format	PDF
ISSN	00975397
DOI	10.1137/110832318
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1
Volume Number	42
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2013-01-29
Access Restriction	Subscribed
Subject Keyword	Nonnumerical algorithms query complexity Randomized algorithms Approximation algorithms approximation algorithms submodular functions
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Symmetry and Approximability of Submodular Maximization Problems

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

Symmetry and approximability of submodular maximization problems

Constrained Submodular Maximization via New Bounds for DR-Submodular Functions

Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

Unified greedy approximability beyond submodular maximization

Symmetry and approximability of submodular maximization problems.

Symmetry and approximability of submodular maximization problems (2011)

Symmetry and Approximability of Submodular Maximization Problems

Similar Documents

Symmetry and Approximability of Submodular Maximization Problems

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

Symmetry and approximability of submodular maximization problems

Constrained Submodular Maximization via New Bounds for DR-Submodular Functions

Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

Unified greedy approximability beyond submodular maximization

Symmetry and approximability of submodular maximization problems.

Symmetry and approximability of submodular maximization problems (2011)

Symmetry and Approximability of Submodular Maximization Problems