Random sampling in cut, flow, and network design problems

DOI10.1145/195058.195422zbMath1344.68275OpenAlexW2068888615MaRDI QIDQ2817658

David R. Karger

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Flows in graphs (05C21)

Related Items (13)

Graph coarsening: from scientific computing to machine learning ⋮ Recent developments in maximum flow algorithms ⋮ Dynamic planar embeddings of dynamic graphs ⋮ Distributed CONGEST Algorithms against Mobile Adversaries ⋮ On percolation and ‐hardness ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Approximating minimum cuts under insertions ⋮ Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time ⋮ Random sampling and greedy sparsification for matroid optimization problems ⋮ Weighted random sampling with a reservoir ⋮ Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs ⋮ Unnamed Item ⋮ Approximability of capacitated network design

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