Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice

DOI10.1007/978-3-030-92681-6_29OpenAlexW4206238481MaRDI QIDQ2150564

Yang Zhou, Fengmin Wang, Jingjing Tan, Xiao-Qing Zhang

Publication date: 29 June 2022

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

zbMATH Keywords

integer latticeknapsack constraintstreaming algorithmnon-submodular

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular maximization meets streaming: matchings, matroids, and more
• A note on maximizing a submodular set function subject to a knapsack constraint
• Maximizing monotone submodular functions over the integer lattice
• Parametric monotone function maximization with matroid constraints
• Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
• Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
• Non-submodular maximization on massive data streams
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• An analysis of approximations for maximizing submodular set functions—I
• Approximating Robust Parameterized Submodular Function Maximization in Large-Scales
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Submodular Function Maximization in Parallel via the Multilinear Relaxation
• Online Submodular Maximization with Preemption
• Online submodular welfare maximization: Greedy is optimal
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

This page was built for publication: Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice