On the hardness of approximating the k-\textsc{Way Hypergraph Cut} problem

DOI10.4086/TOC.2020.V016A014MaRDI QIDQ5140849zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Shi Li

Publication date 17 December 2020

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2020.v016a014

zbMATH Keywords

\(k\)-way hypergraph cuthardness of approximation

Mathematics Subject Classification ID

Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1670644
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• From graph to hypergraph multiway partition: is the single threshold the only route?
• scientific article; zbMATH DE number 6850403
• Computing minimum multiway cuts in hypergraphs

Cites work

• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Finding k Cuts within Twice the Optimal
• Finding minimum 3-way cuts in hypergraphs
• Greedy splitting algorithms for approximating multiway partition problems
• LP relaxation and tree packing for minimum k-cut
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

Cited in

(7)

• New approximations and hardness results for submodular partitioning problems
• scientific article; zbMATH DE number 6850403 (Why is no real title available?)
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• Sum-of-squares lower bounds for densest k-subgraph
• Approximating submodular \(k\)-partition via principal partition sequence
• Approximating submodular matroid-constrained partitioning
• \(\{s,t\}\)-separating principal partition sequence of submodular functions

This page was built for publication: On the hardness of approximating the \(k\)-\textsc{Way Hypergraph Cut} problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140849)