Sebastians Einwand überprüfen

[poettig]

I though a little bit about the problem definition of team 2 and the complexity/capacity constraint that is used to balance the edges.
Currently, I see the following problem:

The idea is based on [1]. However, in their problem, the authors bound the size of each block (i.e. in terms of the number of edges) by some constant C.
While this works, I think it does not generalize to the proposed bound of (1+e) (|E| / k) proposed by team 2.
This upper bound might not be feasible, because as soon as a hyperedge is cut (i.e., connects more than one block), then the weight of the edge is accounted for multiple times.

For example if an edge connects 3 blocks, then its weight is added to each of the three blocks. Thus the weight of all blocks (which in the formulation of
team 2 corresponds to the sum of the edges that connect the block) is very likely to be larger then (1+e) (|E| / k).

Please correct me if I'm wrong!
So in order to use the proposed approach, we would need to come up with a reasonable upper bound for the block weights.

[lukashuebner]

Duplikat von "2-Phasen Ansatz"