A tight linear time (1/2)-approximation for unconstrained submodular maximization

Niv Buchbinder, Moran Feldman, Joseph Seffi Naor, Roy Schwartz

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


We consider the Unconstrained Submodular Maximization problem in which we are given a nonnegative submodular function f : 2N → R+, and the objective is to find a subset S ⊆ N maximizing f(S). This is one of the most basic submodular optimization problems, having a wide range of applications. Some well-known problems captured by Unconstrained Submodular Maximization include Max-Cut, Max-DiCut, and variants of Max-SAT and maximum facility location. We present a simple randomized linear time algorithm achieving a tight approximation guarantee of 1/2, thus matching the known hardness result of Feige, Mirrokni, and Vondrák [SIAM J. Comput., 40 (2011), pp. 1133-1153]. Our algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem.

שפה מקוריתאנגלית
עמודים (מ-עד)1384-1402
מספר עמודים19
כתב עתSIAM Journal on Computing
מספר גיליון5
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2015

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1700???
  • ???subjectarea.asjc.2600.2600???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A tight linear time (1/2)-approximation for unconstrained submodular maximization'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי