Constrained non-monotone submodular maximization: Offline and secretary algorithms

Anupam Gupta, Aaron Roth, Grant Schoenebeck, Kunal Talwar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Constrained submodular maximization problems have long been studied, most recently in the context of auctions and computational advertising, with near-optimal results known under a variety of constraints when the submodular function is monotone. In this paper, we give constant approximation algorithms for the non-monotone case that work for p-independence systems (which generalize constraints given by the intersection of p matroids that had been studied previously), where the running time is . Our algorithms and analyses are simple, and essentially reduce non-monotone maximization to multiple runs of the greedy algorithm previously used in the monotone case. We extend these ideas to give a simple greedy-based constant factor algorithms for non-monotone submodular maximization subject to a knapsack constraint, and for (online) secretary setting (where elements arrive one at a time in random order and the algorithm must make irrevocable decisions) subject to uniform matroid or a partition matroid constraint. Finally, we give an O(logk) approximation in the secretary setting subject to a general matroid constraint of rank k.

Original languageEnglish (US)
Title of host publicationInternet and Network Economics - 6th International Workshop, WINE 2010, Proceedings
Pages246-257
Number of pages12
DOIs
StatePublished - 2010
Event6th International Workshop on Internet and Network Economics, WINE 2010 - Stanford, CA, United States
Duration: Dec 13 2010Dec 17 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6484 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Workshop on Internet and Network Economics, WINE 2010
Country/TerritoryUnited States
CityStanford, CA
Period12/13/1012/17/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Constrained non-monotone submodular maximization: Offline and secretary algorithms'. Together they form a unique fingerprint.

Cite this