A TIGHT LINEAR TIME (1/2)-APPROXIMATION FOR UNCONSTRAINED SUBMODULAR MAXIMIZATION

被引：144

作者：

Buchbinder, Niv ^{[1
]}

Feldman, Moran ^{[2
]}

Naor, Joseph

Schwartz, Roy ^{[3
]}

机构：

[1] Tel Aviv Univ, Stat & Operat Res Dept, IL-69978 Tel Aviv, Israel

[2] Ecole Polytech Fed Lausanne, Sch Comp & Commun Sci, CH-1015 Lausanne, Switzerland

[3] Princeton Univ, Dept Comp Sci, Princeton, NJ 08540 USA

来源：

SIAM JOURNAL ON COMPUTING | 2015年 / 44卷 / 05期

关键词：

submodular functions; approximation algorithms; linear time; APPROXIMATION ALGORITHMS; CUT; MINIMIZATION; LOCATION;

D O I：

10.1137/130929205

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the Unconstrained Submodular Maximization problem in which we are given a nonnegative submodular function f : 2(N) -> R+, and the objective is to find a subset S subset of 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 Vondrak [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

共 40 条

[1] An 0.828-approximation algorithm for the uncapacitated facility location problem [J].

Ageev, AA ;

Sviridenko, MI .

DISCRETE APPLIED MATHEMATICS, 1999, 93 (2-3) :149-156

[2] Maximizing a class of submodular utility functions [J].

Ahmed, Shabbir ;

Atamtuerk, Alper .

MATHEMATICAL PROGRAMMING, 2011, 128 (1-2) :149-169

[3]

[Anonymous], 1999, MAXIMIZATION SUBMODU

[4]

Buchbinder N., 2014, P 25 ANN ACM SIAM S, P1433, DOI DOI 10.1137/1.9781611973402.106

[5] MAXIMIZING A MONOTONE SUBMODULAR FUNCTION SUBJECT TO A MATROID CONSTRAINT [J].

Calinescu, Gruia ;

Chekuri, Chandra ;

Pal, Martin ;

Vondrak, Jan .

SIAM JOURNAL ON COMPUTING, 2011, 40 (06) :1740-1766

[6]

Chekuri C, 2011, ACM S THEORY COMPUT, P783

[7] Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures [J].

Chekuri, Chandra ;

Vondrak, Jan ;

Zenklusen, Rico .

2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2010, :575-584

[8]

CHERENIN V, 1962, P C EXP PERSP APPL M

[9] LOCATION OF BANK ACCOUNTS TO OPTIMIZE FLOAT - ANALYTIC STUDY OF EXACT AND APPROXIMATE ALGORITHMS [J].

CORNUEJOLS, G ;

FISHER, ML ;

NEMHAUSER, GL .

MANAGEMENT SCIENCE, 1977, 23 (08) :789-810

[10]

Cornuejols G., 1977, Annals of Discrete Mathematics, V1, P163, DOI [DOI 10.1016/S0167-5060(08)70732-5, 10.1016/S0167-5060(08)70732-5]

← 1 2 3 4 →