In an instance of the network design problem, we are given a graph G=(V,E), an edge-cost function c:E -> R^{>= 0}, and a connectivity criterion. The goal is to find a minimum-cost subgraph H of G that meets the connectivity requirements. An important family of this class is the survivable network design problem (SNDP): given non-negative integers r_{u v} for each pair u,v in V, the solution subgraph H should contain r_{u v} edge-disjoint paths for each pair u and v. While this problem is known to admit good approximation algorithms in the offline case, the problem is much harder in the online setting. Gupta, Krishnaswamy, and Ravi [Gupta et al., 2012] (STOC'09) are the first to consider the online survivable network design problem. They demonstrate an algorithm with competitive ratio of O(k log^3 n), where k=max_{u,v} r_{u v}. Note that the competitive ratio of the algorithm by Gupta et al. grows linearly in k. Since then, an important open problem in the online community [Naor et al., 2011; Gupta et al., 2012] is whether the linear dependence on k can be reduced to a logarithmic dependency. Consider an online greedy algorithm that connects every demand by adding a minimum cost set of edges to H. Surprisingly, we show that this greedy algorithm significantly improves the competitive ratio when a congestion of 2 is allowed on the edges or when the model is stochastic. While our algorithm is fairly simple, our analysis requires a deep understanding of k-connected graphs. In particular, we prove that the greedy algorithm is O(log^2 n log k)-competitive if one satisfies every demand between u and v by r_{uv}/2 edge-disjoint paths. The spirit of our result is similar to the work of Chuzhoy and Li [Chuzhoy and Li, 2012] (FOCS'12), in which the authors give a polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. Moreover, we study the greedy algorithm in the online stochastic setting. We consider the i.i.d. model, where each online demand is drawn from a single probability distribution, the unknown i.i.d. model, where every demand is drawn from a single but unknown probability distribution, and the prophet model in which online demands are drawn from (possibly) different probability distributions. Through a different analysis, we prove that a similar greedy algorithm is constant competitive for the i.i.d. and the prophet models. Also, the greedy algorithm is O(log n)-competitive for the unknown i.i.d. model, which is almost tight due to the lower bound of [Garg et al., 2008] for single connectivity.

Moss and Rabani study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an $O(\log n)$-approximation algorithm for the node-weighted prize-collecting Steiner tree problem (PCST)---where the goal is to minimize the cost of a tree plus the penalty of vertices not covered by the tree. They use the algorithm for PCST to obtain a bicriteria $(2, O(\log n))$-approximation algorithm for the budgeted node-weighted Steiner tree problem---where the goal is to maximize the prize of a tree with a given budget for its cost. Their solution may cost up to twice the budget, but collects a factor $\Omega(\frac{1}{\log n})$ of the optimal prize. We improve these results from at least two aspects. Our first main result is a primal-dual $O(\log h)$-approximation algorithm for a more general problem, node-weighted prize-collecting Steiner forest (PCSF), where we have $h$ demands each requesting the connectivity of a pair of vertices. Our algorithm can be seen as a greedy algorithm which reduces the number of demands by choosing a structure with minimum cost-to-reduction ratio. This natural style of argument leads to a much simpler algorithm than that of Moss and Rabani for PCST. Our second main contribution is for the budgeted node-weighted Steiner tree problem, which is also an improvement to the work of Moss and Rabani. In the unrooted case, we improve upon an existing $O(\log^2 n)$-approximation by Guha et al., and present an $O(\log n)$-approximation algorithm without any budget violation. For the rooted case, where a specified vertex has to appear in the solution tree, we improve the bicriteria result of Moss and Rabani to the bicriteria approximation ratio of $(1+\epsilon, O(\log n)/\epsilon^2)$ for any positive (possibly subconstant) $\epsilon$. That is, for any permissible budget violation $1+\epsilon$, we present an algorithm achieving a trade off in the guarantee for the prize. Indeed, we show that this is almost tight for the natural linear-programming relaxation used by us as well as in the previous works.

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. When the input graph is planar, we present a simple and elegant streaming algorithm that, with high probability, estimates the size of a maximum matching within a constant factor using Õ( n 2/3 ) space, where n is the number of vertices. The approach generalizes to the family of graphs that have bounded arboricity, which include graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model (as opposed to the random-order streaming model) in o ( n ) space. We circumvent the barriers inherent in the adversarial-order model by exploiting several structural properties of planar graphs, and more generally, graphs with bounded arboricity. We further reduce the required memory size to Õ(√ n ) for three restricted settings: (i) when the input graph is a forest; (ii) when we have 2-passes and the input graph has bounded arboricity; and (iii) when the edges arrive in random order and the input graph has bounded arboricity. Finally, we design a reduction from the Boolean Hidden Matching Problem to show that there is no randomized streaming algorithm that estimates the size of the maximum matching to within a factor better than 3/2 and uses only o ( n 1/2 ) bits of space. Using the same reduction, we show that there is no deterministic algorithm that computes this kind of estimate in o ( n ) bits of space. The lower bounds hold even for graphs that are collections of paths of constant length.

In this paper we study a stochastic variant of the celebrated $k$-server problem. In the k-server problem, we are required to minimize the total movement of k servers that are serving an online sequence of $t$ requests in a metric. In the stochastic setting we are given t independent distributions in advance, and at every time step i a request is drawn from P_i. Designing the optimal online algorithm in such setting is NP-hard, therefore the emphasis of our work is on designing an approximately optimal online algorithm. We first show a structural characterization for a certain class of non-adaptive online algorithms. We prove that in general metrics, the best of such algorithms has a cost of no worse than three times that of the optimal online algorithm. Next, we present an integer program that finds the optimal algorithm of this class for any arbitrary metric. Finally by rounding the solution of the linear relaxation of this program, we present an online algorithm for the stochastic k-server problem with an approximation factor of $3$ in the line and circle metrics and factor of O(log n) in general metrics. In this way, we achieve an approximation factor that is independent of k, the number of servers. Moreover, we define the Uber problem, motivated by extraordinary growth of online network transportation services. In the Uber problem, each demand consists of two points -a source and a destination- in the metric. Serving a demand is to move a server to its source and then to its destination. The objective is again minimizing the total movement of the k given servers. It is not hard to show that given an alpha-approximation algorithm for the k-server problem, we can obtain a max{3,alpha}-approximation algorithm for the Uber problem. Motivated by the fact that demands are usually highly correlated with the time (e.g. what day of the week or what time of the day the demand is arrived), we study the stochastic Uber problem. Using our results for stochastic k-server we can obtain a 3-approximation algorithm for the stochastic Uber problem in line and circle metrics, and a O(log n)-approximation algorithm for a general metric of size n. Furthermore, we extend our results to the correlated setting where the probability of a request arriving at a certain point depends not only on the time step but also on the previously arrived requests.

We give the first polynomial-time online algorithm for the node-weighted Steiner forest problem with a poly-logarithmic competitive ratio. The competitive ratio of our algorithm is optimal up to a logarithmic factor. For the special case of graphs with an excluded fixed minor (e.g., planar graphs), we obtain a logarithmic competitive ratio, which is optimal up to a constant, using a different online algorithm. Both these results are obtained as special cases of generic results for a large class of problems that can be encoded as online $\{0, 1\}$- proper functions. Our results are obtained by using a new framework for online network design problems that we call disk paintings. The central idea in this technique is to amortize the cost of primal updates to a set of carefully selected mutually disjoint fixed-radius dual disks centered at a subset of terminals. We hope that this framework will be useful for other online network design problems.

Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of $0.5$. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of $1/e\approx 0.36$ In this paper, we introduce prophet secretary, a natural combination of the prophet inequality and the secretary problems. In the prophet secretary problem we are given a set $\{D_1,\ldots,D_n\}$ of (not necessarily identical) distributions. A number $X_i$ is drawn from each distribution $D_i$ and then, after applying a random permutation $\pi_1,\ldots, \pi_n$, the numbers are given to us in an online fashion, i.e., at step $k$, $X_{\pi_k}$ is revealed. We are allowed to choose only one number, which can be done only upon receiving that number. The goal is to maximize the expectation of the chosen value, compared to the expectation of the optimum offline solution that knows the drawn values in advance. In particular, we show that by using a single uniform threshold one cannot break the 0.5 barrier of the prophet inequality for the prophet secretary problem. However, we show that $\bullet$ using $n$ distinct nonadaptive thresholds one can obtain a competitive ratio that goes to $(1-1/e \approx 0.63)$ as $n$ grows, and $\bullet$ no online algorithm can achieve a competitive ratio better than 0.75. Our results improve the (asymptotic) approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to $(1-1/e)$ when the order of agents (customers) is chosen randomly. We also consider the minimization variants of stopping theory problems and, in particular, the prophet secretary problem. Interestingly, we show that, even for the simple case in which the input elements are drawn from identical and independent distributions, there is no constant competitive online algorithm for the minimization variant of the prophet secretary problems. We extend this hardness result to the minimization variants of both the prophet inequality and the secretary problem as well.

Motivated by the importance of energy storage networks in smart grids, we provide an algorithmic study of the online energy storage management problem in a network setting, the first to the best of our knowledge. Given online power supplies, either entirely renewable supplies or those in combination with traditional supplies, we want to route power from the supplies to demands using storage units subject to a decay factor. Our goal is to maximize the total utility of satisfied demands less the total production cost of routed power. We model renewable supplies with the zero production cost function and traditional supplies with convex production cost functions. For two natural storage unit settings, private and public, we design poly-logarithmic competitive algorithms in the network flow model using the dual fitting and online primal dual methods for convex problems. Furthermore, we show strong hardness results for more general settings of the problem. Our techniques may be of independent interest in other routing and storage management problems.

We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest (EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic approach for solving mixed packing/covering integer programs in the online paradigm. In EW-DB-SF, we are given an edge-weighted graph with a degree bound for every vertex. Given a root vertex in advance, we receive a sequence of terminal vertices in an online manner. Upon the arrival of a terminal, we need to augment our solution subgraph to connect the new terminal to the root. The goal is to minimize the total weight of the solution while respecting the degree bounds on the vertices. In the offline setting, edge-weighted degree-bounded Steiner tree (EW-DB-ST) and its many variations have been extensively studied since early eighties. Unfortunately, the recent advancements in the online network design problems are inherently difficult to adapt for degree-bounded problems. In particular, it is not known whether the fractional solution obtained by standard primal-dual techniques for mixed packing/covering LPs can be rounded online. In contrast, in this paper we obtain our result by using structural properties of the optimal solution, and reducing the EW-DB-SF problem to an exponential-size mixed packing/covering integer program in which every variable appears only once in covering constraints. We then design a generic integral algorithm for solving this restricted family of IPs. As mentioned above, we demonstrate a new technique for solving mixed packing/covering integer programs. Define the covering frequency k of a program as the maximum number of covering constraints in which a variable can participate. Let m denote the number of packing constraints. We design an online deterministic integral algorithm with competitive ratio of O(k*log(m)) for the mixed packing/covering integer programs. We prove the tightness of our result by providing a matching lower bound for any randomized algorithm. We note that our solution solely depends on m and k. Indeed, there can be exponentially many variables. Furthermore, our algorithm directly provides an integral solution, even if the integrality gap of the program is unbounded. We believe this technique can be used as an interesting alternative for the standard primal-dual techniques in solving online problems.

We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem – which asks for a subgraph with minimum degree that connects a given set of vertices – is perhaps one of the most representative problems in this class. This paper deals with its well-studied generalization called the degree-bounded Steiner forest problem where the connectivity demands are represented by vertex pairs that need to be individually connected. In the classical online model, the input graph is given offline but the demand pairs arrive sequentially in online steps. The selected subgraph starts off as the empty subgraph, but has to be augmented to satisfy the new connectivity constraint in each online step. The goal is to be competitive against an adversary that knows the input in advance. The standard techniques for solving degree-bounded problems often fall in the category of iterative and dependent rounding techniques. Unfortunately, these rounding methods are inherently difficult to adapt to an online settings since the underlying fractional solution may change dramatically in between the rounding steps. Indeed, this might be the very reason that despite many advances in the online network design paradigm in the past two decades, the natural family of degree-bounded problems has remained widely open. In this paper, we design an intuitive greedy-like algorithm that achieves a competitive ratio of O(log n) where n is the number of vertices. We show that no (randomized) algorithm can achieve a (multiplicative) competitive ratio o(log n); thus our result is asymptotically tight. We further show strong hardness results for the group Steiner tree and the edge-weighted variants of degree-bounded connectivity problems. Fürer and Raghavachari resolved the offline variant of degree-bounded Steiner forest in their paper in SODA'92. Since then, the family of degree-bounded network design problems has been extensively studied in the literature resulting in the development of many interesting tools and numerous papers on the topic. We hope that our approach and its dual analysis, paves the way for solving the online variants of the classical problems in this family of problems.

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. When the input graph is planar, we present a simple and elegant streaming algorithm that with high probability estimates the size of a maximum matching within a constant factor using space, where n is the number of vertices. The approach generalizes to the family of graphs that have bounded arboricity, which include graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model (as opposed to the random-order streaming model) in o(n) space. We circumvent the barriers inherent in the adversarial-order model by exploiting several structural properties of planar graphs, and more generally, graphs with bounded arboricity. We further reduce the required memory size to for three restricted settings: (i) when the input graph is a forest; (ii) when we have 2-passes and the input graph has bounded arboricity; and (iii) when the edges arrive in random order and the input graph has bounded arboricity. Finally, we design a reduction from the Boolean Hidden Matching Problem to show that there is no randomized streaming algorithm that estimates the size of the maximum matching to within a factor better than 3/2 and uses only o(n1/2) bits of space. Using the same reduction, we show that there is no deterministic algorithm that computes this kind of estimate in o(n) bits of space. The lower bounds hold even for graphs that are collections of paths of constant length.

We give the first polynomial-time online algorithm for the node-weighted Steiner forest problem with a poly-logarithmic competitive ratio. The competitive ratio of our algorithm is optimal up to a logarithmic factor. For the special case of graphs with an excluded fixed minor (e.g., planar graphs), we obtain a logarithmic competitive ratio, which is optimal up to a constant, using a different online algorithm. Both these results are obtained as special cases of generic results for a large class of problems that can be encoded as online 0, 1-proper functions. Our results are obtained by using a new framework for online network design problems that we call disk paintings. The central idea in this technique is to amortize the cost of primal updates to a set of carefully selected mutually disjoint fixed-radius dual disks centered at a subset of terminals. We hope that this framework will be useful for other online network design problems.

The emergence of new capabilities such as virtualization and elastic (private or public) cloud computing infrastructures has made it possible to deploy multiple applications, on demand, on the same cloud infrastructure. A major challenge to achieve this possibility, however, is that modern applications are typically distributed, structured systems that include not only computational and storage entities, but also policy entities (e.g., load balancers, firewalls, intrusion prevention boxes). Deploying applications on a cloud infrastructure without the policy entities may introduce substantial policy violations and/or security holes. In this paper, we present PACE: the first systematic framework for Policy-Aware Application Cloud Embedding. We precisely define the policy-aware, cloud application embedding problem, study its complexity and introduce simple, efficient, online primal-dual algorithms to embed applications in cloud data centers. We conduct evaluations using data from a real, large campus network and a realistic data center topology to evaluate the feasibility and performance of PACE. We show that deployment in a cloud without considering in-network policies may lead to a large number of policy violations (e.g., using tree routing as a way to enforce in-network policies may observe up to 91% policy violations). We also show that our embedding algorithms are very efficient by comparing with a good online fractional embedding algorithm.

We study the problem of online prophet-inequality matching in bipartite graphs. There is a static set of bidders and an online stream of items. We represent the interest of bidders in items by a weighted bipartite graph. Each bidder has a capacity, i.e., an upper bound on the number of items that can be allocated to her. The weight of a matching is the total weight of edges matched to the bidders. Upon the arrival of an item, the online algorithm should either allocate it to a bidder or discard it. The objective is to maximize the weight of the resulting matching. We consider this model in a stochastic setting where we know the distribution of the incoming items in advance. Furthermore, we allow the items to be drawn from different distributions, i.e., we may assume that the tth item is drawn from distribution Dt. In contrast to i.i.d. model, this allows us to model the change in the distribution of items throughout the time. We call this setting the Prophet-Inequality Matching because of the possibility of having a different distribution for each time. We generalize the classic prophet inequality by presenting an algorithm with the approximation ratio of 1--1/√k+3 where k is the minimum capacity. In case of k=2, the algorithm gives a tight ratio of 1/2 which is a different proof of the prophet inequality.

Coalition formation is a key topic in multi-agent systems. Coalitions enable agents to achieve goals that they may nothave been able to achieve on their own. Previous work hasshown problems in coalition games to be computationally hard. Wooldridge and Dunne (Artifi. Intell. 2006) studied the classical computational complexity of several natural decision problems in Coalitional Resource Games (CRG) - games in which each agent is endowed with a set of resources and coalitions can bring about a set of goals if they are collectively endowed with the necessary amount of resources. The input of coalitional resource games bundles together several elements, e.g., the agent set Ag, the goal set G, the resource set R, etc. Shrot et al. (AAMAS 2009) examine coalition formation problems in the CRG model using the theory of Parameterized Complexity. Their refined analysis shows that not all parts of input act equal - some instances of the problem are indeed tractable while others still remain intractable.We answer an important question left open by Shrot, Aumann,and Kraus by showing that the SC Problem (checking whether a Coalition is Successful) is W[1]-hard when parameterized by the size of the coalition. Then via a single theme of reduction from SC, we are able to show that various problems related to resources, resource bounds, and resource conflicts introduced by Wooldridge et al. are (i) W[1]-hard or co-W[1]-hard w.r.t the size of the coalition; and (ii) Para-NP hard or co-Para-NP-hard w.r.t |R|. When parameterized by |G| or |R| + |Ag|, we give a general algorithm which proves that these problems are indeed tractable.

We study a very natural local protocol for a file transfer problem. Consider a scenario where several files, which may have varied sizes and get created over a period of time, are to be transferred between pairs of hosts in a distributed environment. Our protocol assumes that while executing the file transfers, an individual host does not use any global knowledge; and simply subdivides its I/O resources equally among all the active file transfers at that host at any point in time. This protocol is motivated by its simplicity of use and its applications to scheduling map-reduce workloads.