In this paper we propose a utility model that accounts for both sales and branding advertisers. We first study the computational complexity of optimization problems related to both online and offlineallocation of display advertisements. Next, we focus on a particular instance of the online allocation problem, and design a simple online algorithm with provable approximation guarantees. Our algorithm is near optimal as is shown by a matching lower bound.Finally, we report on experiments to establish actual case behavior on some real datasets, with encouraging results.

In the context of auctions of digital goods, an interesting Random Sampling Auction has been proposed by Goldberg, Hartline and Wright; this leads to a truthful mechanism. Since random sampling is apopular approach for auctions that aim to maximize the seller's revenue, this method has been analyzed further by Feige, Flaxman, Hartline and Kleinberg, who have shown that it is substantially more competitive than known before. In this work, we further improve upon the bounds on the competitiveness through a mix of probabilistic techniques and computer-aided analysis, leading to near-optimal bounds.

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.
 

Abstract:
In this paper we extend the notion of submodularity to functions defined over sequences and analyze the greedy algorithm for maximizing such functions subject to a maximum length constraint on the solution sequence. A large class of combinatorial problems can be modeled in this framework specially those that involve time. As an example, we model the online ad allocation problem directly in this framework which immediately implies that a greedy approach gives a 1-1/e approximation assuming that the queries are iid random variable coming from a fixed but unknown distribution. In this work, we extend the notion of submodularity defined by Nemhauser for set functions to the more general class of sequence function (A set function is a special case of a sequence function in which the order and frequency of elements don't matter).

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.