Timeline for Sampling with non-uniform costs
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 19, 2010 at 0:15 | comment | added | Suresh Venkat | Your problem might be too hard as stated. Suppose I have an instance where all $c_i = 1$ except for $c_1 = n$. Now my bit vector has $b_1 = 1$ and $b_n = 1$, with all other bits being zero. OPT can obtain a factor 2 approximation (or k=1) by querying that bit, but it will be difficult to find $b_n$ by random sampling in less than $\Theta(n)$ cost. | |
| Nov 18, 2010 at 22:57 | comment | added | Warren Schudy | This sounds like it could be homework. Can you tell us why you care? | |
| Nov 18, 2010 at 20:33 | answer | added | trutheality | timeline score: 1 | |
| Nov 18, 2010 at 18:27 | history | asked | Jack | CC BY-SA 2.5 |