Events - Colloquia & Seminars

CCIS Colloquium Spring 2007

Graph Algorithms for Wireless Network Design: Fault-Tolerance and Coverage

Speaker: MohammadTaghi Hajiaghayi

Affiliation: MIT & CMU

Date: Friday, April 6, 2007

Talk: 10:00 a.m., 366 WVH

Abstract

In this talk, we present real-world applications with deep theoretical underpinnings and consequences and show how wireless multi-hop networks, algorithmic graph theory, computational geometry, computational economics and finally computational complexity have a nice intersection in this area. We mainly focus on the following two practical problems in wireless networks (near the end of the talk, time permitting, we highlight some of our related recent results on non-uniform buy-at-bulk, oblivious routing, online auctions and finally Bidimensionality theory).

First, we consider the concept of power optimization in fault-tolerant topology control algorithms for wireless multi-hop sensor networks. More formally, here our goal is to find a k-connected spanning subgraph of a given graph which minimizes the power. The power of a spanning subgraph is the sum of the powers of the nodes, and the power of each node is the weight of the maximum edge attached to that node in the subgraph. From the theoretical point of view, in this pioneering work, we show an O(k)-approximation algorithm and an O(log4 n)-approximation algorithm for this problem and some inapproximability results. From the practical point of view, we present efficient local heuristic algorithms and global and practical distributed approximation algorithms. We also compare different approximation algorithms and heuristics via simulation.

Second, we prove logarithmic approximability and almost-logarithmic inapproximability for a maximization problem called ``unique coverage'': given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. The unique coverage problem defined above is a natural maximization version of set cover which was brought to our attention from its applications in wireless networks. In one (simplified) application, we have a certain budget to build/place some transmitters at a subset of a specified set of possible locations.

Our goal is to maximize the clients that are ``covered'' by (i.e., are within the range of) exactly one transmitter; these are the clients that receive signal without interference. Specifically, we prove O(1/log^{sigma(epsilon)} n) inapproximability assuming that NP is not subseteq BPTIME(2^{n^epsilon}) for some epsilon > 0. We also prove O(1/log^{1/3-\epsilon} n) inapproximability, for any epsilon > 0, assuming that refuting random instances of 3SAT is hard on average. We establish matching upper bounds up to exponents, even for a more general (budgeted) setting, giving an Omega(1/log n)-approximation algorithm as well as an Omega(1/log B)-approximation algorithm when every set has at most B elements. We also show that our inapproximability results extend to envy-free pricing, an important problem in computational economics. We believe that unique coverage has the potential to be a central inapproximable maximization problem in the same way that set cover is for minimization problems.

Brief Biography

MohammadTaghi Hajiaghayi received the Bachelor's degree in Computer Engineering from Sharif University of Technology in 2000. He received the Master's degree in Computer Science from the University of Waterloo in 2001. Since September 2001, he is a Ph.D. candidate in Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology. During his Ph.D. studies, he also worked at the IBM T.J. Watson Research Center (Department of Mathematical Sciences) and at the Microsoft Research Center (Theory group). Currently, Dr. Hajiaghayi is a Postdoctoral Fellow in the School of Computer Science at Carnegie Mellon University with ALADDIN project. Before this from June 2005 to December 2005, he was a Postdoctoral Associate in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). His research interests are combinatorial optimizations and approximation algorithms, wireless and mobile computing, game theory and combinatorial auctions, computational geometry and embeddings and algorithmic graph theory.