Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint

DOI10.1007/s11590-019-01430-zzbMath1445.90094WikidataQ127913651 ScholiaQ127913651MaRDI QIDQ2191293

Yishui Wang, Ruiqi Yang, Yong Zhang, Yanjun Jiang, Da-Chuan Xu

Publication date: 24 June 2020

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

Full work available at URL: https://doi.org/10.1007/s11590-019-01430-z

zbMATH Keywords

streaming; non-submodular; \(d\)-knapsack constraint

Mathematics Subject Classification ID

90C27: Combinatorial optimization

Related Items

Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint, Sequence submodular maximization meets streaming, Fast algorithms for maximizing monotone nonsubmodular functions, Streaming submodular maximization with the chance constraint, Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice, Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice, On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice

Cites Work

• Unnamed Item
• Maximizing a class of submodular utility functions
• The ellipsoid method and its consequences in combinatorial optimization
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• A note on maximizing a submodular set function subject to a knapsack constraint
• Approximating the least core value and least core of cooperative games with supermodular costs
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• An analysis of approximations for maximizing submodular set functions—I