Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
From MaRDI portal
Publication:5494928
DOI10.1137/130920277zbMath1307.68098OpenAlexW2049451257MaRDI QIDQ5494928
Publication date: 30 July 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/65020/1/WRAP_Ward_1271053-cs-091214-fw-sicomp14.pdf
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (29)
Siting renewable power generation assets with combinatorial optimisation ⋮ Streaming Algorithms for Submodular Function Maximization ⋮ Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ An Improved Analysis of Local Search for Max-Sum Diversification ⋮ Matroid-constrained vertex cover ⋮ Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The multi-budget maximum weighted coverage problem ⋮ Greedy guarantees for non-submodular function maximization under independent system constraint with applications ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ Practical budgeted submodular maximization ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint ⋮ On maximizing a monotone \(k\)-submodular function subject to a matroid constraint ⋮ Evaluation of Combinatorial Optimisation Algorithms for c-Optimal Experimental Designs with Correlated Observations ⋮ Non-monotone submodular function maximization under \(k\)-system constraint ⋮ Unnamed Item ⋮ Non-submodular streaming maximization with minimum memory and low adaptive complexity ⋮ Unnamed Item ⋮ Online submodular maximization: beating 1/2 made simple ⋮ Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Generalized budgeted submodular set function maximization ⋮ Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
This page was built for publication: Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
