Message from discussion
Algo Question
MIME-Version: 1.0
Received: by 10.151.133.5 with SMTP id k5mr1495522ybn.2.1246463660559; Wed, 01
Jul 2009 08:54:20 -0700 (PDT)
Date: Wed, 1 Jul 2009 08:54:20 -0700 (PDT)
In-Reply-To: <7b16a2f60907010547k3467b1f3i8b6a8833cc7e7980@mail.gmail.com>
X-IP: 76.251.38.87
References: <7b16a2f60907010547k3467b1f3i8b6a8833cc7e7980@mail.gmail.com>
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; Ads
Filter 1.2.0.72; GTB6; .NET CLR 1.0.3705; .NET CLR 1.1.4322; Media Center PC
4.0; .NET CLR 2.0.50727; .NET CLR 3.0.04506.648; .NET CLR 3.5.21022; .NET CLR
3.0.4506.2152; .NET CLR 3.5.30729; OfficeLiveConnector.1.3;
OfficeLivePatch.0.0),gzip(gfe),gzip(gfe)
Message-ID: <7b3d0102-b580-42b0-b116-9602045aba10@h8g2000yqm.googlegroups.com>
Subject: Re: Algo Question
From: Dave <dave_and_da...@Juno.com>
To: Algorithm Geeks <algogeeks@googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
This can be formulated as a 0-1 integer programming problem.
Define the matrix A such that a(i,j) =3D 1 if machine i is connected to
machine j, and =3D 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) =3D 0
means that machine j is not an administrative machine and x(j) =3D 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) >=3D 1.
The inequality above means that the i'th component of the matrix-
vector product A*x is >=3D 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=A0am, priya k <priya.annau...@gmail.com> wrote:
> =A0we 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 ha=
ve
> 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 betwe=
en
> 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 t=
o
> spend so that every machine in the network is administered by at least on=
e
|
