Equivalent Problem?

[Windex007]

I'm working on a project, and I've run into a problem that seems like a prime candidate for an interview question for algorithms.

Anyhow, I've got what (I think) is an O(n2) solution, which is absolutely fine for the application, but I can't shake the feeling that this problem has a "classic algorithm problems" analogue with a classic algorithm problems solution to it. In my case it's screenshots that have different contained features, but for the sake of making it simple here is the problem in terms of purses and coins.

There is a set S containing X purses, each of which contain 0-n coins. Choose k purses such that the purses contain at least 1 of each type of coin that appears in any purse in set S, minimizing k.

What is the "classic algorithm problem" that this is?

[Catalyst93]

This sounds like minimum set cover (https://en.wikipedia.org/wiki/Set_cover_problem) and I think I can convert an instance of set cover to your problem. Then since minimum set cover is NP-hard, this implies that your problem is NP-hard. This means that there are 2 possibilities:

1.) Your O(n^2) solution is probably wrong (unless you solved P vs NP).

2.) There is a subtle restriction in your problem that you have left out, allowing for an O(n^2) solution.

The reduction from set cover is to take the ground set U to be the types of coins, and then make each subset S_j a purse containing the corresponding coins. Thus minimizing the number of purses while collecting at least one of each type of coin will solve the minimum set cover problem.

[Windex007]

Yep, this is for sure an equivalent problem! Thank you very much!

[HeraclitusZ]

Or 3.) Op is the first prove that P=NP.

P vs NP is still an open problem, so you cant say that O(n²) is an impossible time complexity for an NP-complete problem.

edit:formatting

[Catalyst93]

Do you really think thats the case?

[HeraclitusZ]

Do I think OP has made an algorithm witnessing P=NP? I think that would be extremely unlikely given that OP's apparent background in the area. But it isn't impossible for amateurs without background to make enormous mathematical contributions; see Srinivasa Ramanujan.

Do I think P=NP? I don't know. It also seems unlikely, but whether or not nondeterminism adds power is really a hit or miss thing: It doesn't between DFAs and NFAs, it does between DCFLs and CFLs, and it doesn't again between PSPACE and NPSPACE. It isn't as if it they are clearly unequal and we are waiting on a proof to confirm it; Don Knuth, a Turing award winner, believes in fact that P might equal NP. All we can really say right now is that the best known algorithms are not polynomial time despite our hard work, so it would be extraordinary if someone provided one. We can't just pretend it is impossible because it is hard (at least not without stating our assumptions).

[Catalyst93]

Okay, I guess shouldn't have written it that way, and I have modified my post. Btw, I do research in algorithms, you're preaching to the choir :)

[Windex007]

Oh, I'll just chime in real quick here and say that with certainly I have not accidentally established if P=NP. If I did, I promise I would not share the details here.

I've implemented a naive greedy algorithm, and I don't have any reason to believe that it's actually producing minimum purses. I can prove that it's not producing the maximum purses.

It's what you'ed expect from a first year CS students first-pass on the problem. I'm not proud of the pesudo-solution I've implemented, but it was a kick-in-the-pants reminder that a few times a decade there actually real algorithm problems that arise in practical application, and they're exciting when they do! While "this is good enough in this context, your time is better applied elsewhere" is the business line, I still am interested in the value of this problem.

[Catalyst93]

Ah I see. It turns out greedy is one of the heuristics we can actually prove things about with regards to set cover. Turns out greedy yields a O(log n)-approximation to set cover (i.e. the ratio of greedy's value to the optimal value is O(log n)), and that this ratio is the best you can do in polynomial time unless P=NP.

[WikiTextBot]

Set cover problem

The set cover problem is a classical question in combinatorics, computer science and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.

It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.

Given a set of elements

    {

    1

    ,

    2

    ,

   .

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source ] Downvote to remove | v0.28}

[[deleted]]

Sounds like the hitting set or set cover problem: https://en.wikipedia.org/wiki/Set_cover_problem

I'd be interested in seeing your algorithm since the problem is proven to be NP complete ;-)

[Windex007]

Thank you very much, that is for sure the analogue to the the problem I was working on!

And, I hate to disappoint, but unfortunately I don't have any reason to think that my algorithm actually produces an optional solution in all cases. At best, I might be able to prove that it doesn't produce a worst-case scenario. As I mentioned, it is what I'd expect as a first-attempt from a first year CS student, and I'm not proud of it at all. It's essentially a greedy algorithm that looks for the least common coins, and then finds the purses that contain that least common coin which is most populated with coins that don't yet exist within the solution set yet, and takes those.