<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.6000.16640" name=GENERATOR></HEAD>
<BODY>
<DIV dir=ltr align=left><SPAN class=284252920-01052008><FONT face=Arial
color=#0000ff size=2>Mohammad Hossein Bateni will present his research
seminar/general exam on </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=284252920-01052008><FONT face=Arial
color=#0000ff size=2>Thursday May 8 at 3PM in room 402. The member of his
committee are: </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=284252920-01052008><FONT face=Arial
color=#0000ff size=2>Moses Charikar (advisor), Bob Tarjan, and Sanjeev
Arora. Everyone is </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=284252920-01052008><FONT face=Arial
color=#0000ff size=2>invited to attend his talk and those faculty wishing to
remain for the oral </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=284252920-01052008><FONT face=Arial
color=#0000ff size=2>exam following are welcome to do so. His abstract and
reading list </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=284252920-01052008><FONT face=Arial
color=#0000ff size=2>follow below.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=284252920-01052008><FONT face=Arial
color=#0000ff
size=2>-----------------------------</FONT></SPAN></DIV><BR>------------Abstract----------
<DIV>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\}$.<BR><BR>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.<BR><BR>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. <I><BR></I>
<DIV>========== <BR><BR></DIV>And this is my reading
list.<BR><BR>------------Books------------------<BR>(1) Algorithm Design by
<I>Jon Kleinberg and Eva Tardos</I>. The whole book.<BR>(2) Approximation
Algorithms by <I>Vijay V. Vazirani</I>. Chapters 1-17.<BR><PRE style="MARGIN-LEFT: 40px">1 Introduction<BR>Part I. Combinatorial Algorithms<BR>2 Set Cover<BR>3 Steiner Tree and TSP<BR>4 Multiway Cut and k-Cut<BR>5 k-Center<BR>6 Feedback Vertex Set<BR>7 Shortest Superstring<BR>
8 Knapsack<BR>9 Bin Packing<BR>10 Minimum Makespan Scheduling<BR>11 Euclidean TSP<BR>Part II. LP-Based Algorithms<BR>12 Introduction to LP-Duality 93<BR>13 Set Cover via Dual Fitting<BR>14 Rounding Applied to Set Cover<BR>
15 Set Cover via the Primal-Dual Schema<BR>16 Maximum Satisfiability<BR>17 Scheduling on Unrelated Parallel Machines</PRE>(3)
Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan. Chapters
1-6.<BR><PRE style="MARGIN-LEFT: 40px">1 Introduction<BR>2 Game-Theoretic Techniques<BR>3 Moments and Deviations<BR>4 Tail Inequalities<BR>5 The Probabilistic Method<BR>6 Markov Chains and Random Walks</PRE><BR>----------Research
Papers-------------<BR>[1] Noga Alon and Yossi Azar and Gerhard J. Woeginger and
Tal Yadid. <I>Approximation schemes for scheduling on parallel machines</I>.
Journal of Computing, 1(1):55-66, 1998.<BR>[2] Arash Asadpour and Amin Saberi.
<I>An approximation algorithm for max-min fair allocation of indivisible
goods</I>. STOC 2007.<BR>[3] Nikhil Bansal and Maxim Sviridenko. <I>The santa
claus problem</I>. STOC 2006.<BR>[4] Ivona Bezakova and Varsha Dani.
<I>Allocating indivisible goods</I>. SIGecom Exchange, 5(3):11-18, 2005.<BR>[5]
Tomas Ebenlendr, Marek Krcal and Jiri Sgall. <I>Graph balancing: A special case
of scheduling unrelated parallel machines</I>. SODA 2008.<BR>[6] Uriel Feige.
<I>On allocations that maximize fairness</I>. SODA 2008.<BR>[7] Subhash Khot and
Ashok Kumar Ponnunswami. <SPAN style="FONT-STYLE: italic">Approximation
algorithms for the max-min allocation problem</SPAN>. APPROX 2007.<BR
clear=all>[8] David Golovin. <I>Max-min fair allocation of indivisible
goods</I>. Technical Report, Carnegie Mellon University, CMU-CS-05-144,
2005.<BR>[9] Jan Karel Lenstra, David B. Shmoys and Eva Tardos. <I>Approximation
algorithms for scheduling unrelated parallel machines</I>. Mathematical
Programming, 46:259-271, 1990.<BR>[10] David B. Shmoys and Eva Tardos. <SPAN
style="FONT-STYLE: italic">An approximation algorithm for the generalized
assignment problem</SPAN>. Mathematical Programming 62:461-474,
1993.<BR>=============================<BR><BR></DIV></BODY></HTML>