[talks] M Bateni general exam

[Melissa M Lawson]

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.
=============================


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20080501/21afc200/attachment.html>