Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

DOI10.1137/20M1357317OpenAlexW4297823791MaRDI QIDQ5028360FDOQ5028360

Authors: Chien-Chung Huang, Naonori Kakimura, Simon Mauras, Yuichi Yoshida 

Publication date: 9 February 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.05477

Recommendations

• A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Multi-pass streaming algorithms for monotone submodular function maximization
• Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Streaming algorithms for submodular function maximization
• Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints

zbMATH Keywords

approximation algorithminapproximabilitysubmodular function maximizationstreaming model

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• A threshold of ln n for approximating set cover
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Title not available (Why is that?)
• Monotone submodular maximization over a matroid via non-oblivious local search
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Maximizing a monotone submodular function subject to a matroid constraint
• An analysis of approximations for maximizing submodular set functions—I
• Fast algorithms for maximizing submodular functions
• Submodular maximization over multiple matroids via generalized exchange properties
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Maximizing submodular set functions subject to multiple linear constraints
• Symmetry and approximability of submodular maximization problems
• Better streaming algorithms for the maximum coverage problem
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Streaming algorithms for submodular function maximization
• Online submodular maximization with free disposal: randomization beats \(\frac{1}{4}\) for partition matroids
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
• Multi-pass streaming algorithms for monotone submodular function maximization
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Online Submodular Maximization Problem with Vector Packing Constraint.
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• The adaptive complexity of maximizing a submodular function
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• Submodular function maximization in parallel via the multilinear relaxation
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Title not available (Why is that?)

Cited In (8)

• Thresholding Methods for Streaming Submodular Maximization with a Cardinality Constraint and Its Variants
• Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
• Semi-streaming algorithms for submodular matroid intersection
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
• On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints
• Multi-pass streaming algorithms for monotone submodular function maximization
• Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint

This page was built for publication: Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

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