Fast approximation of matroid packing and covering

DOI10.1007/S10479-018-2756-8MaRDI QIDQ1730564zbMATH OpenOpenAlexFDO

Authors 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) Approximation algorithms (68W25) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• A Fast Approximation for Maximum Weight Matroid Intersection
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Representative families for matroid intersections, with applications to location, packing, and covering problems
• scientific article; zbMATH DE number 26304

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 910872 (Why is no real title available?)
• A Characterization of Union of Linearly Independent Sets
• A linear programming approach to increasing the weight of all minimum spanning trees
• A quick method for finding shortest pairs of disjoint paths
• Computing weighted strength and applications to partitioning
• Edge-Disjoint Spanning Trees of Finite Graphs
• Fast approximation for computing the fractional arboricity and extraction of communities of a graph
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• Games induced by the partitioning of a graph
• Minimum cuts in near-linear time
• Minimum partition of a matroid into independent subsets
• On the Problem of Decomposing a Graph into n Connected Factors
• Optimal attack and reinforcement of a network
• Submodular functions and optimization.
• The multiplicative weights update method: a meta-algorithm and applications

Cited in

(3)

• Computing weighted strength and applications to partitioning
• Time-expanded packings
• Fast First-Order Algorithms for Packing–Covering Semidefinite Programs

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

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