Fixed parameter approximation scheme for min-max \(k\)-cut

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

zbMATH Keywords

min-max objective\(k\)-cutparameterized approximation scheme

Mathematics Subject Classification ID

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