Constrained submodular maximization via greedy local search

DOI10.1016/j.orl.2018.11.002zbMath1476.90289arXiv1705.06319OpenAlexW2964343703MaRDI QIDQ2294252

Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai

Publication date: 10 February 2020

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.06319

zbMATH Keywords

matroidknapsacksubmodular functions

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (8)

A multi-pass streaming algorithm for regularized submodular maximization ⋮ On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice ⋮ Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint ⋮ A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ A constrained two-stage submodular maximization ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Non-Submodular Maximization with Matroid and Knapsack Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• On the complexity of approximating \(k\)-set packing
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• A threshold of ln n for approximating set cover
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Fast algorithms for maximizing submodular functions
• A Unified Continuous Greedy Algorithm for Submodular Maximization

This page was built for publication: Constrained submodular maximization via greedy local search