Random sampling in cut, flow, and network design problems

DOI10.1287/MOOR.24.2.383MaRDI QIDQ2757600zbMATH OpenOpenAlexFDO

Authors David R. Karger

Publication date 26 November 2001

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.2225

zbMATH Keywords

networksrandomized algorithmnetwork designsampling theorems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Random sampling in cut, flow, and network design problems
• Randomized approximation schemes for cuts and flows in capacitated graphs
• Minimum cuts in near-linear time
• scientific article; zbMATH DE number 1256719
• A new approach to the minimum cut problem

Cited in

(34)

• scientific article; zbMATH DE number 1418277 (Why is no real title available?)
• Routing in undirected graphs with constant congestion
• STACS 2005
• Deterministic sampling algorithms for network design
• Guided design search in the interval-bounded sailor assignment problem
• Sparse reliable graph backbones
• A general framework for graph sparsification
• Models and methods for solving the problem of network vulnerability
• Near-optimal distributed computation of small vertex cuts
• Ranking and sparsifying a connection graph
• Graph reduction with spectral and cut guarantees
• Hallucination helps: energy efficient virtual circuit routing
• Computing exact minimum cuts without knowing the graph
• Distributional limits of graph cuts on discretized grids
• Minimum cut in \(O(m \log^2 n)\) time
• Sublinear time hypergraph sparsification via cut and edge sampling queries
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Minimum cut in O(m^2 n time
• On packing low-diameter spanning trees
• On the size of two minimal linkages
• Integrated exact, hybrid and metaheuristic learning methods for confidentiality protection
• Random contractions and sampling for hypergraph and hedge connectivity
• scientific article; zbMATH DE number 7053293 (Why is no real title available?)
• Random sampling in cut, flow, and network design problems
• Fast augmenting paths by random sampling from residual graphs
• Fixed parameter approximation scheme for min-max \(k\)-cut
• On the use of guided design search for discovering significant decision variables in the fixed‐charge capacitated multicommodity network design problem
• Randomized approximation schemes for cuts and flows in capacitated graphs
• Deterministic Sampling Algorithms for Network Design
• A framework for clustering massive graph streams
• Faster cut sparsification of weighted graphs
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Time-message trade-offs in distributed algorithms
• Cluster before you hallucinate: node-capacitated network design and energy efficient routing

This page was built for publication: Random sampling in cut, flow, and network design problems

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