Fixed parameter approximation scheme for min-max \(k\)-cut
From MaRDI portal
Publication:5925652
DOI10.1007/s10107-022-01842-3OpenAlexW3100811607WikidataQ114228489 ScholiaQ114228489MaRDI QIDQ5925652
Weihang Wang, Karthekeyan Chandrasekaran
Publication date: 14 March 2023
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-022-01842-3
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
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
- Random Sampling in Cut, Flow, and Network Design Problems
- 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
- Approximation Algorithms for Min-k-Overlap Problems Using the Principal Lattice of Partitions Approach
- The Karger-Stein algorithm is optimal for k-cut
- A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
- 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
- Improving the integrality gap for multiway cut
This page was built for publication: Fixed parameter approximation scheme for min-max \(k\)-cut
