Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
K Chandrasekaran, C Chekuri - Mathematics of Operations …, 2022 - pubsonline.informs.org
We consider the Hypergraph-k-Cut problem. The input consists of a hypergraph G=(V, E)
with nonnegative hyperedge-costs c: E→ R+ and a positive integer k. The objective is to find …
with nonnegative hyperedge-costs c: E→ R+ and a positive integer k. The objective is to find …
[PDF][PDF] On the hardness of approximating the k-way hypergraph cut problem
We consider the approximability of the k-WAY HYPERGRAPH CUT problem: the input is an
edge-weighted hypergraph G=(V, E) and an integer k and the goal is to remove a min …
edge-weighted hypergraph G=(V, E) and an integer k and the goal is to remove a min …
[PDF][PDF] A note on the hardness of approximating the k-way Hypergraph Cut problem
We consider the approximability of K-WAY HYPERGRAPH CUT problem: the input is an
edge-weighted hypergraph G=(V, E) and an integer k and the goal is to remove a min …
edge-weighted hypergraph G=(V, E) and an integer k and the goal is to remove a min …
New approximations and hardness results for submodular partitioning problems
R Santiago - … Algorithms: 32nd International Workshop, IWOCA 2021 …, 2021 - Springer
We consider the following class of submodular k-multiway partitioning problems:(Sub-k-
MP)\min ∑ _ i= 1^ kf (S_i): S_1 ⊎ S_2 ⊎ ⋯ ⊎ S_k= V and S_i ≠ ∅ for all i ∈ k min∑ i= 1 kf …
MP)\min ∑ _ i= 1^ kf (S_i): S_1 ⊎ S_2 ⊎ ⋯ ⊎ S_k= V and S_i ≠ ∅ for all i ∈ k min∑ i= 1 kf …