### Abstract

We consider the problem of maximizing a non-negative submodular set function f: 2^{N} → ℝ_{+} over a ground set N subject to a variety of packing type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular when f may be a non-monotone function. Our algorithms are based on (approximately) solving the multilinear extension F of f [5] over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully in some settings [6, 22, 24, 13, 3], it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize F over an arbitrary down-closed polytope P that has an efficient separation oracle. Previously this was known only for monotone functions [36]. For non-monotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints [24] or a matroid polytope [37,30]. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when f is non-monotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via LP duality we show that a contention resolution scheme for a constraint is related to the correlation gap [1] of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.

Original language | English (US) |
---|---|

Title of host publication | STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing |

Pages | 783-792 |

Number of pages | 10 |

DOIs | |

State | Published - 2011 |

Event | 43rd ACM Symposium on Theory of Computing, STOC'11 - San Jose, CA, United States Duration: Jun 6 2011 → Jun 8 2011 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 43rd ACM Symposium on Theory of Computing, STOC'11 |
---|---|

Country | United States |

City | San Jose, CA |

Period | 6/6/11 → 6/8/11 |

### Keywords

- approximation algorithm
- contention resolution scheme
- independence constraint
- matroid
- submodular function maximization

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'Submodular function maximization via the multilinear relaxation and contention resolution schemes'. Together they form a unique fingerprint.

## Cite this

*STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing*(pp. 783-792). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1993636.1993740