Fix a constant $0<\alpha<1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w_1, w_2,\ldots, w_N$ and with coordinates all in the range $[0,M]$ for some $M$. Let $W=\sum w_i$. Find a simple (i.e. non self-intersecting) curve that partitions them into two sets of rectangles such that each set has total weight at least $\alpha W$ and the total weight of all rectangles cut by the curve is as small as possible, or output that no such curve exists. This is NP-complete, and I'm interested in a good heuristic/approximation algorithms with $O(N+poly(M))$ time (or more exactly $O(N+poly(M)+polylog(W))$ time).
A thorough search doesn't give me any reference in literature that studies this problem. Any insight is appreciated!