On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint

DOI10.1007/978-3-030-92681-6_7OpenAlexW4205825502MaRDI QIDQ2149857

Yicheng Xu, Xiao-guang Yang, Yi-Jing Wang

Publication date: 29 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92681-6_7

zbMATH Keywords

matroid constraintmassive databicriteria algorithmapproximately submodular

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (1)

Algorithms for maximizing monotone submodular function minus modular function under noise

Cites Work

• Unnamed Item
• Simultaneous approximation of multi-criteria submodular function maximization
• Optimization, approximation, and complexity classes
• A simple greedy algorithm for the profit-aware social team formation problem
• Parametric monotone function maximization with matroid constraints
• Combinatorial auctions with decreasing marginal utilities
• A threshold of ln n for approximating set cover
• Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Guess free maximization of submodular and linear sums

This page was built for publication: On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint