scientific article; zbMATH DE number 7286924

DOI10.4086/toc.2020.v016a014zbMath1462.68066OpenAlexW3112296152MaRDI QIDQ5140849

Chandra Chekuri, Shi Li

Publication date: 17 December 2020

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

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

hardness of approximation\(k\)-way hypergraph cut

Mathematics Subject Classification ID

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

Related Items (2)

Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time ⋮ New approximations and hardness results for submodular partitioning problems

Cites Work

• Finding minimum 3-way cuts in hypergraphs
• Greedy splitting algorithms for approximating multiway partition problems
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Detecting high log-densities
• LP Relaxation and Tree Packing for Minimum $k$-Cut
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Finding k Cuts within Twice the Optimal
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

This page was built for publication: