A Refined Analysis of Submodular Greedy

Best algorithms for approximating the maximum of a submodular set function

G. L. Nemhauser and L. A. Wolsey · 1978

Earlier work this paper cites.

An analysis of approximations for maximizing submodular set functions—i

George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher · 1978

Earlier work this paper cites.

Comparison theorems for differential equations

Alex McNabb · 1986

Earlier work this paper cites.

A threshold of ln n for approximating set cover

Uriel Feige · 1998

Earlier work this paper cites.

The budgeted maximum coverage problem

Samir Khuller, Anna Moss, and Joseph Naor · 1999

Earlier work this paper cites.

A note on maximizing a submodular set function subject to a knapsack constraint

Maxim Sviridenko · 2004

Earlier work this paper cites.

Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)

Thomas M. Cover and Joy A. Thomas · 2006

Cited alongside, same era.

Cost-effective outbreak detection in networks

Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance · 2007

Cited alongside, same era.

The generalized maximum coverage problem

Reuven Cohen and Liran Katzir · 2008

Cited alongside, same era.

Multi-document summarization via budgeted maximization of submodular functions

Hui Lin and Jeff Bilmes · 2010

Cited alongside, same era.

Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks

K. Son, H. Kim, Y. Yi, and B. Krishnamachari · 2011

Cited alongside, same era.

Ordinary differential equations and dynamical systems

Thomas C Sideris · 2013

Fast algorithms for maximizing submodular functions

Ashwinkumar Badanidiyuru and Jan Vondrák · 2014

Later among the works it cites.

A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint

Alina Ene and Huy L. Nguyen · 2019

Later among the works it cites.

A (1-e -1 {}^{\mbox{-1}} - ϵ \epsilon )-approximation for the monotone submodular multiple knapsack problem

Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz, and Hadas Shachnai · 2020

Later among the works it cites.

Practical budgeted submodular maximization

Original

Moran Feldman, Zeev Nutov, and Elad Shoham · 2020

Later among the works it cites.

“bring your own greedy”+ max: Near-optimal 1/2-approximations for submodular knapsack

Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin · 2020

Later among the works it cites.