An FPT algorithm beating 2-approximation for k-cut
From MaRDI portal
Publication:4608074
zbMATH Open1403.68350arXiv1710.08488MaRDI QIDQ4608074FDOQ4608074
Authors: Anupam Gupta, Euiwoong Lee, Jason Li 
Publication date: 15 March 2018
Full work available at URL: https://arxiv.org/abs/1710.08488
Recommendations
- Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs
- Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
- Fixed parameter approximation scheme for min-max \(k\)-cut
- Fixed parameter approximation scheme for min-max \(k\)-cut
- A Polynomial Algorithm for the k-cut Problem for Fixed k
Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25)
Cited In (21)
- Partitioning subclasses of chordal graphs with few deletions
- Designing FPT algorithms for cut problems using randomized contractions
- On the fixed-parameter tractability of capacitated clustering
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- To close is easier than to open: dual parameterization to \(k\)-median
- Hypergraph \(k\)-cut in randomized polynomial time
- Deterministic enumeration of all minimum cut-sets and \(k\)-cut-sets in hypergraphs for fixed \(k\)
- Partitioning subclasses of chordal graphs with few deletions
- On integer and bilevel formulations for the \(k\)-vertex cut problem
- A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
- Title not available (Why is that?)
- FPT approximation and subexponential algorithms for covering few or many edges
- Constant-Factor FPT Approximation for Capacitated k-Median
- Fast and Deterministic Approximations for k-Cut.
- Fixed parameter approximation scheme for min-max \(k\)-cut
- Fixed parameter approximation scheme for min-max \(k\)-cut
- A parameterized approximation scheme for min \(k\)-cut
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
- Maximizing coverage while ensuring fairness: a tale of conflicting objectives
- LP relaxation and tree packing for minimum \(k\)-cut
- A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
This page was built for publication: An FPT algorithm beating 2-approximation for \(k\)-cut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608074)
