Abstracts are below.
* Fri, Dec 11, 9:30am: Mathias Hallman
The Bin-Packing Problem
* Fri, Dec 11, 10:30am: Thach Nguyen
Approximation Algorithms for the Maximum Spanning Star Forest Problem: Part I
* Fri, Dec 11, 1pm: Jessica Chang
Approximation Algorithms with Submodular Objectives -- Part I
* Fri, Dec 11, 2pm: Ben Birnbaum
Iterative Rounding for Single-Source Unsplittable Flow and Other Problems
* Mon, Dec 14, 10am: Kate Moore
The Ellipsoid Algorithm
* Mon, Dec 14, 11am: Kevin Zatloukal
Approximation Algorithms with Submodular Objectives -- Part II
* Mon, Dec 14, 12pm: Richard Pang
Dynamic Programming Based Approximation Algorithms
* Mon, Dec 14, 1:30pm: Elisa Celis
Primal Dual Algorithms for Computing Balanced Outcomes
* Mon, Dec 14, 2:30pm: Alyssa Harding
Approximation Algorithms for the Prize Collecting Steiner Tree Problem
* Tues, Dec 15, 1:00pm: Adrian Sampson
Approximation Algorithms for Uncapacitated Facility Location
* Wed, Dec 16, 9am: Karthik Mohan
Minimum Routing Cost Spanning Tree
* Wed, Dec 16, 10am: Austin Webb
Local Graph Partitioning
* Thurs, Dec 17, noon: Trinh Huynh-Ngoc
Approximation Algorithms for the Maximum Spanning Star Forest Problem -- Part II
WITH ABSTRACTS:
* Fri, Dec 11, 9:30am: Mathias Hallman -- The Bin-Packing Problem
Given a set of n pieces, the bin-packing problem is to pack these
pieces in as few bins as possible, where each bin has a capacity of 1
and each piece i has a size s_i in (0,1]. The problem is a
combinatorial NP-hard problem, but can be approximately solved in
polynomial time. I will present two algorithms to do this. The first
one uses a linear grouping scheme along with a DP-algorithm to achive
an upper bound of (1+e)OPT+1 on the number of bins used, where e
(epsilon) > 0. The other algorithm uses a harmonic grouping scheme
along with a LP-representation to achive an upper bound of OPT +
O(log^2(OPT)). Applications of the problem includes e.g. loading
trucks with weight capacity and creating file backup in removable
media.
* Fri, Dec 11, 10:30am: Thach Nguyen -- Approximation Algorithms for the Maximum Spanning Star Forest Problem: Part I
An (undirected) star is a tree of diameter at most 2, and a direct
star is defined similarly where edges must point to the leaves. A star
forest is a graph that consists of node-disjoint stars. In the
"maximum spanning star forest problem", given an (undirected or
directed) graph $G(V,E)$ and a weight function $w: E \rightarrow R$,
we would like to compute a star forest that contains all the vertices
of $G$ and has the maximum total edge weight. When $G$ is unweighted,
i.e. $w(e) = 1$ for all $e \in E$, the maximum spanning star forest
problem is the complement of the minimum dominating set problem.
Previous work on the maximum spanning star forest problem mainly
concerns the special cases of unweighted undirected graphs. For the
weighted case, the best known results are trivial algorithms that
approximate the maximum spanning star forests within a factor of 2. In
this project, we aim to find better approximation algorithm for this
general unrestricted case.
Our presentation contains two parts. In the first part, we will
present a previous result: an approximation algorithm for the
unweighted problem that utilizes a non-linear rounding technique and
the better-of-two-algorithms approach. In the second part, we describe
our attempts to find approximation algorithms for the general problem.
* Fri, Dec 11, 1pm: Jessica Chang: Approximation Algorithms with Submodular Objectives -- Part I
Many computational problems have goals to optimize over additive
functions, e.g. cost or weight functions, despite the fact that the
real world is often not modeled by linearity. In this project, we
study computational problems over set functions more general than
modular functions. In particular, we investigate various approaches
to the set cover problem with a submodular set function. The class of
submodular functions subsumes additive ones and captures the economic
principle of diminishing marginal retuk)n2) approximation.
* Fri, Dec 11, 2pm: Ben Birnbaum: Iterative Rounding for Single-Source Unsplittable Flow and Other Problems
I will study iterative rounding as applied to two problems: the
single-source unsplittable flow problem and the spanning star forest
problem. The first problem is listed as an open problem at the end of
Mohit Singh's Ph.D. thesis. Currently the best approximation for the
problem is given by Skutella (2002), which finds an unsplittable flow
satisfying the original demands in which the flow on each edge e is no
more than 2f(e) + d_{max}, where f(e) is the amount of flow on e in an
optimal splittable flow, and d_{max} is the maximum demand. Goemans
conjectures that there should be an algorithm that improves this to
f(e) + d_{max}. I will investigate the use of iterative rounding
techniques for this problem.
* Mon, Dec 14, 10am: Kate Moore -- The Ellipsoid Algorithm
During the quarter, we've encountered several problems that have
exponentially-sized LPs: min-cost bounded-degree spanning trees,
multicuts, balanced cuts, and oblivious-routing/cut tree packings. In
order to solve such large linear programs, we've relied on the
ellipsoid method. If there is a polynomial time separation oracle,
this method allows us to prove polynomial time solvability for an
exponentially large set of constraints. However, there are few
details about the ellipsoid algorithm in Section 4.3 - the section of
the book that introduces the concept. In this presentation, I will
use outside resources (currently TBD) to present more technical
details about how the ellipsoid method works. I will also try to
provide some explanation of its theoretical relevance, and demystify
its obscurity as a practical tool.
* Mon, Dec 14, 11am: Kevin Zatloukal -- Approximation Algorithms with Submodular Objectives -- Part II
Many computational problems have goals to optimize over additive
functions, e.g. cost or weight functions, despite the fact that the
real world is often not modeled by linearity. In this project, we
study computational problems over set functions more general than
modular functions. In particular, we investigate various approaches
to the set cover problem with a submodular set function. The class of
submodular functions subsumes additive ones and captures the economic
principle of diminishing marginal returns. In addition, we consider
the load balancing problem with smoothed submodular set functions, a
class of functions more general than additive functions yet more
restricted than submodular functions.
* Mon, Dec 14, 12pm: Richard Pang: Dynamic Programming Based Approximation Algorithms
Dynamic programming is a powerful tool in algorithmic analysis. It
can be combined with rounding to produce interesting polynomial
approximation schemes (PTAS) for various problems. Two problems we
will cover are the Euclidean traveling salesman problem (TSP) and the
maximum-weight independent set problem in planar graphs. The
Euclidean TSP is a TSP variant where cities are denoted as points
(xi;yi), and the cost of traveling between two cities is the Euclidean
distance between the points. We can first produce a PTAS for instances
of the problem with certain nice properties. Then, we recursively and
randomly divide the orginial problem into subproblems with the nice
properties. We can show that a decomposition can be found with
probability at least 1/2 , which will produce a tour of cost at most
(1 + epsilon)OPT. In the maximum-weight independent set problem, we
are given an undirected graph G = (V;E) with nonnegative vertex
weights wi >= 0, and we want to find an independent set S that
maximizes \sum_{i\in S} w_i. We can first transform the graph into a
k-outerplanar graph with maximum degree 3. Then, we can obtain a
spanning forest decomposition and solve the problem on the subtrees to
obtain a O(2O(k)n2) approximation.
* Mon, Dec 14, 1:30pm: Elisa Celis -- Primal Dual Algorithms for Computing Balanced Outcomes
I will be looking at balanced outcomes and solutions to message
passing algorithms from a primal-dual approach. I hope to present the
background and primal-dual algorithm for computing the lex-center in
Azar et al's paper on Monotonicity in Bargaining Networks (to appear
in SODA '10, see:
http://research.microsoft.com/en-us/um/people/nikdev/pubs/monotonicity.pdf). Given
time I hope to present or draw connections to other related work on
message passing such as Bayati et al Natural Dynamics for Balanced
Oucomes (http://arxiv.org/abs/0911.1767), and possibly to my own work.
* Mon, Dec 14, 2:30pm: Alyssa Harding -- Approximation Algorithms for the Prize Collecting Steiner Tree Problem
I will describe approximation algorithms based on rounding, random
rounding and the primal-dual method for the Prize-Collecting Steiner
Tree Problem.
* Tues, Dec 15, 1:00pm: Adrian Sampson -- Approximation Algorithms for Uncapacitated Facility Location
I will discuss approaches to the uncapacitated facility location (UFL)
problem based on randomized rounding of linear programs. First, I'll
summarize the 4-approximation algorithm given by a deterministic
rounding technique (Section 4.5). Next, I'll show how the guarantee
can be improved to 3 using randomized rounding with the same LP
(Section 5.8), highlighting the kinds of benefits that can be offered
by randomization. Finally, depending on time, I'll explore an improved
randomized rounding approach yielding a 1 + 2/e guarantee (Section
12.1 and [1]).
[1]: Chudak and Shmoys, 2004: http://dx.doi.org/10.1137/S0097539703405754
* Wed, Dec 16, 9am: Karthik Mohan -- Minimum Routing Cost Spanning Tree
A review of the approximation algorithms for the Minimum routing cost
spanning tree problems will be presented. More specifically a
2-approximation, 3/2-approximation and a generalized Polynomial time
approximation scheme will be discussed. The main idea is that general
stars that use information from the optimal routing spanning tree give
good approximations. Also, there is a trade-off between the amount of
information used and the result complexity of the approximation
algorithm.
Reference:
Spanning Trees and Optimization Problems Bang Ye Wu and Kun-Mao Chao
* Wed, Dec 16, 10am: Austin Webb -- Local Graph Partitioning
Local graph partitioning has become increasingly of interest as huge
datasets, specifically those in graphical form, have become more
common. In order to analyze the structure of such datasets or break
them up for efficient storage, we often need to probe them locally for
low conductance vertex subsets. This is a highly difficult problem and
in most cases we must resort to approximate solutions, which prompted
the development of some number of approximation algorithms. The
algorithm due to Anderson and Peres, which we present, is the best so
far in terms of its ratio of computational complexity to the volume of
the output set, though it does not have the best demonstrated
approximation guarantee. The algorithm is based on the volume-biased
evolving set process and a dynamic data structure that allows it to
ignore all but a subset of vertices under consideration. We give an
overview of how the algorithm works and attempt to give an intuition
for why the algorithm outperforms its nearest competitor (due to
Andersen, Chung, and Lang) and all similar algorithms based on simple
random walks or PageRank vectors.
* Thurs, Dec 17, noon: Trinh Huynh-Ngoc
Approximation Algorithms for the Maximum Spanning Star Forest Problem -- Part II
An (undirected) star is a tree of diameter at most 2, and a direct
star is defined similarly where edges must point to the leaves. A star
forest is a graph that consists of node-disjoint stars. In the
"maximum spanning star forest problem", given an (undirected or
directed) graph $G(V,E)$ and a weight function $w: E \rightarrow R$,
we would like to compute a star forest that contains all the vertices
of $G$ and has the maximum total edge weight. When $G$ is unweighted,
i.e. $w(e) = 1$ for all $e \in E$, the maximum spanning star forest
problem is the complement of the minimum dominating set problem.
Previous work on the maximum spanning star forest problem mainly
concerns the special cases of unweighted undirected graphs. For the
weighted case, the best known results are trivial algorithms that
approximate the maximum spanning star forests within a factor of 2. In
this project, we aim to find better approximation algorithm for this
general unrestricted case.
Our presentation contains two parts. In the first part, we will
present a previous result: an approximation algorithm for the
unweighted problem that utilizes a non-linear rounding technique and
the better-of-two-algorithms approach. In the second part, we describe
our attempts to find approximation algorithms for the general problem.
TO BE RESCHEDULED:
Alex Jaffe: Primal-dual Algorithms for Semi-definite Programs -- Part I
Primal-dual algorithms have had a tremendous impact on the design of
approximation algorithms over the past two decades. These algorithms
utilize the structure of an LP relaxation and its dual, without ever
taking the time to optimally solve either LP. In so doing, researchers
have found exceptionally fast algorithms for classic problems, that
meetand occassionaly beatthe approximation factors of the best
known LP rounding techniques. Since 1994, another vital branch of
approximation algorithms has developed in parallel to, but largely in
isolation from, primal-dual algorithms: the rounding of semidefinite
programming relaxations. A generalization of linear programming,
semidefinite programs allow for optimization over vectors in a
high-dimensional space, with linear constraints over the dot products
of these vectors. Rounding such programs has produced approximation
algorithms tighter any known linear programming methods, for a huge
set of NP-hard problems. In 2007, Arora-Kale were the first to
systematically unify these two disciplines. They construct a general
framework for producing primal-dual algorithms for semidefinite
programming relaxations, using a common (but often implicit) technique
known as multiplicative weights update. Their framework can in fact be
thought of as the natural generalization of a similar framework by
Plotkin-Shmoys -Tardos, for the subset of LPs known as packing and
covering problems. In essence, both frameworks maintain and improve a
(possibly infeasible) primal solution over several steps. For a given
problem, they require the construction of an oracle which guides the
progress of the primal-dual algorithm, by finding dual-variable
certificates of the current primal solutions flaws. We will
present the Arora-Kale framework, and discuss its relation to the
Plotkin-Shmoys-Tardos framework and the solutions of zero-sum
games. We will then show a simple oracle to exhibit these ideas, and
finally, give a sketch of the proof that that the framework converges
quickly for good oracles.
TO BE RESCHEDULED:
Punya Biswal -- Primal-dual Algorithms for Semi-definite Programs -- Part II
In part 1, we presented the matrix multiplicative weights framework
proposed by Arora and Kale [AK] for efficiently solving and rounding
SDP relaxations of combinatorial optimization problems. Now we shall
show how this technology can be applied to the sparsest cut problem by
implementing an Oracle that receives a candidate primal solution and
identifies either a set of highly violated constraints or an integral
sparse cut. In particular, well present a construction of [AK]
that uses single-commodity flows and achieves a O(log n)
approximation. The overall algorithm is very efficient: its runtime is
dominated by a subpolynomial number of single-commodity flows.
Well also talk about our ongoing work on a natural generalization
of the sparsest cut problem, and the corresponding generalization of
the [AK] oracle.
Reference:
[AK] S. Arora, S. Kale, A combinatorial primal-dual approach to semidefinite programs. STOC
2007: 227236.