Random sampling and greedy sparsification for matroid optimization problems

DOI10.1007/BF01585865MaRDI QIDQ1290633zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Random sampling in cut, flow, and network design problems
• Random sampling in cut, flow, and network design problems
• Covering minimum spanning trees of random subgraphs
• Covering minimum spanning trees of random subgraphs

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3652272 (Why is no real title available?)
• scientific article; zbMATH DE number 50766 (Why is no real title available?)
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• scientific article; zbMATH DE number 1256719 (Why is no real title available?)
• scientific article; zbMATH DE number 1559539 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1424304 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3026247 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A matroid approach to finding edge connectivity and packing arborescences
• A new approach to the minimum cut problem
• A randomized linear-time algorithm for finding minimum spanning trees (extended abstract)
• A randomized linear-time algorithm to find minimum spanning trees
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Connectivity and edge-disjoint spanning trees
• Edge-Disjoint Spanning Trees of Finite Graphs
• Expected time bounds for selection
• Extensions of Mappings into n-Cubes
• Forests, frames, and games: Algorithms for matroid sums and applications
• Matroid Applications and Algorithms
• Matroids and the greedy algorithm
• Minimum partition of a matroid into independent subsets
• On the Abstract Properties of Linear Dependence
• Packing Spanning Trees
• Random sampling in cut, flow, and network design problems
• Separating from the dominant of the spanning tree polytope
• The multi-tree approach to reliability in distributed networks
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time

Cited in

(5)

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

This page was built for publication: Random sampling and greedy sparsification for matroid optimization problems

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