Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
type: Item
instance of: scholarly article
title: Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
author: Jingjing Tan
author: Fengmin Wang
author: Weina Ye
author: Yang Zhou
author: Xiao-Qing Zhang
published in: Theoretical Computer Science
publication date: 2022-10-24T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7605943
zbMATH Keywords: integer lattice
zbMATH Keywords: non-submodular
zbMATH Keywords: knapsack constraint
zbMATH Keywords: streaming algorithms
MaRDI profile type: Publication
full work available at URL: j.tcs.2022.09.028
OpenAlex ID: W4297372942
cites work: Online Submodular Maximization with Preemption
cites work: An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
cites work: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
cites work: Submodular maximization meets streaming: matchings, matroids, and more
cites work: Submodular Function Maximization in Parallel via the Multilinear Relaxation
cites work: Q4607903
cites work: Q3549682
cites work: Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
cites work: Q3112637
cites work: Parametric monotone function maximization with matroid constraints
cites work: Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
cites work: Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
cites work: Q3096108
cites work: Online submodular welfare maximization: Greedy is optimal
cites work: An analysis of approximations for maximizing submodular set functions—I
cites work: A note on maximizing a submodular set function subject to a knapsack constraint
cites work: ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
cites work: Maximizing monotone submodular functions over the integer lattice
cites work: Q3549686
cites work: Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
cites work: Non-submodular maximization on massive data streams
cites work: Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
DOI: 10.1016/J.TCS.2022.09.028
description: scientific article; zbMATH DE number 7605943