Fixed parameter approximation scheme for min-max \(k\)-cut
From MaRDI portal
Publication:5918433
DOI10.1007/978-3-030-73879-2_25zbMath1483.90133arXiv2011.03454OpenAlexW3162567112MaRDI QIDQ5918433
Karthekeyan Chandrasekaran, Weihang Wang
Publication date: 21 December 2021
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2011.03454
Integer programming (90C10) Minimax problems in mathematical programming (90C47) Combinatorial optimization (90C27)
Related Items (2)
Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Greedy splitting algorithms for approximating multiway partition problems
- Min-max correlation clustering via multicut
- Local guarantees in graph cuts and clustering
- Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- LP Relaxation and Tree Packing for Minimum $k$-Cut
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- The Complexity of Multiterminal Cuts
- Finding k Cuts within Twice the Optimal
- A new approach to the minimum cut problem
- The Karger-Stein algorithm is optimal for k-cut
- A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
- Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
- Multiway cut, pairwise realizable distributions, and descending thresholds
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Min-Max Graph Partitioning and Small Set Expansion
- Parameterized Algorithms
- Cutsets and partitions of hypergraphs
- Fixed parameter approximation scheme for min-max \(k\)-cut
- Improving the integrality gap for multiway cut
This page was built for publication: Fixed parameter approximation scheme for min-max \(k\)-cut
