An analysis of approximations for maximizing submodular set functions—I

Cites Work

Cores of convex games
Title not available (Why is that?)
Matroids and the greedy algorithm
A cost function property for plant location problems
Comments on the note of Frieze
Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

On the approximability of the link building problem
An exact solution framework for the multiple gradual cover location problem
Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems
Polymatroids and mean-risk minimization in discrete optimization
A Fast and Scalable Computational Framework for Large-Scale High-Dimensional Bayesian Optimal Experimental Design
Micro- and macromodels of social networks. I: Theory fundamentals
Roof duality, complementation and persistency in quadratic 0–1 optimization
A PTAS for the minimization of polynomials of fixed degree over the simplex
Discriminative models for multi-class object layout
A Canonical Representation of Simple Plant Location Problems and Its Applications
On the supermodular knapsack problem
Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization
Pseudo-Boolean optimization
Clustering on trees
Simultaneous pursuit of out-of-sample performance and sparsity in index tracking portfolios
Is submodularity testable?
Pareto optimization for subset selection with dynamic cost constraints
An approximation algorithm for maximum weight budgeted connected set cover
Submodular functions: learnability, structure, and optimization
Maximizing a non-decreasing non-submodular function subject to various types of constraints
An individual-based model of information diffusion combining friends' influence
Directed submodularity, ditroids and directed submodular flows
A note on maximizing a submodular set function subject to a knapsack constraint
Approximation algorithms for maximum weight k-coverings of graphs by packings
Exact hypervolume subset selection through incremental computations
Polynomial time approximation scheme for \(t\)-latency bounded information propagation problem in wireless networks
Locating service facilities whose reliability is distance dependent.
Thresholded covering algorithms for robust and max-min optimization
Structure preserving reductions among convex optimization problems
Minimization of ordered, symmetric half-products
Fixed points approach to clustering
The expressive power of binary submodular functions
Idempotent expansions for continuous-time stochastic control
Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs
On an approximation measure founded on the links between optimization and polynomial approximation theory
An analysis of the greedy algorithm for the submodular set covering problem
Sensor placement for fault location identification in water networks: a minimum test cover approach
Multi-level facility location as the maximization of a submodular set function
Election control through social influence with voters' uncertainty
The component commonality problem in a real multidimensional space: an algorithmic approach
Improved approximation algorithms for capacitated facility location problems
Fast approximate energy minimization with label costs
The multi-level uncapacitated facility location problem is not submodular
A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints
The maximum vertex coverage problem on bipartite graphs
Edge deletion algorithms for minimizing spread in SIR epidemic models
Solving the uncapacitated facility location problem using tabu search
Finding a collective set of items: from proportional multirepresentation to group recommendation
Optimal interval scheduling with a resource constraint
Maximizing influence in competitive environments: a game-theoretic approach
Maximization of submodular functions: theory and enumeration algorithms
Computational complexity analysis of the sensor location flow observability problem
On covering location problems on networks with edge demand
A heuristic lagrangean algorithm for the capacitated plant location problem
On a class of functions attaining their maximum at the vertices of a polyhedron
The simple plant location problem: Survey and synthesis
On the Greedy Heuristic for Continuous Covering and Packing Problems
Locating flow-capturing units on a network with multi-counting and diminishing returns to scale
The submodular knapsack polytope
A comparison of two dual-based procedures for solving the p-median problem
Unimodular functions
General asymptotic and submodular results for the Median problem with unreliable facilities
Submodularity and valid inequalities in capacitated fixed charge networks
Hub location as the minimization of a supermodular set function
An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.
A Probabilistic Analysis of the K-Location Problem
Approximation algorithms for dynamic assortment optimization models
Scalable influence maximization for independent cascade model in large-scale social networks
Submodular functions are noise stable
Recent trends in combinatorial optimization
Measuring the impact of MVC attack in large complex networks
Efficient minimization of higher order submodular functions using monotonic Boolean functions
Maximizing a class of submodular utility functions
Assortment optimization over time
Budgeted nature reserve selection with diversity feature loss and arbitrary split systems
Recent developments in discrete convex analysis
Capacitated strategic assortment planning under explicit demand substitution
Submodular spectral functions of principal submatrices of a Hermitian matrix, extensions and applications
Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid
Minimizing the Spread of Rumor Within Budget Constraint in Online Network
General rumor blocking: an efficient random algorithm with martingale approach
Restricted strong convexity implies weak submodularity
A note on solving DiDi's driver-order matching problem
Rumor correction maximization problem in social networks
A Review for Submodular Optimization on Machine Scheduling Problems
Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives
Parametric monotone function maximization with matroid constraints
Influence maximization with deactivation in social networks
Nonnegative definite Hermitian matrices with increasing principal minors
Submodular stochastic probing on matroids
Distributed resource allocation with binary decisions via Newton-like neural network dynamics
A model of anytime algorithm performance for bi-objective optimization
On strict submodularity of social influence
Non-monotone submodular function maximization under \(k\)-system constraint
Discriminative frequent subgraph mining with optimality guarantees
Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
Online submodular welfare maximization: greedy beats 1/2 in random order
Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints

This page was built for publication: An analysis of approximations for maximizing submodular set functions—I

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4152030)