Timeline for Im looking for an algorithm that can solve or approximate the solution to a problem
Current License: CC BY-SA 4.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 9, 2019 at 19:23 | answer | added | Max Alekseyev | timeline score: 1 | |
| Nov 9, 2019 at 19:15 | comment | added | Max Alekseyev | @RobPratt: You're right. In fact, it's the Minimum (not Maximum) coverage problem, better known as Minimum k-Union problem. In the context of OP's problem, let $D_j$ be the set of doors requiring the key $j$, then we need to pick a set of keys $T$ with $|T|=M-k$ minimizing the size of $\bigcup_{j\in T} D_j$. | |
| Nov 8, 2019 at 11:40 | vote | accept | Dangz1 | ||
| Nov 7, 2019 at 19:04 | comment | added | RobPratt | I added the SAS code to my answer. | |
| Nov 7, 2019 at 11:02 | comment | added | Dangz1 | That sounds like a good solution and time. What did you use? Can I see your code? | |
| Nov 7, 2019 at 2:08 | comment | added | RobPratt | Excluding the problematic data, with $k=200$, I get an optimal objective value of 1290 in a few minutes. | |
| Nov 7, 2019 at 1:00 | comment | added | Dangz1 | I imagined k as a variable, but you can use any value. The duplicates should be removed. I think % mismatch is due to some ingredients being diluted, they should be the same ingredient though(you can exclude problematic data if you like). Im sorry for giving you messy data set, I just pulled the data from a site today. | |
| Nov 7, 2019 at 0:53 | comment | added | RobPratt | Do you still want to use $k=20$? Also, there are a couple other data issues: 75 duplicate recipes (is this intended?), and mismatch in ingredients (recipe has %, but ingredient does not have %). | |
| Nov 7, 2019 at 0:50 | comment | added | Dangz1 | Yes, the filenames are reversed. K would be the number of ingredients(keys). | |
| Nov 7, 2019 at 0:32 | comment | added | RobPratt | Looks like the filenames are reversed, but I was able to download. What is $k$ here? | |
| Nov 6, 2019 at 22:24 | comment | added | Dangz1 | @RobPratt I dont know if Im allowed to post links here but here:link. Its a google drive link. The doors are actually just recipes to make ejuice and keys would be the ingredients. Each line is one recipe, ingredients are separated by commas. I have wrongly assumed that there are only 100 keys. There are actually 2370 keys(ingredients). | |
| Nov 6, 2019 at 21:39 | comment | added | RobPratt | Similar flavor, but not quite the same as the maximum coverage problem. If you interchange $x$ and $y$ in the Wikipedia formulation, you can see that the difference between the problems is AND versus OR. In the OP's problem, each door requires all the keys in its set. In maximum coverage, each covered element requires only one set that contains it. | |
| Nov 6, 2019 at 21:29 | comment | added | Max Alekseyev | This is Maximum coverage problem. | |
| Nov 6, 2019 at 17:18 | comment | added | RobPratt | Do you have data you can share for your 100-key instance? | |
| Nov 6, 2019 at 1:20 | answer | added | david | timeline score: 1 | |
| Nov 5, 2019 at 22:00 | history | edited | Andrés E. Caicedo |
edited tags
|
|
| S Nov 5, 2019 at 20:56 | history | suggested | Daniele Tampieri | CC BY-SA 4.0 |
Math Jaxed + minor grammar correction and formatting. I decided to edit it since the problem posed seems a real research problem: however I could be wrong.
|
| Nov 5, 2019 at 20:50 | review | Suggested edits | |||
| S Nov 5, 2019 at 20:56 | |||||
| Nov 5, 2019 at 20:03 | history | edited | Dangz1 | CC BY-SA 4.0 |
deleted 22 characters in body
|
| S Nov 5, 2019 at 20:01 | history | suggested | RobPratt |
added combinatorial-optimization tag
|
|
| Nov 5, 2019 at 19:56 | review | Suggested edits | |||
| S Nov 5, 2019 at 20:01 | |||||
| Nov 5, 2019 at 19:55 | answer | added | RobPratt | timeline score: 3 | |
| Nov 5, 2019 at 19:50 | review | First posts | |||
| Nov 5, 2019 at 20:50 | |||||
| Nov 5, 2019 at 19:49 | history | asked | Dangz1 | CC BY-SA 4.0 |