A (k+3)2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems

DOI10.4230/LIPICS.STACS.2012.42MaRDI QIDQ2904748zbMATH OpenFDO

Authors Justin Ward

Publication date 23 August 2012

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

zbMATH Keywords

\(k\)-exchange systems\(k\)-set packingapproximation algorithmslocal searchsubmodular maximization

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Improved approximations for k-exchange systems (extended abstract)
• Submodular maximization over multiple matroids via generalized exchange properties
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• Monotone submodular maximization over a matroid via non-oblivious local search
• Non-monotone submodular function maximization under k-system constraint

Cited in

(11)

• On the intersection of independence systems
• Generalized budgeted submodular set function maximization
• An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
• Informative path planning as a maximum traveling salesman problem with submodular rewards
• The multi-budget maximum weighted coverage problem
• Practical budgeted submodular maximization
• Improved approximations for k-exchange systems (extended abstract)
• Generalized budgeted submodular set function maximization
• The power of subsampling in submodular maximization
• Submodular Maximization Through the Lens of Linear Programming
• Weak submodularity implies localizability: local search for constrained non-submodular function maximization

This page was built for publication: A \(\frac{(k+3)}{2}\)-approximation algorithm for monotone submodular \(k\)-set packing and general \(k\)-exchange systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904748)