Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems

From MaRDI portal
Publication:3964292

DOI10.1287/moor.7.3.410zbMath0498.90024OpenAlexW2053853578MaRDI QIDQ3964292

Laurence A. Wolsey

Publication date: 1982

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.7.3.410




Related Items (49)

Submodular Maximization Subject to a Knapsack Constraint Under Noise ModelsDual domination problems in graphsMaximization of monotone non-submodular functions with a knapsack constraint over the integer latticeStreaming algorithms for maximizing DR-submodular functions with \(d\)-knapsack constraintsA new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problemsDirected submodularity, ditroids and directed submodular flowsMaximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithmsHub Location as the Minimization of a Supermodular Set FunctionSubmodularity and valid inequalities in capacitated fixed charge networksMaximizing set function formulation of two scheduling problemsCompetitive facility location and design problemDecision trees for function evaluation: simultaneous optimization of worst and expected costFast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack ConstraintOn maximizing a monotone \(k\)-submodular function under a knapsack constraintDiscrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. OfflineA fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer latticeFPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage ObjectiveStreaming submodular maximization under \(d\)-knapsack constraintsOn streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer latticeSubmodular optimization problems and greedy strategies: a surveyEnergy-constrained geometric coverage problem\textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximizationA simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraintScenario Submodular CoverPractical budgeted submodular maximizationMaximize a monotone function with a generic submodularity ratioA note on maximizing a submodular set function subject to a knapsack constraintCut problems in graphs with a budget constraintUnnamed ItemStreaming algorithms for maximizing monotone submodular functions under a knapsack constraintA continuous knapsack problem with separable convex utilities: approximation algorithms and applicationsMaximizing expected utility over a knapsack constraintConstrained submodular maximization via greedy local searchStreaming algorithms for maximizing monotone submodular functions under a knapsack constraintImproved streaming algorithms for maximizing monotone submodular functions under a knapsack constraintA Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack ConstraintA Tight Approximation for Submodular Maximization with Mixed Packing and Covering ConstraintsMulti-pass streaming algorithms for monotone submodular function maximizationWorst-case analysis of the greedy algorithm for a generalization of the maximum \(p\)-facility location problemThe simple plant location problem: Survey and synthesisAn analysis of the greedy algorithm for the submodular set covering problemPolynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget ConstraintsA note on submodular set cover on matroidsBeyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraintsStreaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer latticeBudget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and OnlineNon-Submodular Maximization with Matroid and Knapsack ConstraintsApproximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming ModelPacking under convex quadratic constraints




This page was built for publication: Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems