- You are here:
- GT Home
- Home
- News & Events

Series: ACO Seminar

I will present two related 30-minute talks.
Title 1: Generalized Online Matching with Concave Utilities
Abstract 1: In this talk we consider a search engine's ad matching
problem with soft budget. In this problem, there are two sides. One side
is ad slots and the other is advertisers. Currently advertisers are
modeled to have hard budget, i.e., they have full utility for ad slots
until they reach their budget, and at that point they can't be assigned
any more ad-slots. Mehta-Saberi-Vazirani-Vazirani and Buchbinder-J-Naor
gave a 1-1/e approximation algorithm for this problem, the latter had a
traditional primal-dual analysis of the algorithm.
In this talk, we consider a situation when the budgets are soft. This is
a natural situation if one models that the cost of capital is convex or
the amount of risk is convex. Having soft budget makes the linear
programming relaxation as a more general convex programming relaxation.
We still adapt the primal-dual schema to this convex program using an
elementary notion of convex duality. The approximation factor is then
described as a first order non-linear differential equation, which has
at least 1-1/e as its solution. In many cases one can solve these
differential equations analytically and in some cases numerically to get
algorithms with factor better than 1-1/e.
Based on two separate joint works, one with Niv Buchbinder and Seffi Naor, and the other with Nikhil Devanur.
Title 2: Understanding Karp-Vazirani-Vazirani's Online Matching (1990) via Randomized Primal-Dual.
Abstract 2: KVV online matching algorithm is one of the most beautiful
online algorithms. The algorithm is simple though its analysis is not
equally simple. Some simpler version of analysis are developed over the
last few years. Though, a mathematical curiosity still remains of
understanding what is happening behind the curtains, which has made
extending the KVV algorithm hard to apply to other problems, or even
applying to the more general versions of online matching itself.
In this talk I will present one possibility of lifting the curtains. We
develop a randomized version of Primal-Dual schema and redevelop KVV
algorithm within this framework. I will then show how this framework
makes extending KVV algorithm to vertex weighted version essentially
trivial, which is currently done through a lot of hard work in a
brilliant paper of Aggarwal-Goel-Karande-Mehta (2010).
Randomized version of Primal-Dual schema was also a missing technique
from our toolbox of algorithmic techniques. So this talk also fills that
gap.

Series: ACO Seminar

Why did kamikaze pilots wear helmets?
Why does glue not stick to the inside of the bottle?
Why is lemonade made with artificial flavor but dishwashing liquid made with
real lemons?
How can I avoid traffic jams and be paid for it?
While the first three are some of life's enduring questions, the fourth
is the subject of a traffic decongestion research project at Stanford
University. In this talk, I will briefly describe this project and, more
generally, discuss incentive mechanisms for Societal Networks---
networks which are vital for a society's functioning; for example,
transportation, energy, healthcare and waste management. I will
talk about incentive mechanisms and experiments for reducing
road congestion, pollution and energy use, and for improving
"wellness" and good driving habits. Some salient themes are:
using low-cost sensing technology to make societal networks much
more efficient, using price as a signal to co-ordinate individual
behavior, and intelligently "throwing money at problems".

Series: ACO Seminar

Given data drawn from a mixture of multivariate Gaussians, a basic
problem is to accurately estimate the mixture parameters. This
problem has a rich history of study in both statistics and, more
recently, in CS Theory and Machine Learning. We present a polynomial time
algorithm for this problem (running time, and data requirement
polynomial in the dimension and the inverse of the desired accuracy),
with provably minimal assumptions on the Gaussians. Prior to this
work, it was unresolved whether such an algorithm was even information
theoretically possible (ie, whether a polynomial amount of data, and
unbounded computational power sufficed). One component of the proof
is showing that noisy estimates of the low-order moments of a
1-dimensional mixture suffice to recover accurate estimates of the
mixture parameters, as conjectured by Pearson (1894), and in fact
these estimates converge at an inverse polynomial rate. The second
component of the proof is a dimension-reduction argument for how one
can piece together information from different 1-dimensional
projections to yield accurate parameters.

Series: ACO Seminar

The spectacular success of search and display advertising -- to
businesses and search engine companies -- and its huge growth
potential has attracted the attention of researchers from many aspects
of computer science. Since a core problem in this area is that of
effective ad allocation, an inherently algorithmic and game-theoretic
question, numerous theoreticians have worked in this area in recent
years. Ad allocation involves matching ad slots to advertisers, under
demand and supply constraints. In short, the better the matching, the
more efficient the market.
Interestingly, the seminal work on online matching, by Karp, Vazirani
and Vazirani, was done over two decades ago, well before the advent of
the Internet economy! In this talk, I will give an overview of several
key algorithmic papers in this area, starting with its purely academic
beginnings, to papers that actually address the Adwords problem. The
elegant -- and deep -- theory behind these algorithms involves new
combinatorial, probabilistic and linear programming techniques.
Besides the classic KVV paper (STOC 1990), this talk will refer to
several papers with my co-authors:
Mehta, Saberi, Vazirani, Vazirani (FOCS 05, J. ACM 07),
Goel, Mehta (SODA 08),
Feldman, Mehta, Mirrokni, Muthukrishnan (FOCS 09),
Aggarwal, Goel, Karande, Mehta (SODA 10),
Karande, Mehta, Tripathi (STOC 11).

Series: ACO Seminar

A well-known conjecture of Lovasz and Plummer asserts that the number
of perfect matchings in 2-edge-connected cubic graph is exponential in
the number of vertices. Voorhoeve has shown in 1979 that the
conjecture holds for bipartite graphs, and Chudnovsky and Seymour have
recently shown that it holds for planar graphs. In general case,
however, the best known lower bound has been until now barely
super-linear.
In this talk we sketch a proof of the conjecture. The main
non-elementary ingredient of the proof is Edmonds' perfect matching
polytope theorem.
This is joint work with Louis Esperet, Frantisek Kardos, Andrew King
and Daniel Kral.

Series: ACO Seminar

A signed graph is a pair (G, \Sigma) where G is a graph and \Sigma is a subset of the edges of G. A cycle C in G is even (resp. odd) if E(C) \cap \Sigma is even (resp. odd). A blocking pair in a signed graph is a pair of vertices {x, y} such that every odd cycle in (G, \Sigma) intersects at least one of the vertices x and y. Blocking pairs arise in a natural way in the study of even cycle matroids on signed graphs as well as signed graphs with no odd K_5 minor. In this article, we characterize when the blocking pairs of a signed graph can be represented by 2-cuts in an auxiliary graph. We discuss the relevance of this result to the problem of characterizing signed graphs with no odd K_5 minor and determing when two signed graphs represent the same even cycle matroid. This is joint work with Irene Pivotto and Paul Wollan.

Series: ACO Seminar

We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this talk, which is based on a survey with Benny Sudakov, we discuss some of these applications.

Series: ACO Seminar

Hosted by Vijay Vazirani

I will talk about new results on convex programs and distributed algorithms for Fisher markets with linear and spending constraint utilities. In particular: (i) show a new convex program for the linear utilities case of Fisher markets. This program easily extends to the case of spending constraint utilities as well, thus resolving an open question raised by Vazirani; (ii) show that the gradient descent algorithm with respect to a Bregman divergence converges with rate O(1/t) under a condition that is weaker than having Lipschitz continuous gradient (which is the usual assumption in the optimization literature for obtaining the same rate); (iii) show that the Proportional Response dynamics recently introduced by Zhang is equivalent to a gradient descent algorithm for solving the new convex program. This insight also gives us better convergence rates, and helps us generalize it to spending constraint utilities.

Series: ACO Seminar

We look at problems of scheduling jobs to machines when the processing time of a job is machine dependent. Common objectives in this framework are to minimize the maximum load on a machine, or to minimize the average completion time of jobs. These are well-studied problems. We consider the related problem of trying to select a subset of machines to use to minimize machine costs subject to bounds on the maximum load or average completion time of the corresponding schedule. These problems are NP-hard and include set-cover as a special case. Thus we focus on approximation algorithms and get tight, or almost tight approximation guarantees. A key part of our results depends on showing the submodularity of the objective of a related optimization problem.

Series: ACO Seminar

The class of random regular graphs has been the focus of extensive study highlighting
the excellent expansion properties of its typical instance. For instance, it is well
known that almost every regular graph of fixed degree is essentially Ramanujan, and
understanding this class of graphs sheds light on the general behavior of expanders.
In this talk we will present several recent results on random regular graphs,
focusing on the interplay between their spectrum and geometry.
We will first discuss the relation between spectral properties and the abrupt
convergence of the simple random walk to equilibrium, derived from precise
asymptotics of the number of paths between vertices. Following the study of the graph
geometry we proceed to its random perturbation via exponential weights on the edges
(first-passage-percolation). We then show how this allows the derivation of various
properties of the classical Erd\H{o}s-R\'enyi random graph near criticality. Finally,
returning to the spectrum of random regular graph, we discuss the question of how
close they really are to being Ramanujan and conclude with related problems involving
random matrices.
Based on joint works with Jian Ding, Jeong Han Kim and Yuval Peres, with Allan Sly
and with Benny Sudakov and Van Vu.