4
$\begingroup$

This is related to some old posts that were closed because someone had felt that they're related to homework. All I'm looking for here is a reference to a paper that may have partially or completely solved the following problem: n points on the unit interval are given. Consider the set of processes operate discretely on the n points as follows: at every time step, a process takes two points and replaces them by their midpoint. The process stops if only two points are left. I'm interested to know about an optimal process in this set (meaning a process that given an initial set of n points would lead to the smallest distance between the two final points). Any known bounds on the optimal final distance? Any generalization to higher dimensions? Thanks!

$\endgroup$
  • $\begingroup$ Related: 1, 2 $\endgroup$ – Kaveh Dec 7 '10 at 13:56
10
$\begingroup$

Rather than go through some complicated bureaucracy to close this and resuscitate the other earlier-asked variants, it's probably straightforward just to answer this now; I think it's long enough after the previous questions that we don't so much need to worry about it being homework (and the way it's phrased now certainly seems much less suspicious).

The paper I was referring to in the discussion on the earlier problems is:

"Exponentially small bounds on the expected optimum of the partition and subset sum problems", G. S. Lueker, Random Structures and Algorithms, 1998.

But now that I think about it again, I realize that the problem Lueker solves is actually a bit different from what you're asking: he repeatedly replaces a pair of points by their difference, rather than their average. The application for this replacement process is in a variant of the subset sum problem, in which one is given n real numbers and one is trying to find a subset minimizing the difference between the sum of the weights in the chosen subset and the sum of the weights not in the subset. Replacing a pair by their difference is equivalent to imposing a constraint that exactly one of the two items is in the subset: each of the two choices for what to do with the difference in the replaced problem has exactly the same effect as each of the two choices for which item to include in the original problem.

This is also somewhat related to some work of Valiant, "Short monotone formulae for the majority function", J. Algorithms, 5, 1984, 363–366: by repeatedly replacing triples of numbers by their median, you can with high probability find a point near the median of the numbers. See also my paper with Clarkson et al, "Approximating Center Points with Iterated Radon Points", which generalizes this result to higher dimensions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.