• Stochastic Network Theory
  
• Load Balancing
• Random Assignment Problem
• Miscellaneous
  

Stochastic Network Theory:

Load Balancing:
 

•  Load balancing has been a classical problem. The basic version of the problem is: N balls are to be loaded into N bins such that maximum load among N bins is minimized. In a centralized environment, optimal policy is to assign one ball to each bin. However, in a distributed environment it is expensive to implement this policy as one would have to query bins until one finds an empty one every instance a ball is being loaded.  One simple strategy is: each ball goes to a randomly chosen  bin. It is known that this strategy has maximum load of log N/log log N with high probability. Instead, if each ball chooses d (>1) bins at random and loads least loaded of them, then the maximum load goes down to log log N/lod d with high probability. We introduce the idea of 'memory' : we re-use the best few random choices from previous time and  we show that remembering these choices improves performance substantially.

Random Assignment Problem:

• The Random Assignment Problem has been of interest for quite a few years. The Assignment Problem is as follows: There are N jobs and N machines and there is a positive cost associated with performing a given job on a given machine. Now, from the complete bi-partite graph of N^2 costs, the problem is to determine which assignment (permutation) leads to the lowest cost. The Random Assignment Problem is a variation on this problem in which the costs are random variables. In this problem, one is concerned about the distribution of the random variable corresponding to the minimum cost for each realization. Using LP duality and other techniques, mathematicians were able to show that when the costs have a density that takes value 1 at the origin, the limiting value of the expected cost of the minimuam assignment lied between 1.51 and 1.92. However using techniques from Spin Glass thory, Parisi argued that the limiting value is precisely pi^2/6 ! This was rigorously established using ideas from weak convergence by Aldous. Parisi had also made a conjecture for finite N when the costs were independent exponential random variables of mean 1.  He conjectured that the expected value of the minimum cost matching was in fact 1/1^2 + 1/2^2 + ... + 1/N^2. Coppersmith and Sorkin extended these conjectures for minimum k-matchings in a rectangular matrix. 

Miscellaneous:

• This section contains work that are results of either temporary infatuation with a field or class projects or other esoteric interests that are restricted to just a single member of our group.
  

ISNL
 

Copyright © 2003 Stanford University Last modified: 8 Sept 2003 Send comments and questions to mchandra@stanford.edu