patternMinor
Multi-line fitting problem
Viewed 0 times
problemmultilinefitting
Problem
Given a set of
I can formulate an ILP for the same. The problem seems to be hard. I want to formally prove its NP-Completeness.
Note that, for
Even when
n points, and a number k decide whether there exist k straight lines such that all of the points are covered. Here a point is covered by a line if that point lies on that line.I can formulate an ILP for the same. The problem seems to be hard. I want to formally prove its NP-Completeness.
Note that, for
k=1, the problem is in P. Simply find the liner regression/line fitting and test whether the error is zero.Even when
k=2, the problem still seems to be hard. Is it really so? And what about the general case? What are the candidate problems for the reduction?Solution
The general case of this problem is NP-complete, as shown by Meggido and Tamir [N. Megiddo and A. Tamir. On the complexity of locating linear facilities in the plane. Oper. Res. Lett., 1:194–197, 1982.]. Their reduction is from 3SAT, in the usual way: some points in the construction represent clauses, others variables, which are all carefully arranged together with some additional points such that the relation between clauses and variables in 3SAT is represented in the instance. I suggest you read the paper for more details.
Note that if $k$ is constant the problem can be solved in polynomial time: we only need to consider the lines that contain at least two of our points, of which there are $O(n^2)$. So, there are only $O( {n^2 \choose k})=O(n^{2k})$ sets of lines we need to test, which can be done in $O(n)$ time for each set, giving an algorithm that takes $O(n^{2k+1})$ time in total.
While the brute-force approach above is already polynomial for a constant $k$, there are better algorithms. In fact, this problem is fixed parameter tractable in $k$: Afshani et al. give an algorithm with a $O^((Ck/\log k)^{k})$ time algorithm, where $C$ is some constant and the $O^(\cdot)$ notation ignores polynomial factors. However, this particular algorithm may not be very practical. Depending on the application, formulating this problem as an ILP or set cover instance can be more efficient.
Note that if $k$ is constant the problem can be solved in polynomial time: we only need to consider the lines that contain at least two of our points, of which there are $O(n^2)$. So, there are only $O( {n^2 \choose k})=O(n^{2k})$ sets of lines we need to test, which can be done in $O(n)$ time for each set, giving an algorithm that takes $O(n^{2k+1})$ time in total.
While the brute-force approach above is already polynomial for a constant $k$, there are better algorithms. In fact, this problem is fixed parameter tractable in $k$: Afshani et al. give an algorithm with a $O^((Ck/\log k)^{k})$ time algorithm, where $C$ is some constant and the $O^(\cdot)$ notation ignores polynomial factors. However, this particular algorithm may not be very practical. Depending on the application, formulating this problem as an ILP or set cover instance can be more efficient.
Context
StackExchange Computer Science Q#159414, answer score: 6
Revisions (0)
No revisions yet.