In this paper, we investigate the problem of online task scheduling of jobs such as MapReduce jobs, Monte Carlo simulations and generating search index from web documents, on cloud computing infrastructures. We consider the virtualized cloud computing setup comprising machines that host multiple identical virtual machines (VMs) under pay-as-you-go charging, and that booting a VM requires a constant setup time. The cost of job computation depends on the number of VMs activated, and the VMs can be activated and shutdown on demand. We propose a new bi-objective algorithm to minimize the maximum task delay, and the total cost of the computation. We study both the clairvoyant case, where the duration of each task is known upon its arrival, and the more realistic non-clairvoyant case.

We study the following load balancing problem on paths (PB). There is a path containing n vertices. Every vertex i has an initial load h i , and every edge (j, j + 1) has an initial load w j that it needs to distribute among the two vertices that are its endpoints. The goal is to distribute the load of the edges over the vertices in a way that will make the loads of the vertices as balanced as possible (formally, mini- mizing the sum of squares of loads of the vertices). This problem can be solved in polynomial time, e.g, by dynamic programming. We present an algorithm that solves this problem in time O(n log n). As a mental aide in the design of our algorithm, we first design a hy- draulic apparatus composed of bins (representing vertices), tubes (rep- resenting edges) that are connected between bins, cylinders within the tubes that constrain the flow of water, and valves that can close the con- nections between bins and tubes. Water may be poured into the various bins, to levels that correspond to the initial loads in the input to the PB problem. When all valves are opened, the water flows between bins (to the extent that is feasible due to the cylinders) and stabilizes at levels that are the correct output to the respective PB problem. Our algorithm is based on a fast simulation of the behavior of this hydraulic apparatus, when valves are opened one by one.

We describe a real-time bidding algorithm for performance-based display ad allocation. A central issue in performance display advertising is matching campaigns to ad impressions, which can be formulated as a constrained optimization problem that maximizes revenue subject to constraints such as budget limits and inventory availability. The current practice is to solve the optimization problem offline at a tractable level of impression granularity (e.g., the placement level), and to serve ads online based on the precomputed static delivery scheme. Although this offline approach takes a global view to achieve optimality, it fails to scale to ad delivery decision making at an individual impression level. Therefore, we propose a real-time bidding algorithm that enables fine-grained impression valuation (e.g., targeting users with real-time conversion data), and adjusts value-based bid according to real-time constraint snapshot (e.g., budget consumption level). Theoretically, we show that under a linear programming (LP) primal-dual formulation, the simple real-time bidding algorithm is indeed an online solver to the original primal problem by taking the optimal solution to the dual problem as input. In other words, the online algorithm guarantees the offline optimality given the same level of knowledge an offline optimization would have. Empirically, we develop and experiment with two real-time bid adjustment approaches to adapting to the non-stationary nature of the marketplace: one adjusts bids against real-time constraint satisfaction level using control-theoretic methods, and the other adjusts bids also based on the historical bidding landscape statistically modeled. Finally, we show experimental results with real-world ad serving data.

We present a new technique for analyzing the rate of convergence of local dynamics in bargaining networks. The technique reduces balancing in a bargaining network to optimal play in a random-turn game. We analyze this game using techniques from martingale and Markov chain theory. We obtain a tight polynomial bound on the rate of convergence for a nontrivial class of unweighted graphs (the previous known bound was exponential). Additionally, we show this technique extends naturally to many other graphs and dynamics.

Identical products being sold at different prices in different locations is a common phenomenon. To model such scenarios, we supplement the classical Fisher market model by introducing {\em transaction costs}. For every buyer $i$ and good $j$, there is a transaction cost of $c_{ij}$; if the price of good $j$ is $p_j$, then the cost to the buyer $i$ {\em per unit} of $j$ is $p_j + c_{ij}$. The same good can thus be sold at different (effective) prices to different buyers. We provide a combinatorial algorithm that computes $\epsilon$-approximate equilibrium prices and allocations in $O\left(\frac{1}{\epsilon}(n+\log{m})mn\log(B/\epsilon)\right)$ operations - where $m$ is the number goods, $n$ is the number of buyers and $B$ is the sum of the budgets of all the buyers.

We improve the best known competitive ratio (from 1/4 to 1/2), for the online multi-unit allocation problem, where the objective is to maximize the single-price revenue. Moreover, the competitive ratio of our algorithm tends to 1, as the bid-profile tends to "smoothen". This algorithm is used as a subroutine in designing truthful auctions for the same setting: the allocation has to be done online, while the payments can be decided at the end of the day. Earlier, a reduction from the auction design problem to the allocation problem was known only for the unit-demand case. We give a reduction for the general case when the bidders have decreasing marginal utilities. The problem is inspired by sponsored search auctions.

We exhibit a new computational-based definition of awareness, informally that our level of unawareness of an object is the amount of time needed to generate that object within a certain environment. We give several examples to show this notion matches our intuition in scenarios where one organizes, accesses and transfers information. We also give a formal process-independent definition of awareness based on Levin's universal enumeration. We show the usefulness of computational awareness by showing how it relates to decision making, and how others can manipulate our decision making with appropriate advertising, in particular, we show connections to sponsored search and brand awareness. Understanding awareness can also help rate the effectiveness of various user interfaces designed to access information.

We consider markets in the classical Arrow-Debreu model. There are n agents and m goods. Each buyer has a concave utility function (of the bundle of goods he/she buys) and an initial bundle. At an ``equilibrium'' set of prices for goods, if each individual buyer separately exchanges the initial bundle for an optimal bundle at the set prices, the market clears, i.e., all goods are exactly consumed. Classical theorems guarantee the existence of equilibria, but computing them has been the subject of much recent research. In the related area of Multi-Agent Games, much attention has been paid to the complexity as well as algorithms. While most general problems are hard, polynomial time algorithms have been developed for restricted classes of games, when one assumes the number of strategies is constant.

For the Market Equilibrium problem, several important special cases of utility functions have been tackled. Here we begin a program for this problem similar to that for multi-agent games, where general utilities are considered. We begin by showing that if the utilities are separable piece-wise linear concave (PLC) functions, and the number of goods (or alternatively the number of buyers) is constant, then we can compute an exact equilibrium in polynomial time. Our technique for the constant number of goods is to decompose the space of price vectors into cells using certain hyperplanes, so that in each cell, each buyer's threshold marginal utility is known. Still, one needs to solve a linear optimization problem in each cell. We then show the main result - that for general (non-separable) PLC utilities, an exact equilibrium can be found in polynomial time provided the number of goods is constant. The starting point of the algorithm is a ``cell-decomposition'' of the space of price vectors using polynomial surfaces (instead of hyperplanes). We use results from computational algebraic geometry to bound the number of such cells. For solving the problem inside each cell, we introduce and use a novel LP-duality based method. We note that if the number of buyers and agents both can vary, the problem is PPAD hard even for the very special case of PLC utilities such as Leontief utilities and separable PLC utilities.

Determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to define an LP whose dual is equivalent to this relaxation. This opens up the possibility of using the primal-dual schema in a geometric setting for designing an algorithm for this problem. Using this approach, we obtain a 4/3 factor algorithm and integrality gap bound for the case of quasi-bipartite graphs; the previous best integrality gap upper bound being 3/2. We also obtain a factor $sqrt{2}$ strongly polynomial algorithm for this class of graphs. A key difficulty experienced by researchers in working with the bidirected cut relaxation was that any reasonable dual growth procedure produces extremely unwieldy dual solutions. A new algorithmic idea helps finesse this difficulty - that of reducing the cost of certain edges and constructing the dual in this altered instance - and this idea can be extracted into a new technique for running the primal-dual schema in the setting of approximation algorithms.

A vertex k-labeling of graph G is distinguishing if the only automorphism that preserves the labels of G is the identity map. The distinguishing number of G, D(G), is the smallest integer k for which G has a distinguishing k-labeling. In this paper, we apply the principle of inclusion-exclusion and develop recursive formulas to count the number of inequivalent distinguishing k-labelings of a graph. Along the way, we prove that the distinguishing number of a planar graph can be computed in time polynomial in the size of the graph.

In this paper, we study competitive markets - a market is competitive if increasing the endowment of any one buyer does not in- crease the equilibrium utility of any other buyer. In the Fisher setting, competitive markets contain all markets with weak gross substitutabil- ity (WGS), a property which enable efficient algorithms for equilibrium computation. We show that every uniform utility allocation (UUA) market which is competitive, is a submodular utility allocation (SUA) market. Our result provides evidence for the existence of efficient algoritheorems for the class of competitive markets.

The property of Weak Gross Substitutibility (WGS) of goods in a market has been found to be conducive to efficient algorithms for finding equilibria. In this paper, we give a natural definition of a $\delta$ approximate WGS property, and show that the auction algorithm of Garg and Kapoor can be extended to give an $\epsilon + \delta$ approximate equilibrium for markets with this property.

We study the structure of EG(2) markets, the class of Eisenberg-Gale markets with two agents. We prove that all markets in this class are rational and they admit strongly polynomial algorithms whenever the polytope containing the set of feasible utilities of the two agents can be described via a combinatorial LP. This helps resolve positively the status of two markets left as open problems by Jain and Vazirani: the capacity allocation market in a directed graph with two source-sink pairs and the network coding market in a directed network with two sources. Our algorithms for solving the corresponding nonlinear convex programs are fundamentally different from those obtained by Jain and Vazirani; whereas they use the primal- dual schema, we use a carefully constructed binary search.

Arora, Rao and Vazirani showed that the standard semi-definite programming (SDP) relaxation of the sparsest cut problem with the triangle inequality constraints has an integrality gap of $O(\sqrt{\log n})$. They conjectured that the gap is bounded from above by a constant. In this paper, we disprove this conjecture by constructing an $\Omega(\log \log n)$ integrality gap instance. Khot and Vishnoi had earlier disproved the non-uniform version of this Conjecture. A simple ``stretching'' of the integrality gap instance for the sparsest cut problem serves as an $\Omega(\log \log n)$ integrality gap instance for the SDP relaxation of the Minimum Linear Arrangement problem. This SDP relaxation was considered in Charikar et. al. and Feige and Lee, where it was shown that its integrality gap is bounded from above by $O(\sqrt{\log n} \log \log n).$

In this paper, we define a network service provider game. We show that the price of anarchy of the defined game can be bounded by analyzing a local search heuristic for a related facility location problem called the $k$-facility location problem. As a result, we show that the $k$-facility location problem has a locality gap of 5. This result is of interest on its own. Our result gives evidence to the belief that the price of anarchy of certain games are related to analysis of local search heuristics.

Hilbert posed the following problem as the 17th in the list of 23 problems in his famous 1900 lecture: Given a multivariate polynomial that takes only non-negative values over the reals, can it be represented as a sum of squares of rational functions? In 1927, E.~Artin gave an affirmative answer to this question. His result guaranteed the existence of such a finite representation and raised the following important question: What is the {\bf minimum number} of rational functions needed to represent any non-negative $n$-variate, degree $d$ polynomial? In 1967, Pfister proved that any $n$-variate non-negative polynomial over the reals can be written as sum of squares of at most $2^n$ rational functions. In spite of a considerable effort by mathematicians for over 75 years, it is not known whether $n+2$ rational functions are sufficient! In lieu of the lack of progress towards the resolution of this question, we initiate the study of Hilbert's 17th problem from the point of view of Computational Complexity. In this setting, the following question is a natural relaxation: What is the {\bf descriptive complexity} of the sum of squares representation (as rational functions) of a non-negative, $n$-variate, degree $d$ polynomial? We consider arithmetic circuits as a natural representation of rational functions. We are able to show, assuming a standard conjecture in complexity theory, that it is impossible that every non-negative, $n$-variate, degree four polynomial can be represented as a sum of squares of a small (polynomial in $n$) number of rational functions, each of which has a small size arithmetic circuit (over the rationals) computing it.

Our result points to the direction that it is unlikely that every non-negative, $n$-variate polynomial over the reals can be written as a sum of squares of a polynomial (in $n$) number of rational functions. Further, relating to standard (and believed to be hard to prove) complexity-theoretic conjectures sheds some light on why it has been difficult for mathematicians to close the $n+2$ and $2^n$ gap. We hope that our line of work will play an important role in the resolution of this question.

The traditional model of market equilibrium supports impressive existence results, including the celebrated Arrow-Debreu Theorem. However, in this model, polynomial time algorithms for computing (or approximating) equilibria are known only for linear utility functions. We present a new, and natural, model of market equilibrium that not only admits existence and uniqueness results paralleling those for the traditional model but is also amenable to efficient algorithms.

Recently, Jain, Mahdian and Saberi had given a FPTAS for the problem of computing a market equilibrium in the Arrow-Debreu setting, when the utilities are linear functions. Their running time depended on the size of the numbers representing the utilities and endowments of the buyers. In this paper, we give a strongly polynomial time approximation scheme for this problem. Our algorithm builds upon the main ideas behind the algorithm in Devanur et. al.

Strategyproof cost-sharing mechanisms, lying in the core, that recover $1/\alpha$ fraction of the cost, are presented for the set cover and facility location games; $\alpha = O(\log n)$ for the former and 1.861 for the latter. Our mechanisms utilize approximation algorithms for these problems based on the method of dual-fitting.

We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal-dual paradigm in the enhanced setting of KKT conditions and convex programs. We pinpoint the added difficulty raised by this setting and the manner in which our algorithm circumvents it.