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. Shifting Strategy for Graphs Without Geometry.

   To appear in the Special Issue of Journal of Combinatorial Optimization dedicated to ISAAC 2009.

2. Clustering to Minimize the Sum of Radii.

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

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

   With Kevin M. Lillis and Sriram V. Pemmaraju.  In Special Issue of Ad Hoc & Sensor Wireless Networks: An International Journal. Volume: 6, issue: 3-4, pp: 265-297 (2008).

Conference:

1. Approximation Algorithms for Dominating Set in Disk Graphs

   With Matt Gibson.  To be presented at ESA 2010
   Abstract
   Consider the intersecction graph defined by a collection of n disks in the plane. Our goal is to find a dominating of minimum cost. The problem has been extensively studied on various graph classes, including subclasses of disk graphs, yet, for disk graphs, nothing better than an O(log n) approximation was known. We improve the status quo in two ways: for the unweighted case, we show that a simple local search yields a PTAS; for the weighted case, we give a 2^O(log*n) approximation to an optimum solution. The first approach follows the framework of Mustafa-Ray [SoCG09] and Chan-Har-Peled [SoCG09], while the second follows the framework of Varadarajan [STOC10].

2. A Weakly-Robust PTAS for Minimum Clique Partition on Unit Disk Graphs

   With Mohammad Salavatipour.  To be presented at SWAT 2010
   Abstract
   We consider the problem of partitioning the vertex set of an input unit disk graph (UDG) into the fewest number of cliques; the problem is NP-hard. Various O(1) approximations are easily obtainable. We give a first PTAS for this problem. In fact, we give a (weakly) robust algorithm that takes as input a graph with associated edge-lengths (instead of coordinates for the vertices). If the input graph has a realization in the Euclidean plane, then our algorithm is a (1+ε)-approximation. If the input has no feasible UDG embedding, then the algorithm either terminates producing a certificate proving that the graph is not a UDG, or produces a clique partition without any guarantees on the size of the partition.
   We also consider a weighted version of the problem where even the edge-lengths aren't given -- the graph is expressed in general form. The vertices have weights. The weight of a clique is the weight of the heaviest vertex in the clique, and the goal is to produce a clique partition with the lightest weight. This generalizes the classical problem. We give a (weakly) robust (2+ε)-approximation for this problem. This improves on the best known 8-approximation for the unweighted version of the problem.

3. Shifting Strategy for Geometric Graphs Without Geometry

   Appeared at ISAAC 2009
   Abstract
   We give a simple framework which is an alternative to the celebrated shifting strategy of Hochbaum and Maass [J. ACM, 1985]. Our framework does not require the input graph to have a geometric realization -- it only requires that the input graph satisfy some weak property referred to as growth boundedness. As an application of the framework we show how to obtain PTAS for maximum (weighted) independent set problem on this graph class; the problem is NP-hard.
   Via a more sophisticated application of our framework, we also show how to obtain a PTAS for the maximum (weighted) independent set for intersection graphs of (low-dimensional) fat objects that are expressed without geometry. Erlebach et al. [SIAM J. Comput., 2005] and Chan [J. Algorithms, 2003] gave a PTAS for this problem for intersection graphs of fat objects. Their scheme required a geometric representation of the input. Our result gives a positive answer to a question of Erlebach et al. who asked if a PTAS for this problem can be obtained without access to geometry.

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

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

5. 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.

6. 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.

7. Good Quality Virtual Realization of Unit Ball Disk 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) O(log³ n) quality embedding of an input UDG specified in general form. We also show how to obtain a quality-2 embedding of the UDG if we are allowed to embed the graph in O(1)-dimensional Euclidean space, instead of strictly a Euclidean plane.
In the preliminary version which appeared in ESA-07, there is a technical flaw in obtaining a (k,O(log^0.5n)) volume respecting embedding of the cluster graph. Also, our result only applies to UDGs and not UBGs.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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. Scheduling and Embedding Algorithms for Wireless Networks

   Ph.D. Thesis.

2. On k-domination of Graphs.

   Ph.D. Comprehensive Examination.

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

   Master's Thesis.

Talks:

1. Partitioning a Radio Network into Fewest Cliques .

   12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010). Bergen, Norway. June 2010.

2. Shifting Strategy For Geometric Graphs Without Geometry.

   20th International Symposium on Algorithms and Computation (ISAAC 2009). Honolulu, Hawaii, USA. December 2009.

3. Good Quality Virtual Realization of Unit Disk Graphs.

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

4. 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.)

5. 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
Dept. of Computing Science
4-03 Athabasca Hall
University of Alberta
Edmonton, Alberta
Canada T6G 2E8
pirwani@cs.ualberta.ca