CATS Seminar: Spring 2011
(Capital Area Theory Seminar (CATS))
CATS Seminar: Spring 2011
(Capital Area Theory Seminar (CATS))
CATS usually meets on Fridays 1:00pm- 2:00 pm AVW3258 but some talks may be at a different place and time.
For additional information send email to Samir Khuller.
If you want to receive announcements of upcoming talks join the theory-local mailing list.
 |
Fixed-parameter tractability of multicut parameterized by the
size of the cutset
Given an undirected graph G, a collection (s_1,t_1), ..., (s_k,t_k) of pairs of
vertices, and an integer p, the Edge Multicut problem asks if there is a set S
of at most p edges such that the removal of S disconnects every s_i from the
corresponding t_i. Vertex Multicut is the analogous problem where S is a set of
at most
p vertices. Our main result is that both problems can be solved in time
2^{O(p^3)} n^{O(1)}, i.e., fixed-parameter tractable parameterized by the size p
of the cutset in the solution.
This is joint work with Igor Razgon.
Date: Feb 4 (Friday)
Time: 1-2PM
Room: AVW3258
Speaker: Siavosh Benabbas (University of Toronto)
Title: Approximation Algorithms for some Quadratic Threshold CSPs.
Abstract:
Consider the Max-3SAT problem. Here one is given a collection of clauses
each disjunction of three variables or their negations with the objective
of assigning values to the variables to maximize the number of satisfied
clauses. A celebrated result of Hastad(JACM'01) states that Max-3SAT is
NP-hard to approximate within a factor better than 7/8+\epsilon (for any
\epsilon). In other words given a Max-3SAT instance it is NP hard to give
a solution with objective value more than 7/8 times the optimal objective
value. It is not hard to see that a random assignment of values to
variables is already a 7/8 approximation for Max-3SAT as it satisfies 7/8
of all clauses in expectation.
A natural and well studied generalization of Max-3SAT is the Max-kCSP(P)
class of problems. Here one fixes a 0-1 function of k variables, which we
call P, and considers an optimization problem exactly like Max-3SAT except
the clauses are no more disjunctions but rather the application of P to
sets of k literals. For example, Max-3CSP(OR) is the same problem as
Max-3SAT and Max-4CSP(XOR) is the problem of (approximately) solving
linear equations each on 4 variables modulo 2. An important open problem
is for which P the best approximation algorithm for Max-kCSP(P) is a
random assignment of values to the variables. For example, Hastad's result
precisely states that OR of 3 variables is one such P. See Austrin-Mossel
(CCC'08) for a sufficient condition and Austrin-Hastad (STOC'09) for some
necessary conditions.
As it turns out Quadratic Thresholds are the canonical examples of P for
which this problem is open. These are functions defined as the sign of a
quadratic form on k variables. It had been suggested that whenever P is a
quadratic threshold Max-kCSP(P) can be approximated better than a random
assignment. We show some partial results in this direction. In particular
we show approximation algorithms that perform better than a random
assignment if P is a _symmetric_ quadratic threshold, i.e. a quadratic
threshold whose output does not depend on the ordering of its inputs. We
also present an approximation algorithm for a particular P called Monarchy
which is not symmetric. The main interesting property of Monarchy is that
Max-kCSP(Monarchy) seems to resist all previous techniques for devising
approximation algorithms.
joint work with Per Austrin, Avner Magen.
Randomized Algorithms in Linear Algebra and Applications
Abstract:
The introduction of randomization in the design and analysis of algorithms
for matrix computations (such as matrix multiplication, least-squares
regression, the Singular Value Decomposition (SVD), etc.) over the last
decade provided a new paradigm and a complementary perspective to
traditional numerical linear algebra approaches. These novel approaches
were motivated by technological developments in many areas of scientific
research that permit the automatic generation of large data sets, which
are often modeled as matrices.
In this talk we will outline how such approaches can be used to
approximate problems ranging from matrix multiplication and the Singular
Value Decomposition (SVD) of matrices to approximately solving
least-squares problems and systems of linear equations. Applications of
the proposed algorithms to data analysis will also be discussed.
Date: Feb 18(Friday)
Time: 1-2PM
Room:AVW3258
Speaker: Siavosh Benabbas, University of Toronto.
Title: "Integrality Gap of the Hypergraphic Relaxation of Steiner Trees: a
short proof of a 1.55 upper bound" by CKP
(based on a a recent paper of Chakrabarty, Konemann and Pritchard)
In the Steiner Tree Problem one is given a weighted graph G and a subset,
S, of its vertices and the goal is to connect
the vertices in S with minimum possible cost. In other words one wants to
find a tree in G of minimum total cost that spans all
vertices of S. From a practical point of view this is a very important
problem as it comes up, for example, in constructing communication
networks.
Sadly, the problem is NP-hard (and in fact APX-hard.) It is then natural
to study the best possible approximation algorithm for this problem.
Recently there has been some very exciting developments in terms of
approximation algorithms for Steiner Tree problem and its variants.
In particular, Byrka et. al. [1] presented an approximation algorithm with
approximation factor 1.39, improving the previous best
factor of 1.55. They also showed that the Integrality Gap of a certain
Linear Programming relaxation of this problem is at most 1.55, that is
the LP relaxation is always within a factor 1.55 of the optimal solution.
This is interesting as the LP relaxations can often be extended to other
more practical variants of the Steiner Tree problem (for example Prize
Collecting Steiner Tree Problem) and a better Integrality gap can
potentially
be salvaged to give better algorithms for these variants. Unfortunately,
the proof of this Integrality gap was complicated and technical. Recently
Chakrabarty-Konemann and Pritchard [2] presented a simpler, more intuitive
proof of the Integrality gap which I will present this week. The proof
analyzes a "loss contracting" rounding algorithm for the LP.
I will go over relevant definitions and theorems from the literature and
no prior familiarity with either paper is assumed.
References:
[1] J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanita. An improved LP-based
approximation for Steiner tree. In Proc. 42nd STOC, pages 583–592, 2010.
[2] D. Chakrabarty, J. Koenemann, and D. Pritchard. Integrality Gap of the
Hypergraphic Relaxation of Steiner Trees: a short proof of a 1.55 upper
bound, to be published in Operations Research Letters.
Date: March 4th (Friday)
Time: 1-2PM
Room: AVW3258
Speaker: Aravind Srinivasan
Abstract:
I will present the following paper this Friay, March 4th:
"Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs"
by Ashish Goel, Michael Kapralov, Sanjeev Khanna. Available at
http://arxiv.org/abs/0909.3346
Abstract of the Goel-Kapralov-Khanna paper:
In this paper we consider the well-studied problem of finding a perfect matching
in a d-regular bipartite graph on 2n nodes with m=nd edges. The best-known
algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time
O(m\sqrt{n}). In regular bipartite graphs, however, a matching is known to be
computable in O(m) time (due to Cole, Ost and Schirra). In a recent line of work
by Goel, Kapralov and Khanna the O(m) time algorithm was improved first to
\tilde O(min{m, n^{2.5}/d}) and then to \tilde O(min{m, n^2/d}). It was also
shown that the latter algorithm is optimal up to polylogarithmic factors among
all algorithms that use non-adaptive uniform sampling to reduce the size of the
graph as a first step.
In this paper, we give a randomized algorithm that finds a perfect
matching in a d-regular graph and runs in O(n\log n) time (both in expectation
and with
high probability). The algorithm performs an appropriately truncated random
walk on a modified graph to successively find augmenting paths. Our algorithm
may be
viewed as using adaptive uniform sampling, and is thus able to bypass the
limitations of (non-adaptive) uniform sampling established in earlier
work. We also show that randomization is crucial for obtaining o(nd) time
algorithms by establishing an \Omega(nd) lower bound for any deterministic
algorithm. Our
techniques also give an algorithm that successively finds a matching in the
support of a doubly stochastic matrix in expected time O(n\log^2 n) time,
with O(m) pre-processing time; this gives a simple O(m+mn\log^2 n) time
algorithm for finding the Birkhoff-von Neumann decomposition of a doubly
stochastic matrix.
Procrastination Pays: Scheduling jobs in batches to minimize energy usage
Samir Khuller
University of Maryland
samir@cs.umd.edu
We consider an elementary scheduling problem defined as follows. Given a
collection of n jobs, where each job J_i has an integer length l_i as well
as a set T_i of time intervals in which it can be feasibly scheduled.
We are given a parallelism parameter P and can schedule up to P jobs
at any time slot in which the machine is ``active''. The goal is to
preemptively schedule all the jobs in the fewest number of active time slots.
The machine consumes a fixed amount of energy per time slot, regardless of
the number of jobs scheduled at that slot (as long as the number of jobs is
non-zero). In other words, subject to l_i units of each job i being scheduled
in its feasible region and at each slot at most P jobs being scheduled, we
are interested in minimizing the total time duration when the machine is active.
We present an O(n log n) algorithm for the case where jobs have
unit length and T_i forms a single interval.
For general T_i (and unit jobs), we show that the problem is NP-complete even
for P=3. However when P=2, we show that it can be solved
in polynomial time -- we also present several extensions: for example
when the jobs have non-unit requirements we can still solve
this version in polynomial time.
No previous background knowledge on scheduling is expected. In addition, we will
survey some recent work on bundling jobs in batches.
(Joint work with J. Chang and H. Gabow.)
(1st part): online bipartite matching with stochastic inputs
(2nd part): DNA sequence assembly with optical mapping technology
Henry Lin
University of Maryland
Abstract (1st part):
In the first part of the talk, I'll describe an online bipartite
matching problem, which models a scenario in which clients arrive over
time and request permanent service from a set of given servers. This
model may represent settings in which the clients are customers
seeking to have websites hosted online, and the servers are web host
providers. Clients arrive with requests to be assigned only to
certain web hosts based on various constraints, such as the cost or
location of the web host providers. To model this scenario, we
imagine as each client arrives, she announces a set of feasible
servers capable of servicing her request, and our goal is to provide
service to the clients by maintaining a matching between clients who
have arrived and servers capable of servicing their requests. We would
like to assign clients to servers permanently without ever
having to reassign clients to different servers, but when a new client
arrives we may be forced to reassign existing clients to alternative
servers to ensure that the servers can provide service to all clients.
As it is often more important to provide service to all clients, the
goal of our algorithm will be to maintain a matching always between
arrived clients and allowed servers, while minimizing the switching
cost, the total number of times that clients are reassigned to
different servers. Although prior worst case analysis for this
problem has not yielded strong results, we show tight bounds on the
number of times clients need to be switched under a few natural
settings, when the input is assumed to come from a random
distribution.
Abstract (2nd part):
In the second part of the talk, I'll talk about the challenge of
assembling fragments of DNA from an organism back into the entire
original DNA sequence of the organism, otherwise known as "shotgun
sequencing." Although many people assume that the sequence assembly
problem has more or less been solved, many challenges still remain in
terms of accurately and efficiently solving the sequence assembly
problem. In the second half of the talk, I will talk about the
development of new optical mapping technology that can be helpful for
solving the sequence assembly problem, and the algorithmic challenges
that come with utilizing the new optical mapping technology. For the
second part of the talk, I'll try to make sure it's still accessible
for those without any biology background. Please feel free to
interrupt with questions, if anything is unclear, however.
Speed-scaling algorithms for energy savings
Jessica Chang
University of Washington
Abstract:
In the past couple of decades, increasing attention has been given to
optimizing the energy consumption in CPU's. Advances in hardware design is
intimately coupled with an understanding of algorithmic scheduling
strategies. In this talk, I will present two results well-known within the
scheduling community. I will first introduce the speed scaling problem, in
which n jobs of arbitrary length must be scheduled on a single
variable-speed processor. The power consumed is assumed to be a convex
function of speed, and the goal is to minimize the power consumed over the
entire schedule. We will discuss the optimal greedy solution for this
problem. We will also see its role in a constant approximation for the
related setting in which the processor can be put to sleep while paying
constant cost each time it is woken up. The results can be found in the
following papers:
http://www.cs.pitt.edu/~kirk/cs3150spring2010/yds.pdf
http://www.cs.pitt.edu/~kirk/cs3150spring2010/power_soda-1.pdf
