Use a different, possible inexact, hypergraph formulation of the problem that can be more easily handled by Sebastian's framework.
Closed this issue · 0 comments
A few notes on that:
- I got in touch with the developer of PaToH and it turns out that support for edge balancing is only experimental, likely does not work (i.e., produces imbalance solutions) for non-powers of 2,
and only balances internal edges. Internal edge balancing is sth. thats already possible in a feature branch of KaHyPar.
- I talked to Prof. Sanders today and he proposed a simple formulation that should give reasonably balanced solutions for k=2:
He proposed to use the standard hypergraph model (sites = vertices, repeats classes = hyperedges) and then assign each vertex its degree as weight.
While this does not exactly model our problem, it produced reasonably balanced bisections in my initial tests. However, this approach does not work well for k > 2.
- Another ad hoc solution for assigning the 'dangling' vertices is the following: After partitioning the dual hypergraph, all non-dangling vertices are assigned to their
respective block in the original hypergraph and then marked as fixed. Then, KaHyPar is called again in fixed vertex partitioning mode and then tries to find an assignment
for the remaining vertices such that the cut is minimized. The only problem I currently see is that we then might end up with imbalanced solutions.