Algorithms for edit distance on permutations
The edit distance between two strings (aka Levenshtein distance)
is the number of character insertions, deletions and substitutions
required to transform one string to the other.
I will focus on strings which are permutations (or rankings), i.e.
comprise of distinct characters.
I will first present a low-distortion embedding of edit distance
on permutations (aka the Ulam metric) [joint work with Moses Charikar,
and a new proof joint with Parikshit Gopalan and T.S. Jayram].
I will then discuss a data stream algorithm for estimating
the "sortedness" of a permutation, measured by its edit distance
from a monotone permutation [joint with Parikshit Gopalan, T.S. Jayram,
and Ravi Kumar].
The Conjugate Gradient Method with Automatic Preconditioning
Solving a linear system is one of the most fundamental computational
problems. Unfortunately, the basic algorithm that most of us learn
(Gaussian Elimination) is often useless in practice due to slow running
time or stability issues. Instead, it is more common to use iterative
solvers, the simplest ones being steepest descent and conjugate gradient.
The snag with iterative solvers is that their performance often depends on
the "condition number" of the given system, so it is common to modify the
system by applying a "preconditioner" matrix which reduces the condition
number. This raises a key question: given a linear system, how can we find
a good preconditioner?
In this work, we develop a variant of conjugate gradient method which *automatically* constructs good preconditioners. The general idea is very simple. We run the conjugate gradient method until it "gets stuck". The fact that it is stuck then implies a way to modify the preconditioner so that the conjugate gradient steps will be "less stuck" in the future.
This talk will be self-contained -- the audience only needs to know basic linear algebra, and how to interpret pictures of algorithms that are stuck.
Joint work with John Dunagan, Microsoft Research.
Approximation algorithms for buy-at-bulk network design
Buy-at-bulk network design problems arise in telecommunication
networks and related fields where economies of scale result in
concave cost functions for purchasing bandwidth. A basic problem
in this area is the following. We are given a graph G=(V,E) which
represents an underlying network. We are also given a demand matrix
in the form of pairs s_1t_1, s_2t_2, ..., s_kt_k with each pair
s_it_i requesting a bandwidth of d_i units. The goal is to
satisfy these bandwidth requests at minimum cost by buying
capacity on the links of the network. The cost of buying
a capacity on link e is given by a concave cost function
f_e; that is f_e(x) is the cost of buying capacity of x units
on link e.
In this talk we present a new algorithm for this problem that yields an O(log^4 k) approximation ratio. This is the first poly-logarithmic approximation when the functions f_e can be different for different links. The algorithmic idea is intuitive and is amenable to various heuristic implementations. The analysis illustrates a high level idea that allows one to reduce a multi-commodity problem to essentially a single-commodity problem.
Joint work with M.T. Hajiaghayi, G. Kortsarz and M.R. Salavatipour
Provably Good Adaptive Scheduling with Parallelism Feedback
Multiprocessor scheduling in a shared multiprogramming environment is
often structured as two-level scheduling, where a kernel-level job
scheduler allots processors to jobs and a user-level thread scheduler
schedules the work of a job on the allotted processors. In this
context, the number of processors allotted to a particular job may
vary during the job's execution, and the thread scheduler must adapt to
these changes in processor resources.
A-Steal is an adaptive work-stealing thread scheduler for fork-join multithreaded jobs which provides continual parallelism feedback to the job scheduler in the form of requests for processors. A-Steal guarantees that a job completes near optimally while utilizing at least a constant fraction of the allotted processor cycles. Our analysis models the job scheduler as the thread scheduler's adversary, challenging the thread scheduler to be robust to the system environment and the job scheduler's administrative policies. For example, the job scheduler can make available a huge number of processors exactly when the job has little use for them, and provide few processors when the job has ample parallelism. To analyze the performance of A-Steal under this stringent adversarial assumption, we introduce a new technique called ``trim analysis,'' which allows us to prove that A-Steal performs poorly on at most a small number of time steps, exhibiting near-optimal behavior on the vast majority.
To be precise, suppose that a job has work $T_1$ and critical-path
length $T_\infty$. On a machine with $P$ processors, A-Steal
completes the job in expected $O(T_1/P_{trim} + T_\infty + L \lg P)$
time steps, where $L$ is the length of a scheduling quantum and
$P_{trim}$ denotes the $O(T_\infty +L \lg P)$-trimmed availability.
This quantity is the average of the processor availability over all
but the $O(T_\infty +L \lg P)$ time steps having the highest processor
availability. When the job's parallelism dominates the trimmed
availability, that is, $P_{trim} \ll T_1/T_\infty$, the job achieves
nearly perfect linear speedup. Conversely, when the trimmed mean
dominates the parallelism, the asymptotic running time of the job is
nearly the length of its critical path.
New Geometric Relaxations for the Steiner Tree
Problem
and their Algorithmic Consequences
Among the major open problems left in approximation algorithms
is determining the integrality gap of the bidirected
cut relaxation for the Steiner tree problem and exploiting it
algorithmically. The worst integrality gap example known for
this remarkable relaxation is 8/7, i.e., very close to 1.
Yet, current algorithmic ideas give no better guarantee than that
obtained using the undirected relaxation, namely 2.
We give two new geometric ralaxations for this problem; one is exactly equivalent to, and the other is strictly better than, the bidirected relaxation. The most exciting feature of these relaxations is the novel algorithmic ideas they have inspired. In ongoing work, these ideas have so far helped us obtain a 4/3 factor algorithm and integrality gap bound for the case of quasi-bipartite graphs; the previous best being 3/2. We also give a factor $\sqrt{2}$ strongly polynomial algorithm for this class of graphs.
Joint work with Deeparnab Chakrabarty and Vijay V. Vazirani.
Incentive-Based Ranking Mechanisms
We consider ranking/recommendation systems based on user
feedback. We make a case for sharing with users the revenue generated
by such systems. Our main contribution is a mechanism which rewards
useful feedback and is resistant to selfish/malicious behavior (eg.
click spam). The mechanisms are designed to reward discovery of high
quality entities. Misclassified pages represent an arbitrage
opportunity for the discerning user. The mechanisms are simple enough
for use with existing technology.
Joint work with Ashish Goel.
Determinant Versus Permanent
I will talk about the problem of expressing permanent of matrices as
determinant of (possibly larger) matrices. This problem has close
connections with complexity of arithmetic computations: complexities
of computing permanent and determinant roughly correspond to
arithmetic versions of the classes NP and DP respectively. I will
survey known results about their relative complexity and describe two
recently developed approaches that might lead to a proof of the
conjecture that permanent can only be expressed as determinant of
superpolynomial-sized matrices.
Reconstruction of and Optimization on Networks
Abstract: Stochastic models defined on networks introduce novel algorithmic challenges.
This challenges arise from diverse application fields, such as molecular biology, computer networks and social networks.
In this talk I will survey some recent progress in this area.
In particular, I will discuss the problem of reconstructing the network from observations at some nodes and optimization problems defined on such networks.
Based on joint works with C. Daskalakis and S. Roch, with S. Roch and with C. Daskalakis, D. Karp, S. Riesenfeld and E. Verbin
New Results and Open Problems for Deletion Channels and Related Synchronization Problems
At this point, it seems that most everything is known about the basic
channels studied in information theory. For the i.i.d. (independent
and identically distributed) binary erasure channel and the
i.i.d. binary symmetric error channel, the capacity has long been
known, and there are very efficient encoding and decoding schemes that
are near capacity.
The situation is very different for the i.i.d. binary deletion channel. With this channel, the sender sends n bits, and each bit is deleted with some fixed probability p. So, for example, the sender might send 10110010, and the receiver obtains 1100. The i.i.d. binary deletion channel is perhaps the most basic channel that incorporates the challenge of synchronization. Surprisingly, even the capacity of the deletion channel remains unknown!
In this talk, I will survey what is known about the deletion channel,
focusing on our recent work on bounds on the capacity. The main result
is that the for any probability p, the deletion channel has capacity
at least (1-p)/9. Hence, the capacity of the deletion channel is
always within a constant factor of the erasure channel (which has
capacity (1-p)). We also discuss the many remaining open problems in
the area of synchronization channels.
Degree constrained network flows
In a single-sink multicommodity network flow problem on a graph G=(N,A) we wish
to route a set of demands from a collection of source nodes to a sink node t.
We are interested in flows whose support graphs are restricted to have
outdegree at most d at each node - these are termed d-furcated flows.
Our goal here is to minimise the maximum congestion at any node. Specifically, we examine the "congestion gap" for the class of d-furcated flows; this is the maximum ratio between the congestion of an optimal d-furcated flow and an optimal fractional flow (i.e. a flow with no outdegree restriction).
For flows with outdegree at most d=1 (commonly known as confluent flows) the
congestion gap is \Theta(log n) [CK+04]. For flows with outdegree at most d>1
the congestion gap is exactly 1+1/(d-1) [DS+06]. In particular, the congestion
gap becomes bounded, namely 2, if the permissible outdegree increases from one
to two.
Programmable Stochastic Self-Assembly
We consider the control of programmable self-assembling systems whose
dynamics are governed by stochastic reaction-diffusion dynamics. In our
system, particles may decide the outcomes of local reactions initiated by
the environment, thereby steering the global system to produce a desired
assembly type. I will describe the construction of local rule sets using
graph grammars and methods by which the global properties of the resulting
systems can be guaranteed. Then, based on measured natural reaction rates,
we describe a method that automatically generates the best rule set for the
particles so as to maximize the yield in the system - essentially an example
of metabolic pathway engineering in a unique setting. We demonstrate the
design method using a variety of examples, including with our
self-assembling robot test-bed.
TBA
TBA
Analysis of Cycle Stealing and Priority
Queueing in Multi-Server Systems via Dimensionality Reduction Technique
We consider common resource sharing policies for multiserver systems
including cycle stealing policies, priority queueing, task assignment
policies, and threshold policies. Even these simple policies are
already very difficult to analyze because their underlying Markov
chain structure grows infinitely in more than one dimension. The
dimensionality of the Markov chain is typically equal to the number of
servers or the number of job classes. We introduce a new analysis
technique which we call Dimensionality Reduction for Markov Chains,
that enables the first near-exact analysis of many fundamental
resource sharing problems for multiserver systems.
The talk will focus on the new insights obtained by analyzing these
policies and proposals for improved policies. We will consider
questions such as: When does cycle stealing pay? How do different
cycle stealing methods compare? How does the multiserver priority
queue compare with the single server priority queue? What is the
effect of variability in service demand? Under threshold-based load
sharing, where a ``donor'' machine helps a ``beneficiary'' machine at
some threshold point, who should control the threshold: the donor or
the beneficiary? How many thresholds does one need?
Designing Networks with Good Equilibria
Today, many of the networks are created and used by a vast number of
autonomous individuals with diverse objectives. Research in the design
and analysis of algorithms has responded in kind, with an increasing focus
on optimization in networks with self-interested designers or users. We
design protocols for networks with selfish users to minimize the
inefficiency of equilibria. We consider network cost-sharing games, where
the set of Nash equilibria depends fundamentally on the chosen
cost-sharing protocol. We systematically study the design of optimal
cost-sharing protocols for undirected and directed graphs, single-sink and
multicommodity networks, the POA and the POS, and different classes of
cost-sharing methods.
Joint work with Tim Roughgarden and Gregory Valiant
A Primal Dual Approach to Online Optimization Problems
A unified approach, based on the primal-dual method, is discussed for
a wide range of online covering and packing problems, having various
objective functions. This approach has lead to a simple alternative view
and analysis of many previously suggested algorithms, as well as new
results. In particular, a randomized O(log k)-competitive online
algorithm for the weighted caching problem, in which there is a weight
(cost) for fetching each page into the cache, and k is the cache size.
This is the first randomized o(k)-competitive algorithm and its
competitiveness matches the known lower bound on the problem.
Weighted paging is a special case (weighted star metric) of
the well known k-server problem for which it is a major open
question whether randomization can be useful in obtaining
sublinear competitive bounds.
Based on papers with Nikhil Bansal, Niv Buchbinder, and Kamal Jain.
Sampling algorithms and coresets for Lp regression
and applications
L2 regression, also known as the least squares approximation
problem, and more generally Lp regression, are fundamental problems that
have numerous applications in mathematics and statistical data analysis.
Recall that the over-constrained Lp regression problem takes as input an n x
d matrix A, where n > d, an n-vector b, and a number p, and it returns as
output a d-vector x such that ||Ax-b||_p is minimized. Several randomized
algorithms for this problem, each of which provides a relative-error
approximation to the exact solution, are described. The first algorithm
applies novel ``subspace sampling'' probabilities to randomly sample
constraints and thus construct a coreset for the L2 regression problem. The
second algorithm (of T. Sarlos) applies a random projection and uses a
``fast'' version of the Johnson-Lindenstrauss lemma to obtain an efficient
approximation to the L2 regression problem. The third algorithm generalizes
the concept of a ``well-conditioned'' basis and of ``subspace-preserving
sampling'' to obtain efficiently a coreset for Lp regression, for all
$p\in[1,\infty)$. Applications of these random projection and random
sampling algorithms to internet data analysis will be briefly discussed.
Integrality gaps of semidefinite programs for
Vertex-Cover and
connections with \ell_1 embeddability of negative type metrics
We study various strengthenings of the standard SDP formulation for VERTEX
COVER such as
adding the triangle inequalities, or the so-called pentagonal inequalities
as well as the formulation
introduced by Karakostas (ICALP '05).
We show that the integrality gap of all these formulations is 2-o(1) and
in
particular at least 2-O(sqrt{log log n/ log n}).
This almost meets the upper bound due to
Karakostas, of 2-Omega(sqrt{1 / log n}), which is the currently best
approximation algorithm for VERTEX COVER.
Next, viewing SDP solutions as metric spaces, we look at how the integrality gap grows as a function of the distortion required to embed the solution into \ell_1. We show the following threshold phenomenon: Strengthening the SDP with the requirement that the solution is an \ell_1 metric, yields an exact relaxation (integrality gap is 1). On the other hand, with the weaker requirement that the solution is arbitrarily close to being \ell_1 embeddable ( i.e., the distortion is at most 1+epsilon), the integrality gap jumps to 2-o(1).
Finally, inspired by the above findings, we use ideas from the integrality gap constructions to provide a family of simple examples of negative type metrics that cannot be embedded into \ell_1 with distortion better than 8/7-epsilon. To this end we provide a new isoperimetric inequality for the hypercube.
joint work with Avner Magen and Hamed Hatami