>  we have many machines connected to each other. However, administering these
> machines is a great hassle. That is because a machine can be administered
> only by a machine connected directly to it (a machine that is an
> administrator can administrator itself). So, the system administrators have
> decided to convert some of the machines in the network to "administrative
> machines". However, the cost of converting a machine to an administrative
> machine is $100, which is pretty high. So, the system administrators
> approach you to help them out.

> You will be given a list of machines which have a direct connection between
> them. You need to compute the least cost that the company needs to incur so
> that every machine in the final network is administrable by at least one of
> the machines converted to administrative machines.

> You are given as input the node pairs which are connected to each other. You
> are supposed to find the least amount of money in dollars that you need to
> spend so that every machine in the network is administered by at least one
> administrator machine.

On Wed, Jul 1, 2009 at 9:24 PM, Dave <dave_and_da...@juno.com> wrote:

> This can be formulated as a 0-1 integer programming problem.

> Define the matrix A such that a(i,j) = 1 if machine i is connected to
> machine j, and = 0 otherwise (with the interpretation that every
> machine is connected to itself).

> Let x be a vector whose elements are in the set {0, 1}, where x(j) = 0
> means that machine j is not an administrative machine and x(j) = 1
> means that it is.

> Then the 0-1 integer programming problem is:

> detemine x to
> minimize sum{ x(i) }
> subject to [A*x](i) >= 1.

> The inequality above means that the i'th component of the matrix-
> vector product A*x is >= 1. It simply means that machine i is
> connected to at least one administrative machine.

> You should be able to find software or algorithms to solve 0-1 integer
> programming problems.

> Dave

> On Jul 1, 7:47 am, priya k <priya.annau...@gmail.com> wrote:
> >  we have many machines connected to each other. However, administering
> these
> > machines is a great hassle. That is because a machine can be administered
> > only by a machine connected directly to it (a machine that is an
> > administrator can administrator itself). So, the system administrators
> have
> > decided to convert some of the machines in the network to "administrative
> > machines". However, the cost of converting a machine to an administrative
> > machine is $100, which is pretty high. So, the system administrators
> > approach you to help them out.

> > You will be given a list of machines which have a direct connection
> between
> > them. You need to compute the least cost that the company needs to incur
> so
> > that every machine in the final network is administrable by at least one
> of
> > the machines converted to administrative machines.

> > You are given as input the node pairs which are connected to each other.
> You
> > are supposed to find the least amount of money in dollars that you need
> to
> > spend so that every machine in the network is administered by at least
> one
> > administrator machine.