Research

I am primarily interested in algorithmic research.  My research interests expand to design and analysis of algorithms, approximation algorithms in both sequential and distributed models of computation, graph theory, combinatorial optimization, and computational geometry. The focus of my research these days is algorithmic problems on reasonable graph theoretic/geometric models for wireless networks motivated by real problems in such networks. Here's a research statement detailing my research interests and work. The following is a list of the papers that I have co-authored:

Journal:

1. Clustering to Minimize the Sum of Radii.

   With Matt Gibson, Gaurav Kanade, Erik Krohn, and Kasturi Varadarajan. Invited to the Special Issue of Algorithmica dedicated to SWAT 2008.

2. Topology Control and Geographic Routing in Realistic Wireless Networks.

   With Kevin M. Lillis and Sriram V. Pemmaraju.  Invited to the Special Issue of Ad Hoc & Sensor Wireless Networks: An International Journal.

Conference:

1. On the Complexity of Minimum Partition of Frequency-Agile Networks

   With V.S. Anil Kumar, Madhav V. Marathe, and Sriram V. Pemmaraju.  To appear in IEEE Dyspan 2008

2. On Metric Clustering to Minimize the Sum of Radii.

   With Matt Gibson, Gaurav Kanade, Erik Krohn, and Kasturi Varadarajan.  Appeared in SWAT 2008 .
   Abstract
   Given an n-point metric (P,d) and an integer k > 0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in n^{O(log n log Δ)} time and returns with high probability the optimal solution. Here, Δ is the ratio between the maximum and minimum interpoint distances in the metric space. We also show that the problem is NP-hard, even in metrics induced by weighted planar graphs and in metrics of constant doubling dimension.

3. On Clustering to Minimize the Sum of Radii.

   With Matt Gibson, Gaurav Kanade, Erik Krohn, and Kasturi Varadarajan.  Appeared in SODA 2008 .
   Abstract
   Given a set of n input points in the Euclidean plane and an integer k, the goal is to place at most k disks at the input points so as to cover all of them. Define the cost of a disk as its radius and a solution as the sum of costs of the disks. The goal is to find a minimum cost cover. We give an exact algorithm for this problem that runs in poly-time if two sums of square roots of rational number can be compared in poly-time.

4. Good Quality Virtual Realization of Unit Ball Graphs.

   With Sriram V. Pemmaraju.  Appeared in ESA 2007 .
Abstract
Given a unit disk graph (UDG) in general form, we consider the problem of devising a "good quality" embedding in the Euclidean plane for it. "Quality" of an embedding has been defined as the ratio of the length of the longest edge to the length of the shortest non-edge. We give a combinatorial algorithm that gives a O(log^2.5 n) quality embedding of an input UDG specified in general form.

5. Topology Control and Geographic Routing in Realistic Wireless Networks.

   With Kevin M. Lillis and Sriram V. Pemmaraju.  Appeared in Adhoc-Now 2007.
Abstract
Given a alpha-quasi-unit disk graph (qUDG) (alpha >= 1/sqrt(2)) we consider the problem of robust and memoryless geographic routing on such graphs. We compute, in O(1) rounds of distributed computation, a sparse, O(1)-spanner, both in Euclidean and hop distance. This structure permits such routing which is optimal for any geographic routing protocol. We also present a scheme that performs load-balancing on the graph so that any single back-bone is not overloaded by routing requests.

6. Energy Conservation via Domatic Partitions.

   With Sriram V. Pemmaraju.  Appeared in MobiHoc 2006 .
Abstract
We consider the problem of maximizing the number of disjoint dominating sets for certain classes of graphs that commonly model wireless networks. We consider the problem on d-dimen. unit ball graphs in Euclidean space, unit ball graphs in doubling metric space, and growth independence graphs. We almost (sadly, not quite) give a constant-factor approximation to the problem on all these graphs in O(1), O(log^* n), and O(log^* n log Δ) rounds of distributed computation, respectively.

7. Oriented Edge Colorings and Link Scheduling in Sensor Networks.

   With Ted Herman and Sriram Pemmaraju.  Appeared in SENSORWARE/COMSWARE 2006.
Abstract
We consider the problem of finding a TDMA slot assignment for unicast communication in a wireless network on an acyclic network. We give a randomized algorithm that computes w.h.p., in poly-log(n) rounds of distributed computation, a collision-free schedule of nearly 2*Δ time slots.

8. Introduction to Non-rigid Image Registration Evaluation Project.

   With Gary Christensen, Xiujuan Geng, Jon Kuhl, Joel Bruss, Thomas Grabowski, Michael Vannier, John Allen, and Hanna Damasio.  Appeared in WBIR 2006.
Abstract
Non-rigid image registration (NIR) is an important tool that allows for morphological comparisons in the presence or anatomical variations. While many NIR algorithms have been devised, they are difficult to evaluate in the absence of point-wise inter-image correspondence. We provide a framework that allows for evaluation of these algorithms.

9. A Composite Stabilizing Data Structure.

   With Ted Herman.  Appeared in WSS 2001 .
Abstract
We present a composite data structure that is both available and stabilizing. It is stabilizing in the sense that it is resilient to transient faults occurring in that over the course of time as the data structure is operated upon, it corrects itself. It is available in the sense that while it is possibly in an illegitimate state, it is available to operations and a successful operation is guaranteed to change the state of the data structure in an expected manner.

Manuscripts/Reports:

1. On k-domination of Graphs.

   Ph.D. Comprehensive Examination.

2. A Self-Stabilizing Algorithm for a Weaker form of Distributed Mutual Exclusion.

   Master's Thesis.

Talks:

1. Good Quality Virtual Realization of Unit Disk Graphs.

   55th. Midwest Theory Day Fall 2007. University of Chicago, Illinois, USA. November 2007.

2. Good Quality Virtual Realization of Unit Disk Graphs.

   15th. Annual European Symposium on Algorithms 2007.
Eilat, Israel. October 2007. (Tele-talk due to visa/travel restrictions.)

3. Extending the Lifetime of Wireless Networks while Ensuring Coverage.

   2006 SIAM Conference on Discrete Mathematics. Victoria, B.C., Canada. June 2006.

Contact:
Imran A. Pirwani
CCAD
111 ERF
University of Iowa
Iowa City, IA 52242
pirwani@cs.uiowa.edu