Maximizing k -Submodular Functions and Beyond

DOI10.1145/2850419zbMath1445.68371arXiv1409.1399OpenAlexW1771852678MaRDI QIDQ4962626

Justin Ward, Stanislav Živný

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

submodularitybisubmodularity\(k\)-submodularity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (16)

Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints ⋮ On maximizing a monotone \(k\)-submodular function under a knapsack constraint ⋮ Information coverage maximization for multiple products in social networks ⋮ Maximization of \(k\)-submodular function with a matroid constraint ⋮ Maximizing approximately non-\(k\)-submodular monotone set function with matroid constraint ⋮ Weakly \(k\)-submodular maximization under matroid constraint ⋮ Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm ⋮ Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint ⋮ Profit maximization for multiple products in community-based social networks ⋮ \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization ⋮ On maximizing a monotone \(k\)-submodular function subject to a matroid constraint ⋮ On $k$-Submodular Relaxation ⋮ An exact cutting plane method for \(k\)-submodular function maximization ⋮ Improved Randomized Algorithm for k-Submodular Function Maximization ⋮ k-Submodular maximization with two kinds of constraints ⋮ Parametric bisubmodular function minimization and its associated signed ring family

This page was built for publication: Maximizing k -Submodular Functions and Beyond