Fast and deterministic approximations for k-cut

DOI10.4086/TOC.2022.V018A007OpenAlexW4225947064MaRDI QIDQ5077149FDOQ5077149

Authors: Kent Quanrud 

Publication date: 18 May 2022

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.07143

Recommendations

• Fast and Deterministic Approximations for k-Cut.
• Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs
• Finding k Cuts within Twice the Optimal
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• A Polynomial Algorithm for the k-cut Problem for Fixed k

zbMATH Keywords

\(k\)-cutmultiplicative weight updates

Mathematics Subject Classification ID

Approximation algorithms (68W25) Theory of computing (68Qxx)

Cites Work

• Approximation algorithms for NP-hard problems.
• A data structure for dynamic trees
• Beyond the flow decomposition barrier
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• A General Approximation Technique for Constrained Forest Problems
• Title not available (Why is that?)
• Tree packing and approximating \(k\)-cuts
• The multiplicative weights update method: a meta-algorithm and applications
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Title not available (Why is that?)
• Fast Algorithms for Finding Nearest Common Ancestors
• The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• A new approach to the minimum cut problem
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Graph expansion and the unique games conjecture
• Finding k Cuts within Twice the Optimal
• A simple min-cut algorithm
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• Minimum cuts in near-linear time
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Designing FPT algorithms for cut problems using randomized contractions
• Approximation algorithms for covering/packing integer programs
• Title not available (Why is that?)
• Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
• Approximability of capacitated network design
• Minimum cost subpartitions in graphs
• The Steiner k-Cut Problem
• On the \(k\)-cut problem
• Compact cactus representations of all non-trivial min-cuts
• LP relaxation and tree packing for minimum \(k\)-cut
• An FPT algorithm beating 2-approximation for \(k\)-cut
• Fast and Deterministic Approximations for k-Cut.
• Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
• Deterministic global minimum cut of a simple graph in near-linear time
• Near-linear time approximation schemes for some implicit fractional packing problems
• On approximating (sparse) covering integer programs
• Local flow partitioning for faster edge connectivity
• The number of minimum \(k\)-cuts: improving the Karger-Stein bound

Cited In (9)

• LP relaxation and tree packing for minimum \(k\)-cuts
• Title not available (Why is that?)
• Optimal Bounds for the k -cut Problem
• Title not available (Why is that?)
• A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
• Title not available (Why is that?)
• Approximation algorithms for minimum \(K\)-cut
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Fast and deterministic approximations for \(k\)-cut

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