Mohammad Hossein Bateni will present his research seminar/general exam on Thursday May 8 at 3PM in room 402. The member of his committee are: Moses Charikar (advisor), Bob Tarjan, and Sanjeev Arora. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----------------------------- ------------Abstract---------- Consider a resource allocation problem where we have a set of $m$ indivisible items to be distributed amongst $n$ players, each item going to exactly one person. The value of item $j$ for player $i$ is given by a nonnegative quantity $p_{ij}$, and let us assume that the values for sets of items are additive. The problem of minimizing the maximum value received by a player corresponds to the classic makespan minimization problem. Recently, this problem has received renewed attention under the MaxMin objective function, the goal being to find an allocation that maximizes the minimum value received by a player. There is a large gap in our current understanding of this problem. The best known algorithm achieves a $\tilde{O}(\sqrt{n})$ approximation ratio, but only a factor $2$ hardness result is known. Better algorithms are known when each item has an intrinsic value and a player is only interested in a subset of items, i.e., $p_{ij} \in \{0,p_j\}$. In this work, we consider the bounded-degree case when each item has nonzero value for at most $B$ players. We show that $B = 3$ is as hard as the general problem. We give a factor $4$ approximation algorithm when $B=2$. This is the only case we know of when items can have different nonzero valuations that admits better than a $\tilde{O}(\sqrt{n})$-approximation. The degree two case remains factor $2$ inapproximable, even if each item has the same value for both players interested in it. We also give a simpler LP that is equivalent in power to the Configuration LP that has been instrumental in recent progress on the problem. We identify a non-trivial special case where the Configuration LP still has a large $n^{\Omega(1)}$ integrality gap, but for which we are able to get a polylogarithmic approximation ratio via a careful strengthening and rounding of the LP. ========== And this is my reading list. ------------Books------------------ (1) Algorithm Design by Jon Kleinberg and Eva Tardos. The whole book. (2) Approximation Algorithms by Vijay V. Vazirani. Chapters 1-17. 1 Introduction Part I. Combinatorial Algorithms 2 Set Cover 3 Steiner Tree and TSP 4 Multiway Cut and k-Cut 5 k-Center 6 Feedback Vertex Set 7 Shortest Superstring 8 Knapsack 9 Bin Packing 10 Minimum Makespan Scheduling 11 Euclidean TSP Part II. LP-Based Algorithms 12 Introduction to LP-Duality 93 13 Set Cover via Dual Fitting 14 Rounding Applied to Set Cover 15 Set Cover via the Primal-Dual Schema 16 Maximum Satisfiability 17 Scheduling on Unrelated Parallel Machines (3) Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan. Chapters 1-6. 1 Introduction 2 Game-Theoretic Techniques 3 Moments and Deviations 4 Tail Inequalities 5 The Probabilistic Method 6 Markov Chains and Random Walks ----------Research Papers------------- [1] Noga Alon and Yossi Azar and Gerhard J. Woeginger and Tal Yadid. Approximation schemes for scheduling on parallel machines. Journal of Computing, 1(1):55-66, 1998. [2] Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. STOC 2007. [3] Nikhil Bansal and Maxim Sviridenko. The santa claus problem. STOC 2006. [4] Ivona Bezakova and Varsha Dani. Allocating indivisible goods. SIGecom Exchange, 5(3):11-18, 2005. [5] Tomas Ebenlendr, Marek Krcal and Jiri Sgall. Graph balancing: A special case of scheduling unrelated parallel machines. SODA 2008. [6] Uriel Feige. On allocations that maximize fairness. SODA 2008. [7] Subhash Khot and Ashok Kumar Ponnunswami. Approximation algorithms for the max-min allocation problem. APPROX 2007. [8] David Golovin. Max-min fair allocation of indivisible goods. Technical Report, Carnegie Mellon University, CMU-CS-05-144, 2005. [9] Jan Karel Lenstra, David B. Shmoys and Eva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46:259-271, 1990. [10] David B. Shmoys and Eva Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming 62:461-474, 1993. =============================