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

DOI10.1007/s10878-022-00975-7OpenAlexW4313325319MaRDI QIDQ2677650

Weili Wu, Zihan Chen, Bin Liu, Hui-Juan 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

integer latticecardinality constraintstreaming algorithmnon-submodular maximization

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• Maximizing monotone submodular functions over the integer lattice
• A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
• Non-submodular maximization on massive data streams
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice
• The adaptive complexity of maximizing a submodular function
• 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
• Online Submodular Maximization with Preemption
• Fast algorithms for maximizing submodular functions
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Maximize a monotone function with a generic submodularity ratio

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