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
-~----------~----~----~----~------~----~------~--~---
