An analysis of approximations for maximizing submodular set functions—I
From MaRDI portal
Publication:4152030
DOI10.1007/BF01588971zbMath0374.90045WikidataQ56814664 ScholiaQ56814664MaRDI QIDQ4152030
Marshall L. Fisher, Laurence A. Wolsey, Nemhauser, George I.
Publication date: 1978
Published in: Mathematical Programming (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
Joint location and cost planning in maximum capture facility location under random utilities ⋮ A new perspective on low-rank optimization ⋮ Universal Algorithms for Clustering Problems ⋮ Uncertainty in Study of Social Networks: Robust Optimization and Machine Learning ⋮ Online conflict resolution: algorithm design and analysis ⋮ A greedy Galerkin method to efficiently select sensors for linear dynamical systems ⋮ A survey on bilevel optimization under uncertainty ⋮ An exact method for influence maximization based on deterministic linear threshold model ⋮ A Fast and Scalable Computational Framework for Large-Scale High-Dimensional Bayesian Optimal Experimental Design ⋮ Justifying groups in multiwinner approval voting ⋮ Maximization of nonsubmodular functions under multiple constraints with applications ⋮ Distributed strategy selection: a submodular set function maximization approach ⋮ Two-stage non-submodular maximization ⋮ Robust maximum capture facility location under random utility maximization models ⋮ Two-stage BP maximization under \(p\)-matroid constraint ⋮ A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity ⋮ Opinion influence maximization problem in online social networks based on group polarization effect ⋮ Two-stage non-submodular maximization ⋮ Maximizing the influence with \(\kappa\)-grouping constraint ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Unified Greedy Approximability beyond Submodular Maximization ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ Justifying groups in multiwinner approval voting ⋮ Constraint generation approaches for submodular function maximization leveraging graph properties ⋮ Efficient processing of \(k\)-regret minimization queries with theoretical guarantees ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions ⋮ Supermodularity and valid inequalities for quadratic optimization with indicators ⋮ Streaming submodular maximization with the chance constraint ⋮ Unified greedy approximability beyond submodular maximization ⋮ Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint ⋮ The follower competitive facility location problem under the nested logit choice rule ⋮ Two generalizations of proper coloring: hardness and approximability ⋮ Two-stage BP maximization under \(p\)-matroid constraint ⋮ Efficient algorithms for finding diversified top-\(k\) structural hole spanners in social networks ⋮ IM2Vec: representation learning-based preference maximization in geo-social networks ⋮ An exact solution approach for the mobile multi‐agent sensing problem ⋮ Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint ⋮ Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows ⋮ Average submodularity of maximizing anticoordination in network games ⋮ Stochastic Variance Reduction for DR-Submodular Maximization ⋮ Satisfaction-aware task assignment in spatial crowdsourcing ⋮ Differentially private submodular maximization with a cardinality constraint over the integer lattice ⋮ Adaptivity gap for influence maximization with linear threshold model on trees ⋮ Regularized nonmonotone submodular maximization ⋮ Cost intervention in delinquent networks ⋮ Finding the optimal exploration-exploitation trade-off online through Bayesian risk estimation and minimization ⋮ Adaptive algorithms on maximizing monotone nonsubmodular functions ⋮ Fast deterministic algorithms for non-submodular maximization with strong performance guarantees ⋮ Fast parallel algorithms for submodular \(p\)-superseparable maximization ⋮ Model change active learning in graph-based semi-supervised learning ⋮ On the reachability and controllability of temporal continuous-time linear networks: a generic analysis ⋮ Resistance distances in directed graphs: definitions, properties, and applications ⋮ DR-submodular function maximization with adaptive stepsize ⋮ Stochastic model for rumor blocking problem in social networks under rumor source uncertainty ⋮ Optimal experimental design: formulations and computations ⋮ Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models ⋮ Greedy is good: constrained non-submodular function maximization via weak submodularity ⋮ Maximizing the differences between a monotone DR-submodular function and a linear function on the integer lattice ⋮ Efficient algorithms for \(k\)-submodular function maximization with \(p\)-system and \(d\)-knapsack constraint ⋮ \textsc{Greedy+Max}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization ⋮ Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions ⋮ Two-stage submodular maximization problem beyond nonnegative and monotone ⋮ Maximizing stochastic set function under a matroid constraint from decomposition ⋮ Runtime analysis of quality diversity algorithms ⋮ Budget-constrained profit maximization without non-negative objective assumption in social networks ⋮ Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints ⋮ Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables ⋮ Weak submodularity implies localizability: local search for constrained non-submodular function maximization ⋮ Efficient algorithm for stochastic rumor blocking problem in social networks during safety accident period ⋮ Core potentials: the consensus segmentation conjecture ⋮ Randomized greedy methods for weak submodular sensor selection with robustness considerations ⋮ Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back ⋮ Computing paths of large rank in planar frameworks deterministically ⋮ Deals or No Deals: Contract Design for Online Advertising ⋮ Principal points analysis via p-median problem for binary data ⋮ A Canonical Representation of Simple Plant Location Problems and Its Applications ⋮ Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems ⋮ An Offline-Online Decomposition Method for Efficient Linear Bayesian Goal-Oriented Optimal Experimental Design: Application to Optimal Sensor Placement ⋮ Submodular Maximization Subject to a Knapsack Constraint Under Noise Models ⋮ Tight Approximation Bounds for Maximum Multi-coverage ⋮ Hardness Results for Seeding Complex Contagion with Neighborhoods ⋮ Controllability Metrics on Networks with Linear Decision Process--type Interactions and Multiplicative Noise ⋮ A Branch-and-Cut Algorithm for Submodular Interdiction Games ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ A tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimization ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Improving the Betweenness Centrality of a Node by Adding Links ⋮ Edge Deletion Algorithms for Minimizing Spread in SIR Epidemic Models ⋮ Adaptive Test Allocation for Outbreak Detection and Tracking in Social Contact Networks ⋮ Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes ⋮ Multiobjective Tree-Structured Parzen Estimator ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Unnamed Item ⋮ Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order ⋮ Structured Robust Submodular Maximization: Offline and Online Algorithms ⋮ The Power of Subsampling in Submodular Maximization ⋮ Toward Robust Monitoring of Malicious Outbreaks
Cites Work
This page was built for publication: An analysis of approximations for maximizing submodular set functions—I
