Timeline for Rounding to minimise the sum of errors in pairwise distances
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Sep 1, 2012 at 22:58 | history | bounty ended | Jukka Suomela | ||
| S Sep 1, 2012 at 22:58 | history | notice removed | Jukka Suomela | ||
| Sep 1, 2012 at 22:58 | vote | accept | Jukka Suomela | ||
| Aug 31, 2012 at 3:40 | answer | added | Rong Ge | timeline score: 9 | |
| Aug 31, 2012 at 0:08 | history | edited | Jukka Suomela | CC BY-SA 3.0 |
terminology
|
| Aug 29, 2012 at 14:26 | answer | added | Rong Ge | timeline score: 1 | |
| Aug 29, 2012 at 13:31 | answer | added | Marzio De Biasi | timeline score: 1 | |
| Aug 28, 2012 at 23:12 | comment | added | Jukka Suomela | @vzn: I am interested in the computational complexity of this problem. If you can prove that there is a polynomial-time local search approach that is guaranteed to find the global optimum, the bounty is yours. | |
| Aug 28, 2012 at 22:06 | comment | added | vzn | using the floor/ceil idea, think there is a fast greedy algorithm that finds a pretty good local optimum using an approach similar to powells algorithm. it seems like in this formulation the search space is "mostly concave"... but maybe you are not actually interested in a numerical solution? | |
| Aug 28, 2012 at 18:15 | comment | added | vzn | further idea-- use $e'(i,j) = ((y_j - y_i) - (x_j - x_i))^2$ instead of absolute value to minimize. this often improves the algebraic analyzability/simplification of many probs & often does not affect the minimum | |
| Aug 28, 2012 at 17:46 | comment | added | vzn | re the Estie ref cited by val above.. somewhat similar however note it considers ("1d beautification as NP complete", p2) adjacent point differences $y_{i+1} - y_i$ -- not pairwise. a nice analysis might relate the adjacent and pairwise problems, its not clear theres any relation so far... | |
| Aug 28, 2012 at 16:30 | comment | added | vzn | what about this as a possible simplification or constraint-- the optimum must round every rational either using floor(x) or ceil(x)? then there are 2^n possible cases to consider...? moreover much of the math in the 2^n comparisons (calculation of the error function for each case) is repeated & can be reused... | |
| Aug 26, 2012 at 22:41 | comment | added | Jukka Suomela | I have a feeling that this problem should certainly be solvable using well-known techniques. Let's see if the bounty is enough to motivate people to solve this. :) | |
| S Aug 26, 2012 at 22:39 | history | bounty started | Jukka Suomela | ||
| S Aug 26, 2012 at 22:39 | history | notice added | Jukka Suomela | Draw attention | |
| Aug 14, 2012 at 23:18 | comment | added | Jukka Suomela | @TsuyoshiIto: Good question. For the "real" application, I guess we would prefer a solution with $y_1 < y_2 < \dotso < y_n$, and this additional constraint certainly changes the optimum. The formulation with $\le$ was just a simplification — my intuition was that dropping the $\le$ constraint "obviously" never helps, but I have not actually checked it yet. | |
| Aug 14, 2012 at 23:07 | comment | added | Tsuyoshi Ito | Is it essential to require that the order is preserved? In other words, is there an instance where dropping the constraint y_1 ≤ y_2 ≤ … ≤ y_n changes the optimal value? Not that I know the answer for the problem with this constraint dropped, but I just wonder if you can potentially simplify the problem by dropping it. | |
| Aug 14, 2012 at 18:16 | comment | added | val | This report by Estie Arkin seems related: ams.sunysb.edu/~estie/papers/beautification.pdf It is proved that minimizing the number of distinct inter-point distances in the output is NP-hard. This is not the total sum of shifts, as in this questions, but maybe the hardness gadgets in the report could suggest a hardness proof for this problem. | |
| Aug 14, 2012 at 13:51 | history | edited | Jukka Suomela | CC BY-SA 3.0 |
figure & example
|
| Aug 14, 2012 at 12:36 | comment | added | Jukka Suomela | @SureshVenkat: Actually, in that case the problem becomes very simple: you just select the best integral distance $y_i - y_{i-1}$ for each $i$. That is, you can minimise each $e(i-1,i)$ independently. | |
| Aug 14, 2012 at 9:11 | comment | added | Suresh Venkat | Does the DP work for the case when you only care about adjacent measurements ? | |
| Aug 13, 2012 at 20:53 | history | tweeted | twitter.com/#!/StackCSTheory/status/235116792224284673 | ||
| Aug 13, 2012 at 17:58 | history | asked | Jukka Suomela | CC BY-SA 3.0 |