Problem Detail: For a certain problem I am trying to solve given a list of integers, it is advantageous to me to first identify as many of the integers that are mutually coprime as possible. I’m having trouble thinking of a good general algorithm for this, and everything I’ve found online seems to relate to problems that are slightly different to what I’m going for. For example, given the multiset of integers A = {12, 15, 15, 16}, I would like the algorithm to return {15, 16}. The first naive solution I could think of was to order the numbers in increasing order, take the first number into my set, then take any number after that which is coprime with all of the numbers in the set. This works for things such as {2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, but it would erroneously give {12} in my example above. Besides that, the best idea I have is to create a list of sets of the factors of each number, at which point this problem can be reduced to the exact cover problem. However, I feel like this would have a relatively large amount of overhead, especially given the fact that the data sets I’m operating on won’t be very large (~1000 elements somewhere in between 1 and 500). Is there any algorithm I could apply here that would be more simple to implement (even if it is slightly slower) and would guarantee an optimal solution?
Asked By : user3030010
Answered By : D.W.
Your problem is equivalent in complexity to the maximum set packing problem. Unfortunately, maximum set packing is NP-hard. Therefore, you’ll need to use one of the methods in Dealing with intractability: NP-complete problems. Here’s the gist of the equivalence. Each integer in your set A corresponds to a set of its prime factors; now you’re looking for a maximum-size collection of those sets that are pairwise disjoint. That’s exactly maximum set packing. This is only the gist of the idea; this reduction doesn’t quite work, because as you noticed, factoring each element of A can take quite a bit of time (there’s no known polynomial-time algorithm for factoring). It’s possible to fix up the reduction as follows. Given an instance of your problem, factor A into a coprime base. A coprime base is a list of integers that are pairwise co-prime (no two elements in the coprime base any common factor), and where every number in A can be factored into a product of elements of the coprime base. For instance, a coprime base for A = {30, 105, 126} would be {5, 6, 21}. Note that the elements of the coprime base do not need to be prime. There are efficient algorithms for finding a coprime base for A. Now, associate to each number x in A the set of elements of the coprime base that are divisors of x. Then you have an instance of the maximum set packing problem. (Conversely, given an instance of the maximum set packing problem, you can convert it into an instance of your problem, by simply treating the universe for the set packing instance to be the prime numbers.) So given that you basically have an instance of maximum set packing, what should you do? Well, maximum set packing has been well-studied, so you can use the literature on that problem. Here are some candidate approaches: ILP: It’s easy to formulate the maximum set packing problem as an instance of integer linear programming. You have a zero-or-one variable $x_i$ for each integer $i$ in A, with the idea that $x_i=1$ means that $i$ is included in the output list. You add a constraint $x_i+x_j le 1$ for every pair of numbers $i,j$ that have a common factor. Then, you try to maximize the objective function $sum_{i in A} x_i$. Feed this to an off-the-shelf integer linear programming solver, and it will give you the best solution it could find. If you want something simple to implement and optimal, I suspect the ILP-based algorithm is your best bet. It’ll be easy to implement. There’s no guarantee that it’ll be efficient — it’s an NP-hard problem, after all — but it might work well enough in practice if the problems sizes are small enough. Heuristics: You can use any of the known heuristics for set packing. See, e.g., https://en.wikipedia.org/wiki/Set_packing#Heuristics, or search the research literature. Approximation algorithms: Wikipedia says that it is known how to approximate maximum set packing to within a factor $k/2$, if $k$ is the size of the largest set. (In other words, $k$ is the maximum number of elements of the coprime base that can divide any single element of A.) If the numbers in A aren’t too large, then $k$ will be relatively small, so this approximation algorithm might be reasonably effective. Wikipedia doesn’t say what the algorithm is, so you’ll have to do some research in the literature.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/48298
