<p>Assuming P<span class="math-container">$\ne$</span>NP, there is no such poly-time approximation algorithm.</p>
<p>I assume here that any approximation algorithm must return some feasible <span class="math-container">$k$</span>-cover, as long as the given input has one. By a <em><span class="math-container">$k$</span>-cover</em> of a given set <span class="math-container">$S$</span> of points in the plane, I mean a set of <span class="math-container">$k$</span> pairwise-disjoint axis-parallel rectangles such that every point in <span class="math-container">$S$</span> is in one of the rectangles.</p>
<p><strong>Theorem 1.</strong> <em>No such approximation algorithm runs in polynomial time, unless P=NP.</em></p>
<p><em>Proof.</em> If there were such an algorithm, it could decide the following decision problem in poly-time: <em>given <span class="math-container">$(k, S)$</span>, does <span class="math-container">$S$</span> have a <span class="math-container">$k$</span>-cover?</em> (regardless of objective).  By Theorem 2 of [1], this decision problem is NP-hard. <span class="math-container">$~~~\Box$</span></p>
<p><strong>Remark.</strong> The theorem assumes <span class="math-container">$k$</span> is part of the input. For any fixed <span class="math-container">$k$</span>, the problem can be solved in poly-time by exhaustive search, as there are <span class="math-container">$O(n^4)$</span> distinct rectangles to consider, so <span class="math-container">$O(n^{4k})$</span> possible covers, so there is an exact algorithm that runs in time <span class="math-container">$n^{4k+O(1)}$</span>.</p>
<hr />
<p>[1] Ahn, Hee-Kap, et al. &quot;Covering points by disjoint boxes with outliers.&quot; Computational Geometry 44.3 (2011): 178-190. <a href="https://doi.org/10.1016/j.comgeo.2010.10.002" rel="nofollow noreferrer">https://doi.org/10.1016/j.comgeo.2010.10.002</a></p>

CC BY-SA 4.0
2022-03-23T23:02:47.747Z
It's a great answer. Thank you.
All
CC BY-SA 4.0
2022-03-24T22:37:35.317Z
Can we hope maybe there is or not Pseudo-polynomial time approximation algorithm with constant factor?
All
CC BY-SA 4.0
2022-03-26T02:39:36.927Z
I don't think so..  Essentially the problem of approximating your problem is as hard or harder than the $k$-cover problem as defined above, which is NP-hard.   Approximating your problem in pseudo-poly time is no easier than solving an NP-hard problem in pseudo-poly time.
Neal Young
CC BY-SA 4.0
2022-05-09T02:23:14.490Z
Is there any reference about k-cover problem? I search in internet but I not found anything about that. Or how we relate above problem to k-cover? Becuase we try to optimize k-means but k-cover have no spicific objective function according your explination.
ErroR
CC BY-SA 4.0
2022-03-23T20:09:04.557Z
2022-03-23T21:46:19.993Z
2022-03-23T21:46:19.993Z
Neal Young
<p><a href="https://en.wikipedia.org/wiki/K-means_clustering" rel="nofollow noreferrer">According to wikipedia</a>,
consider <span class="math-container">$k$</span>-means problem in the plane :</p>
<p>k-means clustering aims to partition the <span class="math-container">$n$</span> observations into <span class="math-container">$k (≤ n)$</span> sets <span class="math-container">$S = \{S_1, S_2, \dots, S_k\}$</span> so as to minimize the within-cluster sum of squares. Formally, the objective is to find:
<span class="math-container">$$\min\sum_{i=1}^k\sum_{x\in S_i}  \| x − \mu_i \|^2$$</span></p>
<p>where <span class="math-container">$\mu_i$</span> is the mean of points in <span class="math-container">$S_i$</span>.</p>
<p>We know that there is <a href="https://www.sciencedirect.com/science/article/pii/S0020019022000084" rel="nofollow noreferrer">constant factor approximation algorithm</a> for <span class="math-container">$k$</span>-means problem.
Now, consider this example that we find <span class="math-container">$3$</span>-means clustering in the plane:</p>
<p><a href="https://i.sstatic.net/s3AnK.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/s3AnK.png" alt="enter image description here" /></a></p>
<p>But we want modify the above clusters such that we create such  clusters that each cluster has a rectangular shape as bellow:</p>
<p><a href="https://i.sstatic.net/7kYdU.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/7kYdU.png" alt="enter image description here" /></a></p>
<p>My question is, can we do some modification on any constant factor approximation algorithm for <span class="math-container">$k$</span>-means such that give us a rectangular partition and constant factor approximation algorithm? Also, is there any paper about this problem? It seems this problem should be well-studied, but I was unable to find any references.</p>

CC BY-SA 4.0
2022-03-22T12:02:14.350Z
Related: https://cstheory.stackexchange.com/questions/51177/rectangular-clustering-output-of-k-means-algorithm (now deleted)
Neal Young
CC BY-SA 4.0
2022-03-22T13:56:11.697Z
@NealYoung Is there any paper about this problem? Or something that give us some hints. I search many times but I can't find any related things about this problem.
All
CC BY-SA 4.0
2022-03-22T15:53:42.230Z
Do you know anyone who can help with this?
All
CC BY-SA 4.0
2022-03-22T19:06:32.253Z
I think the user @Jut has had similar questions, maybe they can help.
Neal Young
<ds.algorithms><approximation-algorithms>
Another variation of $k$-means problem in the plane
All
# Another variation of $k$-means problem in the plane

(Asked by: username_0 on 2022-03-21)

[According to wikipedia](https://en.wikipedia.org/wiki/K-means_clustering),
consider $k$-means problem in the plane :

k-means clustering aims to partition the $n$ observations into $k (≤ n)$ sets $S = \{S\_1, S\_2, \dots, S\_k\}$ so as to minimize the within-cluster sum of squares. Formally, the objective is to find:
$$\min\sum\_{i=1}^k\sum\_{x\in S\_i} \| x − \mu\_i \|^2$$

where $\mu\_i$ is the mean of points in $S\_i$.

We know that there is [constant factor approximation algorithm](https://www.sciencedirect.com/science/article/pii/S0020019022000084) for $k$-means problem.
Now, consider this example that we find $3$-means clustering in the plane:

[![enter image description here](https://i.sstatic.net/s3AnK.png)](https://i.sstatic.net/s3AnK.png)

But we want modify the above clusters such that we create such clusters that each cluster has a rectangular shape as bellow:

[![enter image description here](https://i.sstatic.net/7kYdU.png)](https://i.sstatic.net/7kYdU.png)

My question is, can we do some modification on any constant factor approximation algorithm for $k$-means such that give us a rectangular partition and constant factor approximation algorithm? Also, is there any paper about this problem? It seems this problem should be well-studied, but I was unable to find any references.

**Tags:** ds.algorithms, approximation-algorithms

> **Comments:**
> **username_1**: Related: https://cstheory.stackexchange.com/questions/51177/rectangular-clustering-output-of-k-means-algorithm (now deleted)  
> **username_0**: @NealYoung Is there any paper about this problem? Or something that give us some hints. I search many times but I can't find any related things about this problem.  
> **username_0**: Do you know anyone who can help with this?  
> **username_1**: I think the user @Jut has had similar questions, maybe they can help.  

---

## 1 answers

### Answer by username_1 on 2022-03-23. Score: 1 | Accepted answer

Assuming P$\ne$NP, there is no such poly-time approximation algorithm.

I assume here that any approximation algorithm must return some feasible $k$-cover, as long as the given input has one. By a *$k$-cover* of a given set $S$ of points in the plane, I mean a set of $k$ pairwise-disjoint axis-parallel rectangles such that every point in $S$ is in one of the rectangles.

**Theorem 1.** *No such approximation algorithm runs in polynomial time, unless P=NP.*

*Proof.* If there were such an algorithm, it could decide the following decision problem in poly-time: *given $(k, S)$, does $S$ have a $k$-cover?* (regardless of objective). By Theorem 2 of [1], this decision problem is NP-hard. $~~~\Box$

**Remark.** The theorem assumes $k$ is part of the input. For any fixed $k$, the problem can be solved in poly-time by exhaustive search, as there are $O(n^4)$ distinct rectangles to consider, so $O(n^{4k})$ possible covers, so there is an exact algorithm that runs in time $n^{4k+O(1)}$.

---

[1] Ahn, Hee-Kap, et al. "Covering points by disjoint boxes with outliers." Computational Geometry 44.3 (2011): 178-190. <https://doi.org/10.1016/j.comgeo.2010.10.002>

> **Comments:**
> **username_0**: It's a great answer. Thank you.  
> **username_0**: Can we hope maybe there is or not Pseudo-polynomial time approximation algorithm with constant factor?  
> **username_1**: I don't think so..  Essentially the problem of approximating your problem is as hard or harder than the $k$-cover problem as defined above, which is NP-hard.   Approximating your problem in pseudo-poly time is no easier than solving an NP-hard problem in pseudo-poly time.  
> **username_2**: Is there any reference about k-cover problem? I search in internet but I not found anything about that. Or how we relate above problem to k-cover? Becuase we try to optimize k-means but k-cover have no spicific objective function according your explination.  

---

