Home •
Research •
Teaching •
|
Algorithms Reading Group - Fall 2008
Room B-11 MLH;
Fridays 9:30am - 10:30/11:30am.
Welcome to the Algorithms
Reading Group. Our schedule for Fall 2008 is to meet every
Friday at 9:30am. in room B-11 MLH.
If you would like to be
on the mailing list then please email:
saurav-pandit@uiowa.edu.
For those who would like to
speak, please email me the following:
- Title of the paper
- Author(s)
- Where it appeared
- Web link to the paper
- Abstract
Please consult the following
tables for our schedule and other details. This page will be
updated when necessary throughout the semester. For previous
offerings of the seminar, please click here.
|
Date |
Speaker |
Title/Announcements/Comments |
Time
|
Room
|
| 08/29 |
Introductory Meeting |
Scheduling the first round of talks |
10:00-10:30 |
Muhly Lounge |
| 09/05 |
Gaurav's Comp |
"Rural Wireless Connectivity Minimum Cost Topology Construction"
Abstract
Wireless mesh networks based on the IEEE 802.11 technology have recently been proposed
and studied as an approach to bridge the digital divide, and connect to distant rural areas.
Point-to-point links are established in the nodes of such networks using high gain directional
antennas. Some nodes are directly connected to the wired internet, and the others connect to
these using a small number of hops.
Minimization of system cost is an important objective in these networks, since generally the
rural populations are low-paying. The dominant cost in this setting is that of constructing the
antenna towers which are needed for Line-of-Sight connectivity. The cost of a tower depends
upon its height, which in turn depends upon the length of its links and the physical obstacles
along those links. We investigate the problem of selecting which links should be established
such that all nodes are connected, while the cost of constructing the antenna towers required
to achieve Line-of-Sight connectivity is minimized. We formulate this as a geometric coverage
problem, show that it is NP-hard, and then present a constant factor approximation. For this
we model it as an integer program and use a primal dual approach for the solution that is
convenient to implement. We also present a polynomial time approximation scheme (PTAS) for
the same problem without the constraints on available transmission power. This algorithm uses
dynamic programming in conjunction with several Computational Geometry techniques.
|
09:00 |
B11 MLH |
| 09/12 |
Matt's Comp |
"Algorithms for Establishing and Extending Sensor Networks"
Abstract
A sensor is a small, battery-operated device that can be placed in
some area to locally monitor its surroundings. A distributed sensor
network is a collection of sensors which work together to monitor some
universe. In this paper, we survey recent results pertaining to two
different algorithmic questions motivated by applications in sensor
networks.
We consider the problem of positioning each of k sensors so as to
cover a set of n points. We assume that each sensor has an adjustable
radius and will cover all points who are within the radius of the
sensor. We wish to cover all of the points with the k sensors so as
to minimize the sum of the radii of each of the sensors. We model
this problem as the algorithmic problem clustering to minimize the sum
of radii. We will consider algorithms given by Gibson et al.
Suppose now that the positions of the sensors are fixed, and each
sensor has duration which represents the maximum amount of time that a
sensor can be ``active''. The second problem we consider is
scheduling a start time to each of the sensors so as to maximize the
total amount of time that the entire area is covered. This problem is
known as the sensor cover problem. We will consider the algorithm
given by Gibson and Varadarajan for a special case of the sensor cover
problem called Restricted Strip Covering.
|
09:00 |
B11 MLH |
| 09/19 |
Kasturi |
"Covering Linear Programs with Greedy Matrices and Terrain Guarding"
Abstract
A 0-1 matrix A is said to be in standard greedy form if for any
two rows and two columns, the induced 2 by 2 submatrix does not
have the form: a 0 in the bottom right corner, and 1 everywhere
else. We consider the covering linear program for a positive
vector c: min cx, subject to Ax \geq 1. We will describe an
algorithm due to Hoffman, Kolen, and Sakarovitch [ SIAM J Alg.
Disc. Meth., 1985 ] that establishes that an integral optimum
to this linear program always exists, and that efficiently finds
such an optimum. This result is employed by a recent algorithm
due to Elbassioni, Matijevic, Mestre, and Severdija
[ http://arxiv.org/abs/0809.0159 ] to obtain a constant factor
approximation for guarding monotone polygonal chains in the
weighted case.
|
09:30-11:30 |
B11 MLH |
| 09/26 |
Erik |
"A Pseudopolynomial Time O(log^2 n)-approximation Algorithm for Art Gallery Problems" Ajay Deshpande, Taejung Kim, Erik D. Demaine, and Sanjay E. Sarma
Appeared in WADS 2007.
Abstract
In this paper, we give a O(log copt)-approximation algorithm for the point guard problem where copt is the optimal number of guards. Our algorithm runs in time polynomial in n, the number of walls of the art gallery and the spread \Delta, which is defined as the ratio between the longest and shortest pairwise distances. Our algorithm is pseudopolynomial in the sense that it is polynomial in the spread \Delta as opposed to polylogarithmic in the spread \Delta, which could be exponential in the number of bits required to represent the vertex positions. The special subdivision procedure in our algorithm finds a finite set of potential guard-locations such that the optimal solution to the art gallery problem where guards are restricted to this set is at most 3 copt. We use a set cover cum VC-dimension based algorithm to solve this restricted problem approximately.
|
09:30-10:30 |
B11 MLH |
| 10/03 |
Saurav |
"A distributed O(1)-approximation algorithm for the uniform facility location problem"
Joachim Gehweiler, Christiane Lammersen, Christian Sohler
Appeared in SPAA 2006.
Abstract
In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.
|
09:30-11:30 |
B11 MLH |
| 10/10 |
Sriram |
"Improved bandwidth approximation for trees and chordal graphs"
Anupam Gupta
Appeared in SODA 2000.
Sriram says
I will present an elegant, randomized algorithm for obtaining an O(log^{2.5} n)-approximation to the minimum bandwidth problem on trees. This is due to Anupam Gupta (conf. version: SODA 2000, journal version: J. Alg. 2001).
|
09:30-10:30 |
B11 MLH |
| 10/17 |
Matt |
"Decomposition of Multiple Coverings into More Parts"
Greg Aloupis, Jean Cardinal, Sebastien Collette, Stefan Langerman, David Orden, and Pedro Ramos
To appear in SODA 2009.
Abstract
We prove that for every centrally symmetric convex polygon
Q, there exists a constant \alpha such that any (\alpha \cdot
k)-fold covering of the plane by translates of Q can be decomposed
into k coverings. This improves on a quadratic upper bound proved by
Pach and Toth (SoCG?07). The question is
motivated by a sensor network problem, in which a region has to be
monitored by sensors with limited battery lifetime.
|
09:30-11:30 |
B11 MLH |
| 10/24 |
No meeting |
|
|
|
| 10/31 |
Don |
"A separator theorem for planar graphs" Richard J. Lipton, Robert E Tarjan
Abstract
Let G be any n-vertex planar graph. We prove that the vertices of G can
be partitioned into three sets A,B,C such that no edge joins a vertex in
A with a vertex in B, neither A nor B contains more than 2n/3 vertices,
and C contains no more than $2\sqrt{2}\sqrt{2}$ vertices. We exhibit an
algorithm which finds such a partition A,B,C in O(n) time.
|
09:30-11:30 |
B11 MLH |
| 11/07 |
Gaurav |
"Optimal Hierarchical Decompositions for Congestion Minimization in Networks" Harold Raecke
Abstract
Hierarchical graph decompositions play an important role in the design
of approximation
and online algorithms for graph problems. This is mainly due to the
fact that the results
concerning the approximation of metric spaces by tree
metrics depend on hierarchical graph decompositions. In this line of
work a probability
distribution over tree graphs is constructed from a given input graph,
in such a way that
the tree distances closely resemble the distances in the original
graph. This allows it,
to solve many problems with a distance-based cost function on trees,
and then transfer
the tree solution to general undirected graphs with only a logarithmic
loss in the
performance guarantee.
The results about oblivious routing in general undirected graphs are based on
hierarchical decompositions of a different type in the sense that they
are aiming to
approximate the bottlenecks in the network (instead of the
point-to-point distances). We call such decompositions cutbased
decompositions. It has
been shown that they also can be used to design approximation and
online algorithms for a
wide variety of different problems, but at the current
state of the art the performance guarantee goes down by an O(log2 n
log log n)-factor
when making the transition from tree networks to general graphs.
In this paper we show how to construct cut-based decompositions that
only result in a
logarithmic loss in performance, which is asymptotically optimal.
Remarkably, one major
ingredient of our proof is a distance-based decomposition
scheme due to Fakcharoenphol, Rao and Talwar. This shows an
interesting relationship
between these seemingly different decomposition techniques.
The main applications of the new decomposition are an optimal O(log
n)-competitive
algorithm for oblivious routing in general undirected graphs, and an O(log
n)-approximation for Minimum Bisection, which improves the O(log1.5 n)
approximation by
Feige and Krauthgamer.
|
09:30-10:30 |
B11 MLH |
| 11/14 |
Kasturi |
Ongoing work on Geometric Set Cover
problem. |
09:30-11:30 |
B11 MLH |
| 11/21 |
Erik |
|
09:30-10:30 |
B11 MLH |
| 11/28 |
Thanksgiving Break |
|
|
|
| 12/05 |
Saurav |
|
09:30-10:30 |
B11 MLH |
| 12/12 |
Sriram |
|
09:30-11:30 |
B11 MLH |
| |
|
|
|
|
Coordinates:
When: Fridays, 9:30-11:30am.
Where: B-11 MLH.
|
|
| |
|
Home
• Research •
Teaching
©
Saurav Pandit. All Rights Reserved.
|
|
|