Timeline for A variation of Set Cover
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 24, 2023 at 23:49 | comment | added | Jackson | @FedorPetrov I have added an edit to the question to show what kind of situation I am thinking about. You are right, there might not be a solution, but I am considering only the situations where this is possible and talking about average over all such situations. I don't know if thinking in terms of graph partitions makes it any easier, that was just to clarify what kind of problem I am looking at. | |
| Apr 24, 2023 at 23:47 | history | edited | Jackson | CC BY-SA 4.0 |
added 346 characters in body
|
| Apr 24, 2023 at 23:43 | comment | added | Jackson | @ClaudeChaunier You are right. I was not looking for an algorithm for some choice of $S_i$'s. I wanted to know the average number of sets that can cover keeping $n,k$ fixed. Also, as pointed out by another comment, this is always not possible, but I am considering all such cases where such a situation exists. But again if there is an algorithm that can do this without depending on what $S_i$ looks like, i.e. for general input, then that will be awesome too. | |
| Apr 24, 2023 at 11:38 | comment | added | Fedor Petrov | (and as stated, this is never possible: we take $S_t$, then for $i=t$ we get a contradiction.) | |
| Apr 24, 2023 at 11:36 | comment | added | Fedor Petrov | But this is not always possible: what do we pick if $n=3$ and $S_i=\{i, i+1\}$ (enumeration of vertices is cyclic modulo 3)? | |
| Apr 24, 2023 at 11:25 | comment | added | Claude Chaunier | When you say "expected number", do you mean you don't want any particular algorithm for some choice of the $S_i$'s up to renumberings? You instead want an average $a_{n,k}$ or a minimum $m_{n,k}$ over all $S_i$'s and renumberings for $n$ and $k$ fixed? | |
| Apr 24, 2023 at 11:01 | answer | added | LeechLattice | timeline score: 2 | |
| S Apr 24, 2023 at 5:53 | review | First questions | |||
| Apr 24, 2023 at 5:59 | |||||
| S Apr 24, 2023 at 5:53 | history | asked | Jackson | CC BY-SA 4.0 |