We consider the problem of query rewrites in the context of keyword  advertisement. Given a three-layer graph consisting of queries, query rewrites, and the corresponding ads that can be served for the rewrites, we formulate a family of graph covering problems whose goals are to suggest a subset of ads with the maximum benefit by suggesting rewrites instead. We obtain constant-factor approximation algorithms for these covering problems, under two versions of constraints and a realistic notion of ad benefit. We perform experiments on real data and show that our algorithms are capable of outperforming a competitive baseline algorithm in terms of the benefit of the rewrites.

In this paper we study a set of problems related to efficient energy management for monitoring applications in wireless sensor networks. We study several generalizations of a basic problem called Set k-Cover. The problem can be described as follows: we are given a set of sensors, and a set of regions to be monitored. Each region can be monitored by a subset of sensors. The goal is to partition the sensors into k sets so that by activating the set of sensors in a time-slot, we can maximize coverage of the regions.
This problem is known to be NP-hard. Our goal is to develop improved approximation algorithms for this problem. We compare the solution obtained by our algorithm to the previous method proposed for the same problem. We are also able to derive improved worst bounds for some cases.
We also consider generalizations of this problem in several different directions. First, we allow each sensor to be active in a different sets (time-slots). We also consider different coverage requirements, such as requiring that the regions be covered in each time slot, or a certain number of regions be monitored in each time slot. We develop a randomized rounding algorithm for this problem. We also consider extensions where each sensor can monitor only a bounded number of regions, and not all the regions adjacent to it.We develop the first approximation algorithms for this problem.

In this paper we study several routing problems that generalize shortest paths and the Traveling Salesman Problem.
We consider a more general model that incorporates the actual cost in terms of gas prices. We have a vehicle with a given tank capacity. In fact, we will assume that U is the distance the vehicle can travel on a full tank of gas. We assume that at each vertex gas may be purchased at a certain price. The objective is to find the cheapest route to go from s to t, or the cheapest tour visiting a given set of locations. Surprisingly, the problem of find the cheapest way to go from s to t can be solved in polynomial time and is not NP-complete. For most other versions however, the problem is NP-complete and we develop polynomial time approximation algorithms for these versions. Project
 

Our work is motivated by the need to manage data on a collection of storage devices to handle dynamically changing demand. As demand for data changes, the system needs to automatically respond to changes in demand for different data items. The problem of computing a migration plan among the storage devices is called the data migration problem.
This problem was shown to be NP-hard and the best known approximation ratio was 9.5 for the half-duplex communication model
In this paper we develop an improved approximation algorithm that gives a bound of 6.5+o(1) using various new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5.
We also consider the full duplex communication model and develop an improved bound of 4 +o(1) for this model, with no
external disks.
 

In most of the real situations, when we are formulating a problem, there are uncertainties about the input information we are using. In In the stochastic optimization problems we are trying to find the best solution by taking into account the uncertainty about the data. The specific problem that we studied in this context was the
facility location problem. In the stochastic facility location problem, there is uncertainty about the demand set. In this situation, we choose a primary set of facilities to open in the first round before knowing the real demand set and then after the real demand set is revealed we open some additional facilities to decrease the cost. There are different ways for modeling the uncertainty in the demand set. We used the scenario based model in which we are given polynomial number of scenarios with their associated probability. We present a 2.32 approximation algorithm for the stochastic facility location in the scenario based model.