Convergence Time to Nash Equilibria in Load Balancing Systems
We study the number of steps required to reach a pure Nash Equilibrium
in a load balancing scenario where each job behaves selfishly and
attempts to migrate to a machine which will minimize its cost.
We consider variety of load balancing models, including identical,
restricted, related and unrelated machines. Our results have a crucial
dependence on the allowable weights assigned to jobs. We consider
arbitrary weights, integer weights, K distinct weights and identical
(unit) weights. We look both at an arbitrary schedule (where the only
restriction is that a job migrates to a machine which lowers its cost)
and specific efficient schedulers (such as allowing the largest weight
job to move first).
This is a joint work with Eyal Even-Dar and Alex Kesselman.
Quasi-Ramanujan 2-lifts and a converse to the Expander Mixing Lemma
Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n
vertices, with a covering map p:H -> G. It turns out that all
eigenvalues of G are also eigenvalues of H. In addition, H has n ``new''
eigenvalues.
We show that every graph of maximal degree d has a 2-lift such that all
``new'' eigenvalues are in the range $[-c \sqrt{d \log^3d}, c \sqrt{d
\log^3d}]$ for some constant $c$. This leads to a polynomial time
algorithm for constructing arbitrarily large d-regular graphs, with
second eigenvalue $O(\sqrt{d \log3 d})$.
The proof uses the following lemma:
Let A be a real symmetric matrix with zero on the diagonal, such that
the $l_1$ norm of each row in A is at most d, and for every $x,y \in
\{0,1\}^n$ with disjoint support, |xAy|/(||x|| ||y||) < f. Then the
spectral radius of A is $O(f (\log(d/f) + 1))$.
An interesting consequence of this lemma is a converse to the Expander
Mixing Lemma.
Joint work with Nati Linial.
A New algorithm for Knapsack
We present a new algorithm for solving all instances of the
Knapsack problem ( i.e. all knapsack capacities, b=1,2, ...M.
and n items. M is an arbitary large number or infinity ).
The time complexity is O ( ( n^2) w log (nw) ),where w is the
weight of the best item. The algorithm is similar to the shortest
path algorithm. Two open topics will be discussed.
This work is joint work with M.T. Shing and L. Landa.