Author Topic: Development question  (Read 1426 times)

Offline Higgins the genius

  • VIP
  • Superstar
  • *
  • Posts: 225
  • Reputation: 337
Development question
« on: July 26, 2018, 03:13:17 PM »
 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?

Online RV Pundit

  • Moderator
  • Enigma
  • *
  • Posts: 38325
  • Reputation: 1074446
Re: Development question
« Reply #1 on: July 26, 2018, 03:53:03 PM »
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?

Online RV Pundit

  • Moderator
  • Enigma
  • *
  • Posts: 38325
  • Reputation: 1074446
Re: Development question
« Reply #2 on: July 26, 2018, 03:54:03 PM »
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.

Offline Higgins the genius

  • VIP
  • Superstar
  • *
  • Posts: 225
  • Reputation: 337
Re: Development question
« Reply #3 on: July 26, 2018, 04:21:27 PM »
Now say it in simpler terms!

Online RV Pundit

  • Moderator
  • Enigma
  • *
  • Posts: 38325
  • Reputation: 1074446
Re: Development question
« Reply #4 on: July 26, 2018, 04:53:27 PM »
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!

Offline Kim Jong-Un's Pajama Pants

  • Moderator
  • Enigma
  • *
  • Posts: 8783
  • Reputation: 106254
  • An oryctolagus cuniculus is feeding on my couch
Re: Development question
« Reply #5 on: July 26, 2018, 05:00:37 PM »
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.
"I freed a thousand slaves.  I could have freed a thousand more if only they knew they were slaves."

Harriet Tubman

Offline gout

  • VIP
  • Enigma
  • *
  • Posts: 4193
  • Reputation: 1374
Re: Development question
« Reply #6 on: July 27, 2018, 12:36:17 PM »
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.
Government, even in its best state, is but a necessary evil; in its worst state, an intolerable one ~ Thomas Paine

Offline veritas

  • Enigma
  • *
  • Posts: 3353
  • Reputation: 4790
Re: Development question
« Reply #7 on: July 27, 2018, 01:05:29 PM »
Build more highways with tolls to pay for upkeep.