Algorithms Reading Group

Text Box: Welcome to Imran Pirwani's Webpage

Algorithms Reading Group
Coordinates:

Room B-13 MLH

Fridays: 1:00pm.-2:20pm.

Welcome to the Algorithms Reading Group. Our schedule for Fall 2007 is to meet every Friday at 1:00pm. in room B-13 MLH. If you would like to be on the mailing list then please email me.

For those who would like to speak, please email me the following:

1. Title

2. Author(s)

3. Citation

4. Web link to the paper

5. Abstract.

Please consult the following tables for our schedule and other details. This will be updated when necessary throughout the semester.

Seminar from previous semesters: Spring 2007, Fall 2006, Spring 2006, Fall 2005, Spring 2005, Fall 2004, Spring 2004, Fall 2003.

Date	Speaker	Title/Announcements/Comments
8/31	Imran Pirwani	"A Clustering Problem for Software Defined Radios" by V.S. Anil Kumar, Madhav Marathe, and Imran Pirwani In Progress
9/7	Erik Krohn	"A Constant-Factor Approximation Algorithm for Optimal Terrain Guarding" by Boaz Ben-Moshe, Matthew J. Katz and Joseph S. B. Mitchell In SODA 2005
9/14	Matt Gibson	"Restricted Strip Covering and the Sensor Cover Problem" by Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian, Ke Yi In SODA 2007
9/21	Imran Pirwani	"Good Quality Virtual Realization of Unit Disk Graphs" by Sriram Pemmaraju and Imran Pirwani In ESA 2007
9/28	Sriram Pemmaraju
10/5	Saurav Pandit
10/12	Benton McCune
10/19	Kasturi Varadarajan
10/26	Gaurav Kanade
11/2	Matt Gibson
11/9	Erik Krohn
11/16	Saurav Pandit
11/23
11/30	Benton McCune
12/7	Gaurav Kanade

Abstracts:
8/31	Given a network modeled by a graph and a set of available frequencies at each node, we define a graph partitioning problem subject to some constraints with the objective of minimizing the size of the partition. We show that the problem is NP-complete. We then show that the reduction used preserves so much of the structure of the problem that one can use the same reduction to show that the clustering problem is also ln n hard to approximate as well under reasonable complexity theoretic assumptions. We consider some natural greedy heuristics and show that they perform poorly (\Omega(n^{epsilon}), for any 0 < epsilon < 1) on even simple graph classes such as planar graphs and unit disk graphs with constant degree. The status of the problem is unclear even on trees, it seems.
9/7	We present the first constant-factor approximation algorithm for a non-trivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an O(1)-approximation up algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic-factor approximations follow from set cover results, our new results exploit geometric structure of terrains to obtain a substantially improved approximation algorithm. The paper can be found here.
9/14	Suppose we are given a set of objects that cover a region and a duration associated with each object. Viewing the objects as jobs, can we schedule their beginning times to maximize the length of time that the original region remains covered? We call this problem the Sensor Cover Problem. It arises in the context of covering a region with sensors. For example, suppose you wish to monitor activity along a fence (interval) by sensors placed at various fixed locations. Each sensor has a range (also an interval) and limited battery life. The problem is then to schedule when to turn on the sensors so that the fence is fully monitored for as long as possible. This one-dimensional problem involves intervals on the real line. Associating a duration to each yields a set of rectangles in space and time, each specified by a pair of fixed horizontal endpoints and a height. The objective is to assign a bottom position to each rectangle (by moving them up or down) so as to maximize the height at which the spanning interval is fully covered. We call this one-dimensional problem Restricted Strip Covering. If we replace the covering constraint by a packing constraint (rectangles may not overlap, and the goal is to minimize the highest point covered), then the problem becomes identical to Dynamic Storage Allocation, a well-studied scheduling problem, which is in turn a restricted case of the well known problem Strip Packing. We present a collection of algorithms for Restricted Strip Covering. We show that the problem is NP-hard and present an O(log log log n)-approximation algorithm. We also present better approximation or exact algorithms for some special cases, including when all intervals have equal width. For the general Sensor Cover Problem, we distinguish between cases in which elements have uniform or variable durations. The results depend on the structure of the region to be covered: We give a polynomial-time, exact algorithm for the uniform-duration case of Restricted Strip Covering but prove that the uniform-duration case for higher-dimensional regions is NP-hard. We give some more specific results for two-dimensional regions. Finally, we consider regions that are arbitrary sets, and we present an O(log n)-approximation algorithm for the most general case. The paper can be found here.
9/21	Given a unit disk graph (UDG) with only connectivity information (no geometric model), we compute an approximate embedding into the Euclidean plane of the graph (a realization) that seeks to minimize the ratio of the longest edge and the shortest non-edge. The approximation ratio achieved is log^2.5n; the construction is combinatorial. This is an improvement over the best known approximation of log³n times lower order terms which requires solving an LP with exponentially many constraints. We also provide a (k, √log n)-volume respecting embedding (in O(log³n) dimensions) of a growth restricted graph which corresponds to a clique partition of the given UBG. We also provide an O(1) quality embedding of the UBG in O(1) dimensions. The key structure (the cluster graph) is based upon a partition of the neighborhood of a vertex into O(1) cliques without any geometry. A consequence of this is a first polynomial time (computational complexity of each node), fully distributed O(1) factor approximation to the minimum clique cover of a UDG without geometry in deterministic O(log Δ log* n) rounds or O(log log n log* n) rounds w.h.p (due to a recent result). The paper can be found here.
9/28	The Koebe Representation Theorem (Koebe, 1930) states that for every planar graph G = (V, E), there exists a collection C of pairwise interior-disjoint disks in the plane and a one-to-one correspondence between V and C such that {u, v} is in E iff the disks corresponding to u and v are mutually tangent. This theorem was rediscovered by Andre'ev (1970) and Thurston (1985). I will present a (non-constructive) proof of the Koebe Representation Theorem and mention some old applications in graph drawing and recent applications in routing on wireless networks. The proof is from "Combinatorial Geometry" by Pach and Agarwal. One connection to routing in wireless networks can be seen in "On a conjecture related to geometric routing" by Christos H. Papadimitriou and David Ratajczak, Theoretical Computer Science, Vol 344 (1), Nov 2005.
10/5
10/12
10/19