title: Generalized Load Balancing (GLB) using Linear Programming (LP)
body: <p>In one of my project - I have a scenario where I need to implement an algorithm capable of doing load balancing. Now, unlike the general load balancing problem present in CS theory (which is NP hard) - where the task is to allocate M loads in N servers (M >> N), such that the maximum load in any one server is minimized, the case that I am dealing with is a little more generic. In my case, the load balancing problem is more generic in the sense - it has more constraints in the form that - such and such job can only be assigned to such an such server (lets say for example job M_{i} has some special security requirements and hence can be allocated/executed only on secure server N_{j}.</p>
  
  <p>Now I looked at the Kleinberg/Tardos book and I found a section (11.7) on the more generic load balancing problem (load balancing with constraints) and I found that this problem is an exact match for the situation I am in. The Generic Load Balancing problem has been converted from IP to LP taking advantage of the fact that LP can result in fractional assignment of jobs to machines which has later been rounded off adding an additional O(MN) time to the process. This approximation solution has then been shown to be within a factor of 2 times from the minimum possible. </p>
  
  <p>Can someone point me to some C/Java/Python/MATLAB code where this algorithm has been implemented? As KL book hardly gives any examples or sample pseudo/actual code, it is hard to get the algorithm internalized completely sometimes. Also as for the linear programming part of the problem - what kind of an implementation is suitable for it - Simplex/Interior Point? How much difference will it make when complexity from this LP part is added to the problem (to the fractional re-assignment part)? Unfortunately, the KL book is not very thorough in these aspects.</p>
  
  <p>Some sample C/Java/Python/MATLAB code (or pointers to code) showing some real implementation of this complete algorithm would be greatly helpful.</p>
  
  <p>Edit: The original paper is "David B. Shmoys, Éva Tardos: An approximation algorithm for the generalized assignment problem. Math. Program. 62: 461-474 (1993)"   </p>