We consider fractional online covering problems with @math -norm objectives. The problem of interest is of the form @math where @math is the weighted sum of @math -norms and @math is a non-negative matrix. The rows of @math (i.e. covering constraints) arrive online over time. We provide an online @math -competitive algorithm where @math and @math is the maximum of the row sparsity of @math and @math . This is based on the online primal-dual framework where we use the dual of the above convex program. Our result expands the class of convex objectives that admit good online algorithms: prior results required a monotonicity condition on the objective @math which is not satisfied here. This result is nearly tight even for the linear special case. As direct applications we obtain (i) improved online algorithms for non-uniform buy-at-bulk network design and (ii) the first online algorithm for throughput maximization under @math -norm edge capacities.
The online primal-dual framework for linear programs @cite_8 is fairly well understood. Tight results are known for the class of packing and covering LPs @cite_24 @cite_1 , with competitive ratio @math for covering LPs and @math for packing LPs; here @math is the row-sparsity and @math is the ratio of the maximum to minimum entries in the constraint matrix. Such LPs are very useful because they correspond to the LP relaxations of many combinatorial optimization problems. Combining the online LP solver with suitable online rounding schemes, good online algorithms have been obtained for many problems, eg. set cover @cite_23 , group Steiner tree @cite_12 , caching @cite_2 and ad-auctions @cite_7 . Online algorithms for LPs with mixed packing and covering constraints were obtained in @cite_0 ; the competitive ratio was improved in @cite_21 . Such mixed packing covering LPs were also used to obtain an online algorithm for capacitated facility location @cite_0 . A more complex mixed packing covering LP was used recently in @cite_4 to obtain online algorithms for non-uniform buy-at-bulk network design: as an application of our result, we obtain a simpler and better (by two log-factors) online algorithm for this problem.
@cite_4 @cite_7 @cite_8 @cite_21 @cite_1 @cite_24 @cite_0 @cite_23 @cite_2 @cite_12
1496647032 2142339200 2274097845 2122886291 2074121653 2905904719 1973444128
We study the online ad-auctions problem introduced by [15]. We design a (1 - 1 e)-competitive (optimal) algorithm for the problem, which is based on a clean primal-dual approach, matching the competitive factor obtained in [15]. Our basic algorithm along with its analysis are very simple. Our results are based on a unified approach developed earlier for the design of online algorithms [7,8]. In particular, the analysis uses weak duality rather than a tailor made (i.e., problem specific) potential function. We show that this approach is useful for analyzing other classical online algorithms such as ski rental and the TCP-acknowledgement problem. We are confident that the primal-dual method will prove useful in other online scenarios as well. The primal-dual approach enables us to extend our basic ad-auctions algorithm in a straight forward manner to scenarios in which additional information is available, yielding improved worst case competitive factors. In particular, a scenario in which additional stochastic information is available to the algorithm, a scenario in which the number of interested buyers in each product is bounded by some small number d, and a general risk management framework. The primal—dual method is a powerful algorithmic technique that has proved to be extremely useful for a wide variety of problems in the area of approximation algorithms for NP-hard problems. The method has its origins in the realm of exact algorithms, e.g., for matching and network flow. In the area of approximation algorithms, the primal—dual method has emerged as an important unifying design methodology, starting from the seminal work of Goemans and Williamson [60] We show in this survey how to extend the primal—dual method to the setting of online algorithms, and show its applicability to a wide variety of fundamental problems. Among the online problems that we consider here are the weighted caching problem, generalized caching, the set-cover problem, several graph optimization problems, routing, load balancing, and the problem of allocating ad-auctions. We also show that classic online problems such as the ski rental problem and the dynamic TCP-acknowledgement problem can be solved optimally using a simple primal—dual approach. The primal—dual method has several advantages over existing methods. First, it provides a general recipe for the design and analysis of online algorithms. The linear programming formulation helps detecting the difficulties of the online problem, and the analysis of the competitive ratio is direct, without a potential function appearing "out of nowhere." Finally, since the analysis is done via duality, the competitiveness of the online algorithm is with respect to an optimal fractional solution, which can be advantageous in certain scenarios. A covering integer program (CIP) is a mathematical program of the form min c⊤ x ∣ Ax ≥ 1, 0 ≤ x ≤ u, x ∈ ℤn , where all entries in A, c, u are nonnegative. In the online setting, the constraints (i.e., the rows of the constraint matrix A) arrive over time, and the algorithm can only increase the coordinates of x to maintain feasibility. As an intermediate step, we consider solving the covering linear program (CLP) online, where the integrality constraints are dropped. Our main results are (a) an O(log k)-competitive online algorithm for solving the CLP, and (b) an O(log k · log l)-competitive randomized online algorithm for solving the CIP. Here k ≤ n and l ≤ m respectively denote the maximum number of nonzero entries in any row and column of the constraint matrix A. Our algorithm is based on the online primal-dual paradigm, where a novel ingredient is to allow dual variables to increase and decrease throughout the course of the algorithm. It is known that this result is the best possible for polynomial-t... We study a wide range of online covering and packing optimization problems. In an online covering problem, a linear cost function is known in advance, but the linear constraints that define the feasible solution space are given one by one, in rounds. In an online packing problem, the profit function as well as the packing constraints are not known in advance. In each round additional information (i.e., a new variable) about the profit function and the constraints is revealed. An online algorithm needs to maintain a feasible solution in each round; in addition, the solutions generated over the different rounds need to satisfy a monotonicity property. We provide general deterministic primal-dual algorithms for online fractional covering and packing problems. We also provide deterministic algorithms for several integral online covering and packing problems. Our algorithms are designed via a novel online primal-dual technique and are evaluated via competitive analysis. Let @math be a ground set of @math elements, and let @math be a family of subsets of @math , @math , with a positive cost @math associated with each @math . Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from @math one by one. Once a new element is given, the algorithm has to cover it by some set of @math containing it. We assume that the elements of @math and the members of @math are known in advance to the algorithm; however, the set @math of elements given by the adversary is not known in advance to the algorithm. (In general, @math may be a strict subset of @math .) The objective is to minimize the total cost of the sets chosen by the algorithm. Let @math denote the family of sets in @math that the algorithm chooses. At the end of the game the adversary also produces (offline) a family of sets @math that covers @math . The performance of the algorithm is the ratio between the cost of @math and the cost of @math . The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. We present an @math competitive deterministic algorithm for the problem and establish a nearly matching @math lower bound for all interesting values of @math and @math . The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting a fractional solution into a deterministic online algorithm. We consider online algorithms for the generalized caching problem. Here we are given a cache of size @math and pages with arbitrary sizes and fetching costs. Given a request sequence of pages, the goal is to minimize the total cost of fetching the pages into the cache. Our main result is an online algorithm with competitive ratio @math , which gives the first @math competitive algorithm for the problem. We also give improved @math -competitive algorithms for the special cases of the bit model and fault model, improving upon the previous @math guarantees due to Irani [Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 701-710]. Our algorithms are based on an extension of the online primal-dual framework introduced by Buchbinder and Naor [Math. Oper. Res., 34 (2009), pp. 270-286] and involve two steps. First, we obtain an @math -competitive fractional algorithm based on solving online an LP formulation strengthened with exponentially many knapsack cover constraints. Second, we design a suitable online rounding procedure to convert this online fractional algorithm into a randomized algorithm. Our techniques provide a unified framework for caching algorithms and are substantially simpler than those previously used. We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design problem, we have a communication network known to the algorithm in advance. What is not known in advance are the connectivity (bandwidth) or cut demands between vertices in the network which arrive online.We develop a unified framework for designing online algorithms for problems involving connectivity and cuts. We first present a general O(log m)-competitive deterministic algorithm for generating a fractional solution that satisfies the online connectivity or cut demands, where m is the number of edges in the graph. This may be of independent interest for solving fractional online bandwidth allocation problems, and is applicable to both directed and undirected graphs. We then show how to obtain integral solutions via an online rounding of the fractional solution. This part of the framework is problem dependent, and applies various tools including results on approximate max-flow min-cut for multicommodity flow, the Hierarchically Separated Trees (HST) method and its extensions, certain rounding techniques for dependent variables, and Racke's new hierarchical decomposition of graphs.Specifically, our results for the integral case include an O(log mlog n)-competitive randomized algorithm for the online nonmetric facility location problem and for a generalization of the problem called the multicast problem. In the nonmetric facility location problem, m is the number of facilities and n is the number of clients. The competitive ratio is nearly tight. We also present an O(log2nlog k)-competitive randomized algorithm for the online group Steiner problem in trees and an O(log3nlog k)-competitive randomized algorithm for the problem in general graphs, where n is the number of vertices in the graph and k is the number of groups. Finally, we design a deterministic O(log3nlog log n)-competitive algorithm for the online multi-cut problem.