k-submodular maximization with two kinds of constraints

DOI10.1142/S1793830921500361MaRDI QIDQ5013487zbMATH OpenOpenAlexFDO

Authors Ganquan Shi, Shuyang Gu, Weili Wu

Publication date 30 November 2021

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830921500361

zbMATH Keywords

\(k\)-submodular maximizationdecreasing thresholdsize constraint

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints
• Improved approximation algorithms for \(k\)-submodular function maximization
• Maximizing bisubmodular and \(k\)-submodular functions
• Maximizing k-submodular functions and beyond

Cites work

• A threshold of ln n for approximating set cover
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An Exact Algorithm for Maximum Entropy Sampling
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Automata, Languages and Programming
• Combinatorial auctions with decreasing marginal utilities
• Derandomization for k-submodular maximization
• Deterministic Algorithms for Submodular Maximization Problems
• Fast algorithms for maximizing submodular functions
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• Improved approximation algorithms for \(k\)-submodular function maximization
• Improved randomized algorithm for k-submodular function maximization
• Maximizing k-submodular functions and beyond
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing Non-monotone Submodular Functions
• Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
• Towards minimizing k-submodular functions

Cited in

(15)

• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• An exact cutting plane method for k-submodular function maximization
• A constrained two-stage submodular maximization
• Constrained submodular maximization via greedy local search
• Group fairness in non-monotone submodular maximization
• On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints
• On \(k\)-submodular relaxation
• Improved approximation algorithms for \(k\)-submodular function maximization
• Maximizing k-submodular functions and beyond
• Maximizing bisubmodular and \(k\)-submodular functions
• A two-stage constrained submodular maximization
• Random approximation algorithms for monotone \(k\)-submodular function maximization with size constraints
• Fast algorithms combining threshold-decreasing and greedy methods for maximizing constraint k-submodular functions
• Maximizing a k-submodular function with p-system constraints
• Approximation algorithms for k-submodular maximization subject to a knapsack constraint

This page was built for publication: \(k\)-submodular maximization with two kinds of constraints

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