On maximizing a monotone \(k\)-submodular function subject to a matroid constraint

DOI10.1016/J.DISOPT.2017.01.003zbMath1387.90226arXiv1607.07957OpenAlexW2491571354MaRDI QIDQ1751212

Shinsaku Sakaue

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

greedy algorithmmatroid constraint\(k\)-submodular function

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27) Oriented matroids in discrete geometry (52C40)

Related Items (12)

Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints ⋮ Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms ⋮ On maximizing a monotone \(k\)-submodular function under a knapsack constraint ⋮ Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint ⋮ 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 ⋮ \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ An exact cutting plane method for \(k\)-submodular function maximization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on maximizing a submodular set function subject to a knapsack constraint
• On $k$-Submodular Relaxation
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• Towards Minimizing k-Submodular Functions
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• An analysis of approximations for maximizing submodular set functions—I
• Improved Approximation Algorithms for k-Submodular Function Maximization
• An Exact Algorithm for Maximum Entropy Sampling
• Maximizing k -Submodular Functions and Beyond
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: On maximizing a monotone \(k\)-submodular function subject to a matroid constraint