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