# Tag Info

2

Theorem 1. The problem admits a 2-approximation algorithm that runs in $O((m+n)\log n)$ time, given a graph $G=(V,E)$ with $m$ edges and $n$ vertices. [Caveat: The current post doesn't specify the objective-function value if one or both of the clusters contains no edges. I assume that the objective-function value only sums the maximum-weight edges within ...

2

The problem even seems to be solvable in polynomial time. Let us call $C_1$ the black cluster and $C_1$ the white cluster. We test for every two edges $e_1,e_2\in E$ whether there exists a bipartition so that $e_1$ is the heaviest edge in $C_1$ and $e_2$ is the heaviest edge in $C_2$. In the end, we ouput the bipartition that minimizes the sum of the two ...

1

If you rotate your rectangles through a common origin, then your method works. Your method works if there always exists a separating line that is parallel to a side of one of your rectangles. Such a line indeed exists. To see this, start from an arbitrary separating line and rotate it until it hits both rectangles, say in vertices $p$ and $q$. For a given ...

Only top voted, non community-wiki answers of a minimum length are eligible