Semi-streaming algorithms for submodular matroid intersection

DOI10.1007/978-3-030-73879-2_15zbMath1490.90245arXiv2102.04348OpenAlexW3164887293MaRDI QIDQ5918428

Paritosh Garg, Ola Svensson, Linus Jordan

Publication date: 21 December 2021

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmmatroid intersectionlocal ratiosemi-streaming algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items

FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective, Semi-streaming algorithms for submodular matroid intersection

Cites Work

• Submodular maximization meets streaming: matchings, matroids, and more
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On graph problems in a semi-streaming model
• Matroid Intersection
• A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Semi-streaming algorithms for submodular matroid intersection
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item