Random sampling and greedy sparsification for matroid optimization problems

DOI10.1007/BF01585865zbMath0919.90128OpenAlexW2068796193MaRDI QIDQ1290633

David R. Karger

Publication date: 3 June 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585865

zbMATH Keywords

combinatorial optimizationgreedy algorithmrandom samplingminimum spanning treesnetwork reliabilityminimum cutsmatroid partitioningmatroid basis

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees, Constant-competitiveness for random assignment matroid secretary without knowing the matroid, Competitive weighted matching in transversal matroids, Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback

Cites Work

• The multi-tree approach to reliability in distributed networks
• Forests, frames, and games: Algorithms for matroid sums and applications
• Separating from the dominant of the spanning tree polytope
• Connectivity and edge-disjoint spanning trees
• A matroid approach to finding edge connectivity and packing arborescences
• A randomized linear-time algorithm for finding minimum spanning trees
• Random sampling in cut, flow, and network design problems
• Extensions of Mappings into n-Cubes
• Edge-Disjoint Spanning Trees of Finite Graphs
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Matroid Applications and Algorithms
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• Expected time bounds for selection
• A randomized linear-time algorithm to find minimum spanning trees
• A new approach to the minimum cut problem
• On the Abstract Properties of Linear Dependence
• Packing Spanning Trees
• Minimum partition of a matroid into independent subsets
• Matroids and the greedy algorithm
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item