Dave has correctly understood the problem. I take it from the problem description that you are given n intervals [r1(i),r2(i)]_i=1^n and are to choose an x(i) in each interval so as to minimize the maximum value of |x(i)-x(j)|. The intervals may overlap, in which case you may be able to pick equally-spaced points, or they may not overlap, in which the endpoints of the intervals become constraints on the selection of the x(i), and may prevent you from selecting equally-spaced points.
Dave 2009/10/22 saltycookie <saltycoo...@gmail.com> > It is not a solution for minimize maximum distance either, since > |x(i)-x(j)| <= c does not hold for every pair of points, only for adjacent > points. > > 2009/10/21 saltycookie <saltycoo...@gmail.com> > >> Yes, you are quite right. If I am not mistaken, you give a good solution >> for finding the minimum maximum distance. >> >> >> But what about the original problem where we want to find the maximum >> minimum distance? I am not clear about the connection between the two >> problems. >> >> Thanks. >> >> 2009/10/21 Dave <dave_and_da...@juno.com> >> >> >>> 林夏祥 , think again. If we are trying to minimize the maximum distance, >>> then we want to minimize the upper bound. That is what I specified: >>> letting c be the upper bound, find the smallest c such that all of the >>> distances do not exceed c. That gives rise to the inequalities >>> |x(i)-x(j)| <= c. >>> If necessary, this can be written as two inequalities: >>> x(i) - x(j) <= c and >>> x(j) - x(i) <= c. >>> >>> Since the relationship is "and," we can just use the two inequalities >>> as part of the constraint conditions. >>> >>> Dave >>> >>> On Oct 21, 12:02 am, 林夏祥 <saltycoo...@gmail.com> wrote: >>> > I don't think LP can solve it. We are to maximize c, not minimize c. >>> > The formulas we have are: >>> > >>> > |x(i)-x(j)| >= c for all i and j >>> > r1(i) <= x(i) <= r2(i) for all i >>> > The first inequality actually is combination of two linear equalities: >>> x(i) >>> > - x(j) >= c or x(i) - x(j) <= -c. Notice the relation of the two is >>> "or", >>> > and we cannot put them together to get a system of linear inequalities. >>> > 2009/10/21 Dave <dave_and_da...@juno.com> >>> > >>> > >>> > >>> > >>> > >>> > >>> > >>> > > This is a linear programming problem. The way you formulate the >>> > > problem depends on the capabilities of the linear programming >>> software >>> > > you have. >>> > >>> > > Basically, you want to >>> > > minimize c >>> > > by finding x(1) to x(n) such that >>> > >>> > > |x(i)-x(j)| <= c for all i and j >>> > > r1(i) <= x(i) <= r2(i) for all i >>> > >>> > > Dave >>> > >>> > > On Oct 5, 9:22 am, monty 1987 <1986mo...@gmail.com> wrote: >>> > > > We have to locate n points on the x-axis >>> > > > For each point xi >>> > > > the x co-ordinate of it lies between a >>> range >>> > > > [r1i,r2i] >>> > > > Now we have to decide the location of points such that >>> > > > minimum { distance between any two points } is maximum. >>> > >>> > > > Any answer is welcomed. >>> > >>> > -- >>> > 此致 >>> > 敬礼! >>> > >>> > 林夏祥- Hide quoted text - >>> > >>> > - Show quoted text - >>> >> >> >> >> -- >> 此致 >> 敬礼! >> >> 林夏祥 >> >> >> >> --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---