Development question

[Higgins the genius]

• Tweet

 If  you were working on a revenue sharing formula for (say) roads, do you give a county like (say) Nairobu more funds to maintain their roads (they have the highest number of kilometers of roads) or do you give Turkana County (the largest County by land mass) more funds to construct new roads to increase access?

[RV Pundit]

NP-hardness of resource allocation problem

I am tring to prove the NP-completeness of the following Binary Integer Linear Program (BILP):

min?i?jxijsubject to?jrijxij?R,  ?  i?[L]?ixij?1,  ?  j?[N]xij?{0,1}.
This a resource allocation problem in which I am trying to minimize the number of resources utilized while guaranteeing a certain minimum rate for all entities.

xij is an indicator random variable that indicates whether or not a resource j is allocated to an entity i. The first set of constraints impose a minimum amount of resource guaranteed for each entity. rij is the rate that an entity i can get in a resource element j. The second set of constraints ensure that a resource is not allocated to multiple users as sharing of resources is not possible in this problem. [L] is the set of user entities and [N] is the set of resources here.

I have tried looking at several covering problems like set cover that look like this but the second set of constraints seem to be falling out of place every time. Can anyone suggest an existing NP complete problem that can be reduced to this problem to prove it's NP-completeness?

[RV Pundit]

The Answer
If you set N=2, and ri0=ri1=ri for each i, and set R=12?i?[L]ri, then the feasibility of this linear program is precisely the Partition problem. Namely, a feasible solution chooses for each i?[L] either xi0 or xi1, so that summing the ri for those i for which you chose xi0 equals R, and similarly for 1.

[Higgins the genius]

Now say it in simpler terms!

[RV Pundit]

It's a very hard question with no simple answers. I think solution is more devolution or more fedaralism - so Turkana can make their own decision just like Nairobeans. Maybe roads are not turkana top priority as it is Nairobi's?

Now say it in simpler terms!

[Kim Jong-Un's Pajama Pants]

If  you were working on a revenue sharing formula for (say) roads, do you give a county like (say) Nairobu more funds to maintain their roads (they have the highest number of kilometers of roads) or do you give Turkana County (the largest County by land mass) more funds to construct new roads to increase access?

It depends on many things.  Natural resources, human resources etc.  Nairobi obviously has more maintenance requirements.  Turkana might need to be developed to extract oil.

[gout]

Development/Localized challenges only require commonsense and some willingness to help by those controlling the resources.

If Turkana/NEP and coastal leaders were quite genuine they would invest in water, health or say housing technologies which enables better air conditioning rather than roads as would be the case in Nairobi or Central Kenya where movement of people is a key economic/social concern.

[veritas]

Build more highways with tolls to pay for upkeep.