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