[Colloq] Hiring Talk: MohammadTaghi Hajiaghayi, Friday, April 6

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents a Hiring Talk By:
MohammadTaghi Hajiaghayi,
MIT & CMU

Who will speak on:
“Graph Algorithms for Wireless Network Design: Fault-Tolerance and Coverage”

Friday, April 6, 2007
10:00am
366 West Village H
Northeastern University

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.

Biography of Speaker:
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.

Host: Rajmohan Rajaraman