Research map / Learning theory and algorithms / Submodular and game algorithms
Improved Approximation Algorithms for $k$-Submodular Maximization via Multilinear Extension
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a multilinear extension for k-submodular functions and unified Frank-Wolfe-type algorithms for k-submodular maximization with monotone or non-monotone objectives and various constraints.
Problem
Maximizing k-submodular functions (a generalization of submodular maximization) under various constraints, for applications in social networks and machine learning.
Approach
Defines a multilinear extension for k-submodular functions and uses continuous Frank-Wolfe-type frameworks on it, which accommodate monotone or non-monotone objectives and different constraint types.
Experimental setup
Builds on: multilinear extension Frank-Wolfe algorithm
Closest papers by meaning
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.91)
- Deletion-Robust Submodular Maximization with Knapsack Constraints (AAAI 2024 · similarity 0.91)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.91)
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.91)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.91)
- Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.