An analysis of approximations for maximizing submodular set functions—I

Cites work

A cost function property for plant location problems
Comments on the note of Frieze
Cores of convex games
Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
scientific article; zbMATH DE number 3461943 (Why is no real title available?)
scientific article; zbMATH DE number 3313442 (Why is no real title available?)
Matroids and the greedy algorithm

Cited in

(only showing first 100 items - show all)

Maximization of submodular functions: theory and enumeration algorithms
The submodular knapsack polytope
Robust placement of sensors in dynamic water distribution systems
A comparison of two dual-based procedures for solving the p-median problem
A tree search algorithm for the multi-commodity location problem
Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
Unimodular functions
On a class of functions attaining their maximum at the vertices of a polyhedron
Directed submodularity, ditroids and directed submodular flows
Submodularity and valid inequalities in capacitated fixed charge networks
Pick-and-choose heuristics for partial set covering
Submodularity and the traveling salesman problem
Structure preserving reductions among convex optimization problems
A cost operator approach to multistage location-allocation
Locating flow-capturing units on a network with multi-counting and diminishing returns to scale
Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
Fixed points approach to clustering
On an approximation measure founded on the links between optimization and polynomial approximation theory
A fast algorithm for finding matching responses in a survey data table
Clustering on trees
Locating service facilities whose reliability is distance dependent.
A note on maximizing a submodular set function subject to a knapsack constraint
Worst-case analysis of the greedy algorithm for a generalization of the maximum \(p\)-facility location problem
Strong formulations for quadratic optimization with M-matrices and indicator variables
Decision trees for function evaluation: simultaneous optimization of worst and expected cost
On general threshold and general cascade models of social influence
Efficient influence maximization under TSCM: a suitable diffusion model in online social networks
Rough set methods in feature selection via submodular function
A local search approximation algorithm for the uniform capacitated k-facility location problem
Stochastic block-coordinate gradient projection algorithms for submodular maximization
Recommending links through influence maximization
Multi-attribute proportional representation
Exploiting submodularity to quantify near-optimality in multi-agent coverage problems
Top-\(k\) overlapping densest subgraphs
A two-stage stochastic programming approach for influence maximization in social networks
Near-linear time approximation schemes for geometric maximum coverage
Supermodular covering knapsack polytope
On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
An approximation algorithm for a competitive facility location problem with network effects
Multi-level facility location problems
Minimization of ordered, symmetric half-products
Improved approximation algorithms for capacitated facility location problems
Implicit enumeration strategies for the hypervolume subset selection problem
Optimization of stochastic virus detection in contact networks
General asymptotic and submodular results for the Median problem with unreliable facilities
Risk averse submodular utility maximization
Assortment optimization over time
A constructive proof of swap local search worst-case instances for the maximum coverage problem
Robust monotone submodular function maximization
Submodular unsplittable flow on trees
Heuristic methods and applications: A categorized survey
On the supermodular knapsack problem
The simple plant location problem: Survey and synthesis
An analysis of the greedy algorithm for the submodular set covering problem
Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs
Locating flow-intercepting facilities: New approaches and results
Spider covers and their applications
Scalable influence maximization for independent cascade model in large-scale social networks
Online budgeted maximum coverage
On greedy heuristics for computing D-efficient saturated subsets
New solution approaches for the maximum-reliability stochastic network interdiction problem
Restricted strong convexity implies weak submodularity
A note on solving DiDi's driver-order matching problem
Rumor correction maximization problem in social networks
Measures minimizing regularized dispersion
An exact solution framework for the multiple gradual cover location problem
Parametric monotone function maximization with matroid constraints
Nonnegative definite Hermitian matrices with increasing principal minors
Election control through social influence with unknown preferences
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
Large-scale influence maximization via maximal covering location
Non-submodular streaming maximization with minimum memory and low adaptive complexity
Search complexity: a way for the quantitative analysis of the search space
Functional pearl: the distributive \(\lambda\)-calculus
Real-time solving of computationally hard problems using optimal algorithm portfolios
Utilitarian welfare and representation guarantees of approval-based multiwinner rules
Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
Generalized budgeted submodular set function maximization
Attribute based diversification of seeds for targeted influence maximization
Parallel Gaussian process surrogate Bayesian inference with noisy likelihood evaluations
A refined analysis of submodular greedy
Pareto optimization for subset selection with dynamic cost constraints
An exact cutting plane method for k-submodular function maximization
Multi-pass streaming algorithms for monotone submodular function maximization
Adaptive influence maximization under fixed observation time-step
Permutatorial optimization via the permutahedron
Data source selection for approximate query
Fractionally subadditive maximization under an incremental knapsack constraint
Motif-role extraction in uncertain graph based on efficient ensembles
Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints
Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
The submodularity of two-stage stochastic maximum-weight independent set problems
An ascending implementation of the Vickrey-Clarke-Groves mechanism for the licensed shared access
Private non-monotone submodular maximization
Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy
Algorithms for influence maximization in socio-physical networks
An adaptive algorithm for maximization of non-submodular function with a matroid constraint

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)