Fast and Deterministic Approximations for k-Cut.

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.23OpenAlexW2977612001MaRDI QIDQ5875475

Kent Quanrud

Publication date: 3 February 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11238/pdf/LIPIcs-APPROX-RANDOM-2019-23.pdf/

zbMATH Keywords

\(k\)-cutmultiplicative weight updates

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Unnamed Item ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

Cites Work

• Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
• Minimum cost subpartitions in graphs
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A data structure for dynamic trees
• On the \(k\)-cut problem
• Approximability of capacitated network design
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• Approximation algorithms for covering/packing integer programs
• Random sampling in cut, flow, and network design problems
• Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
• Beyond the flow decomposition barrier
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• Finding k Cuts within Twice the Optimal
• A new approach to the minimum cut problem
• A simple min-cut algorithm
• Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems
• Local Flow Partitioning for Faster Edge Connectivity
• A General Approximation Technique for Constrained Forest Problems
• Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis
• The number of minimum k -cuts: improving the Karger-Stein bound
• On Approximating (Sparse) Covering Integer Programs
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• The Steiner k-Cut Problem
• Minimum cuts in near-linear time
• The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item