LP Relaxation and Tree Packing for Minimum $k$-Cut

DOI10.1137/19M1299359zbMath1444.05113arXiv1808.05765OpenAlexW3036281379MaRDI QIDQ3300759

Kent Quanrud, Chao Xu, Chandra Chekuri

Publication date: 30 July 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximationminimum cuttree packing\(k\)-cut

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (10)

Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ Unnamed Item ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Unnamed Item ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum cost subpartitions in graphs
• A faster algorithm for computing the principal sequence of partitions of a graph
• Fully-dynamic min-cut
• The principal lattice of partitions of a submodular function
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the \(k\)-cut problem
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
• Theory of Principal Partitions Revisited
• Optimal attack and reinforcement of a network
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• 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
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• 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
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• The Steiner k-Cut Problem
• Minimum cuts in near-linear time

This page was built for publication: LP Relaxation and Tree Packing for Minimum $k$-Cut