An optimal streaming algorithm for non-submodular functions maximization on the integer lattice

DOI10.1007/S10878-022-00975-7MaRDI QIDQ2677650zbMATH OpenOpenAlexFDO

Authors Bin Liu, Zihan Chen, Weili Wu, Huijuan Wang

Publication date 5 January 2023

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-022-00975-7

zbMATH Keywords

cardinality constraintinteger latticenon-submodular maximizationstreaming algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice
• Streaming algorithms for maximizing DR-submodular functions with d-knapsack constraints
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice
• Streaming algorithms for submodular function maximization

Cites work

• A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• An analysis of approximations for maximizing submodular set functions—I
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Fast algorithms for maximizing submodular functions
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Maximize a monotone function with a generic submodularity ratio
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Non-submodular maximization on massive data streams
• Online submodular maximization with preemption
• Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• The adaptive complexity of maximizing a submodular function

Cited in

(10)

• Non-submodular streaming maximization with minimum memory and low adaptive complexity
• Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
• A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
• On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice
• Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice
• Approximation Algorithms for Non-Submodular Optimization Over Sliding Windows
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
• Maximizing the differences between a monotone DR-submodular function and a linear function on the integer lattice
• Greedy algorithm for maximization of semi-monotone non-submodular functions with applications
• Streaming algorithms for non-monotone DR-submodular maximization under a knapsack constraint on the integer lattice

This page was built for publication: An optimal streaming algorithm for non-submodular functions maximization on the integer lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2677650)