Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
From MaRDI portal
Publication:2191293
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
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