[Colloquium] Research at TTIC: Yury Makarychev, TTIC
Dawn Ellis
dellis at ttic.edu
Fri Jan 16 15:31:45 CST 2015
When: Friday, January 23rd at noon
Where: TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
Who: Yury Makarychev, TTIC
Title: Nonuniform Graph Partitioning with Unrelated Weights
Abstract:
We give a bi-criteria approximation algorithm for the Minimum Nonuniform
Partitioning problem, recently introduced by Krauthgamer, Naor, Schwartz
and Talwar (2014). In this problem, we are given a graph $G=(V,E)$ on $n$
vertices and $k$ numbers $\rho_1,\dots, \rho_k$. The goal is to partition
the graph into $k$ disjoint sets $P_1,\dots, P_k$ satisfying $|P_i|\leq
\rho_i n$ so as to minimize the number of edges cut by the partition. Our
algorithm has an approximation ratio of $O(\sqrt{\log n \log k})$ for
general graphs, and an $O(1)$ approximation for graphs with excluded
minors. This is an improvement upon the $O(\log n)$ algorithm of
Krauthgamer, Naor, Schwartz and Talwar (2014). Our approximation ratio
matches the best known ratio for the Minimum (Uniform) $k$-Partitioning
problem.
We extend our results to the case of "unrelated weights" and to the case of
"unrelated $d$-dimensional weights". In the former case, different vertices
may have different weights and the weight of a vertex may depend on the set
$P_i$ the vertex is assigned to. In the latter case, each vertex $u$ has a
$d$-dimensional weight $r(u,i) = (r_1(u,i), \dots, r_d(u,i))$ if $u$ is
assigned to $P_i$. Each set $P_i$ has a $d$-dimensional capacity $c(i) =
(c_1(i),\dots, c_d(i))$. The goal is to find a partition such that
$\sum_{u\in {P_i}} r(u,i) \leq c(i)$ coordinate-wise.
Joint work with Konstantin Makarychev
***************************************
Research at TTIC Seminar Series
TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research. The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.
To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe
Speaker details can be found at: http://www.ttic.edu/tticseminar.php.
For additional questions, please contact David McAllester at
mcallester at ttic.edu
--
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu
TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150116/8fc596be/attachment.htm
More information about the Colloquium
mailing list