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
An adaptive algorithm for maximization of non-submodular function with a matroid constraint
Sequence independent lifting for a set of submodular maximization problems
Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems
Submodular function minimization and polarity
Submodularity and local search approaches for maximum capture problems under generalized extreme value models
Exploiting social influence to control elections based on positional scoring rules
Who should get vaccinated? Individualized allocation of vaccines over SIR network
A unifying look at sequence submodularity
Towards nearly-linear time algorithms for submodular maximization with a matroid constraint
Complexity and approximation results for the balance optimization subset selection model for causal inference in observational studies
Kernel-based models for influence maximization on graphs based on Gaussian process variance minimization
Constrained submodular maximization via a nonsymmetric technique
Multi-agent submodular optimization
Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
Deterministic approximation algorithm for submodular maximization subject to a matroid constraint
Optimal intervention in economic networks using influence maximization methods
Maximum coverage with cluster constraints: an LP-based approximation technique
An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
General bounds for incremental maximization

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)