Fast approximation of matroid packing and covering

DOI10.1007/s10479-018-2756-8zbMath1434.68675OpenAlexW2790423763MaRDI QIDQ1730564

Jérôme Galtier

Publication date: 6 March 2019

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-018-2756-8

zbMATH Keywords

approximation algorithmmatroidjob schedulingKruskal algorithmmultiplicative-weights-update methodstrength and arboricity of graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25)

Related Items (1)

Computing Weighted Strength and Applications to Partitioning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast approximation for computing the fractional arboricity and extraction of communities of a graph
• Games induced by the partitioning of a graph
• Submodular functions and optimization.
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• A quick method for finding shortest pairs of disjoint paths
• A linear programming approach to increasing the weight of all minimum spanning trees
• Optimal attack and reinforcement of a network
• Computing Weighted Strength and Applications to Partitioning
• Fibonacci heaps and their uses in improved network optimization algorithms
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Minimum cuts in near-linear time
• Minimum partition of a matroid into independent subsets
• A Characterization of Union of Linearly Independent Sets

This page was built for publication: Fast approximation of matroid packing and covering