New York Area Theory Day
Organized by: NYU/IBM/Columbia
External sponsorship by: Google
Friday, December 5, 2008
The Theory Day will be held at Courant Institute of Mathematical Sciences,
New York University, 251 Mercer Street, Auditorium 109, New York.
Program
9:30 - 10:00 Coffee and bagels
10:00 - 10:55 Prof. Assaf Naor
Approximate Kernel Clustering
10:55 - 11:05 Short break
11:05 - 12:00 Prof. Joe Mitchell
Approximation Algorithms for some Geometric Coverage
and Connectivity Problems
12:00 - 2:00 Lunch break
2:00 - 2:55 Dr. Jonathan Feldman
A Truthful Mechanism for Offline Ad Slot Scheduling
2:55 - 3:15 Coffee break
3:15 - 4:10 Prof. Yishay Mansour
Regret Minimization for Global Cost Functions
with Applications to Job Scheduling
For directions, please see http://www.cims.nyu.edu/direct.html and
http://cs.nyu.edu/csweb/Location/directions.html (building 46)
To subscribe to our mailing list, follow instructions at
http://www.cs.nyu.edu/mailman/listinfo/theory-ny
Organizers:
Yevgeniy Dodis dodis@cs.nyu.edu
Tal Rabin talr@watson.ibm.com
Baruch Schieber sbar@watson.ibm.com
Rocco Servedio rocco@cs.columbia.edu
=======================================================================
Prof. Assaf Naor
(New York University)
Approximate Kernel Clustering
In the kernel clustering problem we are given a large n times n
positive semi-definite matrix A=(a_{ij}) with \sum_{i,j=1}^n a_{ij}=0
and a small k times k positive semi-definite matrix B=(b_{ij}). The
goal is to find a partition S_1,...,S_k of {1,...n} which
maximizes the quantity
\sum_{i,j=1}^k (\sum_{(p,q)\in S_i\times S_j} a_{pq}) b_{ij}.
We study the computational complexity of this generic clustering
problem which originates in the theory of machine learning. We design
a constant factor polynomial time approximation algorithm for this
problem, answering a question posed by Song, Smola, Gretton and
Borgwardt. In some cases we manage to compute the sharp approximation
threshold for this problem assuming the Unique Games Conjecture
(UGC). In particular, when B is the 3 times 3 identity matrix the UGC
hardness threshold of this problem is exactly 16*pi/27. We present and
study a geometric conjecture of independent interest which we show
would imply that the UGC threshold when B is the k times k identity
matrix is (8*pi/9)*(1-1/k) for every k >= 3.
Joint work with Subhash Khot.
-------------------------------------------------------------------------
Prof. Joe Mitchell
(Stony Brook University)
Approximation Algorithms for some
Geometric Coverage and Connectivity Problems
We examine a variety of geometric optimization problems. We describe
some recent progress in improved approximations algorithms for several
of these problems, including the TSP with neighborhoods, relay
placement in sensor networks, and visibility/sensor coverage. We
highlight many open problems.
-------------------------------------------------------------------------
Dr. Jonathan Feldman
(Google)
A Truthful Mechanism for Offline Ad Slot Scheduling
Targeted advertising on web pages is an increasingly important
advertising medium, attracting large numbers of advertisers and users.
One popular method for assigning ads to various slots on a page (for
example the slots along side web search results) is via a real-time
auction among advertisers who have placed standing bids for clicks.
These "position auctions" have been studied from a game-theoretic
point of view and are now well understood as a single-shot game.
However, since web pages are visited repeatedly over time, there are
global phenomena at play such as supply estimates and budget
constraints that are not modeled by this analysis.
We formulate the "Offline Ad Slot Scheduling" problem, where
advertisers are scheduled beforehand to slots on a web page for
portions of the day. Advertisers specify a daily budget constraint,
as well as a per-click bid, and may not be assigned to more than one
slot on the page during any given time period. We give a scheduling
algorithm and a pricing method that amount to a truthful mechanism
under the utility model where bidders try to maximize their clicks,
subject to their personal constraints. In addition, we show that the
revenue-maximizing schedule is not truthful, but has a Nash
equilibrium whose outcome is identical to our mechanism. Our
mechanism employs a descending-price auction that maintains a solution
to a machine scheduling problem whose job lengths depend on the price.
Joint work with Muthu Muthukrishnan, Eddie Nikolova and Martin Pal.
-------------------------------------------------------------------------
Prof. Yishay Mansour
(Google and Tel Aviv University)
Regret Minimization for Global Cost Functions
with Applications to Job Scheduling
We consider standard regret minimization setting where at each time step the
decision maker has to choose a distribution over $k$ alternatives, and then
observes the loss of each alternative. The setting is very similar to the
classical online job scheduling setting with three major differences:
(1) Information model: in the regret minimization setting losses are only
observed after the actions (assigning the job to a machine) is performed and
not observed before the action selection, as assumed in the classical online
job scheduling setting,
(2) The comparison class: in regret minimization the comparison class is the
best static algorithm (i.e., distribution over alternatives) and not the
optimal offline solution.
(3) Performance measure: In regret minimization we measure the additive
difference to the optimal solution in the comparison class, in contrast to the
ratio used in online job scheduling setting.
Motivated by load balancing and job scheduling, we consider a global cost
function (over the losses incur by each alternative/machine), rather than
simply a summation of the instantaneous losses as done traditionally in regret
minimization. Such global cost functions include the makespan (the maximum over
the alternatives/machines) and the $L_d$ norm (over the alternatives/machines).
The major contribution of this work is to design a novel regret minimization
algorithm based on calibration that guarantees a vanishing average regret,
where the regret is measured with respect to the best static decision maker,
who selects the same distribution over alternatives at every time step. Our
results hold for a wide class of global cost functions. which include the
makespan and the $L_d$ norms, for $d>1$. In contrast, we show that for concave
global cost functions, such as $L_d$ norms for $d<1$, the worst-case average
regret does not vanish.
In addition to the general calibration based algorithm, we provide simple and
efficient algorithms for special interesting cases.
This is a joint work with Eyal Even-Dar and Shie Mannor.
-----------------------------------------------------------------------