Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints

DOI10.4230/LIPICS.APPROX/RANDOM.2021.14OpenAlexW3200835831MaRDI QIDQ6090886FDOQ6090886

Authors: Chien-Chung Huang 

Publication date: 20 November 2023

Full work available at URL: https://hal.science/hal-03594161

Recommendations

• Streaming algorithms for submodular function maximization
• A survey on streaming algorithms for maximizing submodular functions
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Multi-pass streaming algorithms for monotone submodular function maximization
• Semi-streaming algorithms for submodular matroid intersection
• Semi-streaming algorithms for submodular matroid intersection

zbMATH Keywords

matroidmaximum weight matchingstreamingsubmodular function maximization

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (5)

• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Semi-streaming algorithms for submodular function maximization under \(b\)-matching, matroid, and matchoid constraints
• Semi-streaming algorithms for submodular matroid intersection
• Semi-streaming algorithms for submodular matroid intersection
• Linear programming in the semi-streaming model with application to the maximum matching problem

This page was built for publication: Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints

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