Random sampling and greedy sparsification for matroid optimization problems

DOI10.1007/BF01585865zbMATH Open0919.90128OpenAlexW2068796193MaRDI QIDQ1290633FDOQ1290633

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

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

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)

Cites Work

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

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)