A retailer is purchasing goods in bundles from suppliers and then selling these goods in bundles to customers; her goal is to maximize profit, which is the revenue obtained from selling goods minus the cost of purchasing those goods. In this paper, we study this general trading problem from the retailer's perspective, where both suppliers and customers arrive online. The retailer has inventory constraints on the number of goods from each type that she can store, and she must decide upon arrival of each supplier/customer which goods to buy/sell in order to maximize profit. We design an algorithm with logarithmic competitive ratio compared to an optimal offline solution. We achieve this via an exponential-weight-update dynamic pricing scheme, and our analysis dual fits the retailer's profit with respect to a linear programming formulation upper bounding the optimal offline profit. We prove (almost) matching lower bounds, and we also extend our result to an incentive compatible mechanism. Prior to our work, algorithms for trading bundles were known only for the special case of selling an initial inventory.

Abstract In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some adversarial parties try to bias the output. In this work, we focus on the case of an arbitrary number of corrupted parties. Cleve [20] [STOC 1986] has shown that in any such m -round coin-flipping protocol, the corrupted parties can bias the honest parties’ common output bit by $$\Theta (1/m)$$ Θ ( 1 / m ) . For more than two decades, however, the best-known coin-flipping protocol was the one of Awerbuch, Blum, Chor, Goldwasser, and Micali [10] [Manuscript 1985], who presented a t -party, m -round protocol with bias $$\Theta (t/\sqrt{m})$$ Θ ( t / m ) . This was changed by the breakthrough result of Moran, Naor, and Segev [51] [Journal of Cryptology 2016], who constructed an m -round, two -party coin-flipping protocol with optimal bias $$\Theta (1/m)$$ Θ ( 1 / m ) . More recently, Haitner and Tsfadia [37] [SIAM Journal on Computing 2017] constructed an m -round, three -party coin-flipping protocol with bias $$O(\log ^3m / m)$$ O ( log 3 m / m ) . Still for the case of more than three parties, the best-known protocol remained the $$\Theta (t/\sqrt{m})$$ Θ ( t / m ) -bias protocol of [10]. We make a step toward eliminating the above gap, presenting a t -party, m -round coin-flipping protocol, with bias $$O\left( \frac{t^4 \cdot 2^t \cdot \sqrt{\log m}}{m^{1/2+1/(2^{t-1}-2)}}\right) $$ O t 4 · 2 t · log m m 1 / 2 + 1 / ( 2 t - 1 - 2 ) for any $$t\le \tfrac{1}{2} \cdot \operatorname {loglog}m$$ t ≤ 1 2 · loglog m . This improves upon the

In fully-dynamic consistent clustering, we are given a finite metric space $(M,d)$, and a set $F\subseteq M$ of possible locations for opening centers. Data points arrive and depart, and the goal is to maintain an approximately optimal clustering solution at all times while minimizing the recourse, the total number of additions/deletions of centers over time. Specifically, we study fully dynamic versions of the classical $k$-center, facility location, and $k$-median problems. We design algorithms that, given a parameter $\beta\geq 1$, maintain an $O(\beta)$-approximate solution at all times, and whose total recourse is bounded by $O(\log |F| \log \Delta) \cdot OPT_{rec}^{\beta}$. Here $OPT_{rec}^{\beta}$ is the minimal recourse of an offline algorithm that maintains a $\beta$-approximate solution at all times, and $\Delta$ is the metric aspect ratio. We obtain our results via a reduction to the recently proposed Positive Body Chasing framework of [Bhattacharya Buchbinder Levin Saranurak, FOCS 2023], which we show gives fractional solutions to our clustering problems online. Our contribution is to round these fractional solutions while preserving the approximation and recourse guarantees. We complement our positive results with logarithmic lower bounds which show that our bounds are nearly tight.

We study the classic fully dynamic load balancing problem on unrelated machines where jobs arrive and depart over time and the goal is minimizing the maximum load, or more generally the ℓp-norm of the load vector. Previous work either studied the clairvoyant setting in which exact durations are known to the algorithm, or the unknown duration setting in which no information on the duration is given to the algorithm. For the clairvoyant setting algorithms with polylogarithmic competitive ratios were designed, while for the unknown duration setting strong lower bounds exist and only polynomial competitive factors are possible.

We study the problem of maximizing a monotone submodular function subject to a matroid constraint, and present for it a deterministic non-oblivious local search algorithm that has an approximation guarantee of$1-1/e-\epsilon$(for any$\epsilon > 0$) and query complexity of$\tilde{O}_{\epsilon}(nr)$, where$n$is the size of the ground set and$r$is the rank of the matroid. Our algorithm vastly improves over the previous state-of-the-art 0.5008-approximation deterministic algorithm, and in fact, shows that there is no separation between the approximation guarantees that can be obtained by deterministic and randomized algorithms for the problem considered. The query complexity of our algorithm can be improved to$\tilde{O}_{\epsilon}(n+\hat{r}\sqrt{{n}})$using randomization, which is nearly-linear for$r=O(\sqrt{n})$, and is always at least as good as the previous state-of-the-art algorithms.

Maintaining a maximum bipartite matching online while minimizing augmentations is a well studied problem, motivated by content delivery, job scheduling, and hashing. A breakthrough result of Bernstein, Holm, and Rotenberg (SODA 2018) resolved this problem up to a logarithmic factors. However, to model other problems in scheduling and resource allocation, we may need a richer class of combinatorial constraints (e.g., matroid constraints).

Submodular maximization under various constraints is a fundamental problem studied continuously, in both computer science and operations research, since the late 1970’s. A central technique in this field is to approximately optimize the multilinear extension of the submodular objective, and then round the solution. The use of this technique requires a solver able to approximately maximize multilinear extensions. Following a long line of work, Buchbinder and Feldman (2019) described such a solver guaranteeing 0.385-approximation for down-closed constraints, while Oveis Gharan and Vondrák (2011) showed that no solver can guarantee better than 0.478-approximation. In this paper, we present a solver guaranteeing 0.401-approximation, which significantly reduces the gap between the best known solver and the inapproximability result. The design and analysis of our solver are based on a novel bound that we prove for DR-submodular functions. This bound improves over a previous bound due to Feldman et al. (2011) that is used by essentially all state-of-the-art results for constrained maximization of general submodular/DR-submodular functions. Hence, we believe that our new bound is likely to find many additional applications in related problems, and to be a key component for further improvement.

We study the problem of chasing positive bodies in $\ell_{1}$: given a sequence of bodies $K_{t}=\left\{x^{t} \in \mathbb{R}_{+}^{n} \mid C^{t} x^{t} \geq 1, P^{t} x^{t} \leq 1\right\}$ revealed online, where $C^{t}$ and $P^{t}$ are nonnegative matrices, the goal is to (approximately) maintain a point $x_{t} \in K_{t}$ such that $\sum_{t}\left\|x_{t}-x_{t-1}\right\|_{1}$ is minimized. This captures the fully-dynamic low-recourse variant of any problem that can be expressed as a mixed packing-covering linear program and thus also the fractional version of many central problems in dynamic algorithms such as set cover, load balancing, hyperedge orientation, minimum spanning tree, and matching.We give an $O(\log d)$-competitive algorithm for this problem, where d is the maximum row sparsity of any matrix $C^{t}$. This bypasses and improves exponentially over the lower bound of $\sqrt{n}$ known for general convex bodies. Our algorithm is based on iterated information projections, and, in contrast to general convex body chasing algorithms, is entirely memoryless.We also show how to round our solution dynamically to obtain the first fully dynamic algorithms with competitive recourse for all the stated problems above; i.e. their recourse is less than the recourse of every other algorithm on every update sequence, up to polylogarithmic factors. This is a significantly stronger notion than the notion of absolute recourse in the dynamic algorithms literature.

For numerous online bipartite matching problems, such as edge-weighted matching and matching under two-sided vertex arrivals, the state-of-the-art fractional algorithms outperform their randomized integral counterparts. This gap is surprising, given that the bipartite fractional matching polytope is integral, and so lossless rounding is possible. This gap was explained by Devanur et al. (SODA'13), who showed that online lossless rounding is impossible. Despite the above, we initiate the study of lossless online rounding for online bipartite matching problems. Our key observation is that while lossless online rounding is impossible in general, randomized algorithms induce fractional algorithms of the same competitive ratio which by definition are losslessly roundable online. This motivates the addition of constraints that decrease the “online integrality gap”, thus allowing for lossless online rounding. We characterize a set of non-convex constraints which allow for such lossless online rounding, and better competitive ratios than yielded by deterministic algorithms. As applications of our lossless online rounding approach, we obtain two results of independent interest: (i) a doubly-exponential improvement, and a sharp threshold for the amount of randomness (or advice) needed to outperform deterministic online (vertex-weighted) bipartite matching algorithms, and (ii) an optimal semi-OCS, matching a recent result of Gao et al. (FOCS'21) answering a question of Fahrbach et al. (FOCS'20).

Abstract. We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves [Formula: see text]-approximation for the problem (for some [Formula: see text]). This algorithm is the first deterministic algorithm known to improve over the [Formula: see text]-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsey, and Fisher in 1978.

We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which we call T-MSS, an algorithm maintains a point in a metric space and has to serve a sequence of requests. Each request is a map (transformation) $f_t\colon A_t\to B_t$ between subsets $A_t$ and $B_t$ of the metric space. To serve it, the algorithm has to go to a point $a_t\in A_t$, paying the distance from its previous position. Then, the transformation is applied, modifying the algorithm's state to $f_t(a_t)$. Such transformations can model, e.g., changes to the environment that are outside of an algorithm's control, and we therefore do not charge any additional cost to the algorithm when the transformation is applied. The transformations also allow to model requests occurring in the $k$-taxi problem. We show that for $α$-Lipschitz transformations, the competitive ratio is $Θ(α)^{n-2}$ on $n$-point metrics. Here, the upper bound is achieved by a deterministic algorithm and the lower bound holds even for randomized algorithms. For the $k$-taxi problem, we prove a competitive ratio of $\tilde O((n\log k)^2)$. For chasing convex bodies, we show that even with contracting transformations no competitive algorithm exists. The problem T-MSS has a striking connection to the following deep mathematical question: Given a finite metric space $M$, what is the required cardinality of an extension $\hat M\supseteq M$ where each partial isometry on $M$ extends to an automorphism? We give partial answers for special cases.

We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (½ + ε)-approximation for the problem. This algorithm is the first deterministic algorithm known to improve over the ½-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsely and Fisher in 1978.

We consider the k-server problem on trees and HSTs. We give an algorithm based on Bregman projections. This algorithm has a competitive ratios that match some of the recent results given by Bubeck et al. (STOC 2018), whose algorithm was based on mirror-descent-based continuous dynamics prescribed via a differential inclusion.

Submodular function maximization has been studied extensively in recent years under various constraints and models. The problem plays a major role in various disciplines. We study a natural online variant of this problem in which elements arrive one by one and the algorithm has to maintain a solution obeying certain constraints at all times. Upon arrival of an element, the algorithm has to decide whether to accept the element into its solution and may preempt previously chosen elements. The goal is to maximize a submodular function over the set of elements in the solution. We study two special cases of this general problem and derive upper and lower bounds on the competitive ratio. Specifically, we design a 1/ e -competitive algorithm for the unconstrained case in which the algorithm may hold any subset of the elements, and constant competitive ratio algorithms for the case where the algorithm may hold at most k elements in its solution.

The \sf Multiway-Cut problem is a fundamental graph partitioning problem in which the objective is to find a minimum weight set of edges disconnecting a given set of special vertices called terminals. This problem is NP-hard and there is a well-known geometric relaxation in which the graph is embedded into a high dimensional simplex. Rounding a solution to the geometric relaxation is equivalent to partitioning the simplex. We present a novel simplex partitioning algorithm which is based on two ingredients: competing exponential clocks and distortion. Unlike previous methods, it utilizes cuts that are not parallel to the faces of the simplex. Applying this partitioning algorithm to the multiway cut problem, we obtain a simple (4/3)-approximation algorithm, thus, improving upon the current best-known result. This bound is further pushed to obtain an approximation factor of 1.32388. It is known that under the assumption of the unique games conjecture, the best possible approximation for the \sf Multiway-Cut problem can be attained via the geometric relaxation.

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios. In this work, we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing a submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic 1/2-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.

In the adversarial edge arrival model for maximum cardinality matching, edges of an unknown graph are revealed one-by-one in arbitrary order, and should be irrevocably accepted or rejected. Here, the goal of an online algorithm is to maximize the number of accepted edges while maintaining a feasible matching at any point in time. For this model, the standard greedy heuristic is 1/2-competitive, and on the other hand, no algorithm that outperforms this ratio is currently known, even for very simple graphs. We present a clean Min-Index framework for devising a family of randomized algorithms, and provide a number of positive and negative results in this context. Among these results, we present a 5/9-competitive algorithm when the underlying graph is a forest, and prove that this ratio is best possible within the Min-Index framework. In addition, we prove a new general upper bound of 2/(3+1/phi^2) ~ 0.5914 on the competitiveness of any algorithm in the edge arrival model. Interestingly, this bound holds even for an easier model in which vertices (along with their adjacent edges) arrive online, and when the underlying graph is a tree of maximum degree at most 3.

We consider two generalizations of the classical weighted paging problem that incorporate the notion of delayed service of page requests. The first is the (weighted) paging with time windows (\sf PageTW) problem, which is like the classical weighted paging problem except that each page request only needs to be served before a given deadline. This problem arises in many practical applications of online caching, such as the “deadline” I/O scheduler in the Linux kernel and video-on-demand streaming. The second, and more general, problem is the (weighted) paging with delay (\sf PageD) problem, where the delay in serving a page request results in a penalty being added to the objective. This problem generalizes the caching problem to allow delayed service, a line of work that has recently gained traction in online algorithms (e.g., [Y. Emek, S. Kutten, and R. Wattenhofer, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016, pp. 333--344; Y. Azar et al., Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 551--563; Y. Azar and N. Touitou, Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019, pp. 60--71]). We give $O(\log k\log n)$-competitive algorithms for both the \sf PageTW and \sf PageD problems on $n$ pages with a cache of size $k$. This significantly improves on the previous best bounds of $O(k)$ for both problems [Y. Azar et al., Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 551--563]. We also consider the offline \sf PageTW and \sf PageD problems, for which we give $O(1)$-approximation algorithms and prove APX-hardness. These are the first results for the offline problems; even NP-hardness was not known before our work. At the heart of our algorithms is a novel “hitting-set” LP relaxation of the \sf PageTW problem that overcomes the $\Omega(k)$ integrality gap of the natural LP for the problem. To the best of our knowledge, this is the first example of an LP-based algorithm for an online problem with delays/deadlines.

In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. In this work we focus on the case of dishonest majority, ie at least half of the parties can be corrupted. [19] [STOC 1986] has shown that in any m-round coin-flipping protocol the corrupted parties can bias the honest parties’ common output bit by Θ(1/m). For more than two decades the best known coin-flipping protocols against majority was the protocol of [9] [Manuscript 1985], who presented a t-party, m-round protocol with bias This was changed by the breakthrough result of [42] [TCC 2009], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(1/m). Recently, [32] [STOC 14] constructed an m-round, three-party coin-flipping protocol with bias O(log3 m/m). Still for the case of more than three parties, against arbitrary number of corruptions, the best known protocol remained the protocol of [9]. We make a step towards eliminating the above gap, presenting a t-party, m-round coin-flipping protocol, with bias This improves upon the protocol of [9] for any t ≤ 1/2 · log log m, and in particular for t ∊ O(1), this yields an protocol. For the three-party case, this yields an protocol, improving over the the O(log3 m/m)-bias protocol of [32]. Our protocol generalizes that of [32], by presenting an appropriate “defense protocols” for the remaining parties to interact in, in the case that some parties abort or caught cheating ([32] only presented a two-party defense protocol, which limits their final protocol to handle three parties). We analyze our new protocols by presenting a new paradigm for analyzing fairness of coin-flipping protocols. We map the set of adversarial strategies that try to bias the honest parties outcome in the protocol to the set of the feasible solutions of a linear program. The gain each strategy achieves is the value of the corresponding solution. We then bound the the optimal value of the linear program by constructing a feasible solution to its dual.

We consider Multiway Cut, a basic graph partitioning problem in which the goal is to find the minimum weight collection of edges disconnecting a given set of special vertices called terminals. Multiway Cut admits a well known simplex embedding relaxation, where rounding this embedding is equivalent to partitioning the simplex. Current best known solutions to the problem are comprised of a mix of several different ingredients, resulting in intricate algorithms. Moreover, the best of these algorithms is too complex to fully analyze analytically and its approximation factor was verified using a computer. We propose a new approach to simplex partitioning and the Multiway Cut problem based on general transformations of the simplex that allow dependencies between the different variables. Our approach admits much simpler algorithms, and in addition yields an approximation guarantee for the Multiway Cut problem that (roughly) matches the current best computer verified approximation factor.

We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: minxϵR+nf(x) s.t. Ax ≥ 1, where f:R+n→ R+is a monotone convex function, and A is an m×n matrix with non-negative entries. In the online version, a new row of the constraint matrix, representing a new covering constraint, is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment x over time. We also consider a convex packing problem defined as: maxyϵR+mΣj=1myj - g(ATy), where g:R+n→R+is a monotone convex function. In the online version, each variable yj arrives online and the algorithm must decide the value of yj on its arrival. This represents the Fenchel dual of the convex covering program, when g is the convex conjugate of f. We use a primal-dual approach to give online algorithms for these generic problems, and use them to simplify, unify, and improve upon previous results for several applications.

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios. In this work we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic 1/2-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.

Fast algorithms for submodular maximization problems have a vast potential use in applicative settings, such as machine learning, social networks, and economics. Though fast algorithms were known for some special cases, only recently Badanidiyuru and Vondrák [4] were the first to explicitly look for such algorithms in the general case of maximizing a monotone submodular function subject to a matroid independence constraint. The algorithm of Badanidiyuru and Vondrák matches the best possible approximation guarantee, while trying to reduce the number of value oracle queries the algorithm performs. Our main result is a new algorithm for this general case which establishes a surprising tradeoff between two seemingly unrelated quantities: the number of value oracle queries and the number of matroid independence queries performed by the algorithm. Specifically, one can decrease the former by increasing the latter and vice versa, while maintaining the best possible approximation guarantee. Such a tradeoff is very useful since various applications might incur significantly different costs in querying the value and matroid independence oracles. Furthermore, in case the rank of the matroid is O(nc), where n is the size of the ground set and c is an absolute constant smaller than 1, the total number of oracle queries our algorithm uses can be made to have a smaller magnitude compared to that needed by [4]. We also provide even faster algorithms for the well studied special cases of a cardinality constraint and a partition matroid independence constraint, both of which capture many real-world applications and have been widely studied both theorically and in practice.

Submodular function maximization has been studied extensively in recent years under various constraints and models. The problem plays a major role in various disciplines. We study a natural online variant of this problem in which elements arrive one-by-one and the algorithm has to maintain a solution obeying certain constraints at all times. Upon arrival of an element, the algorithm has to decide whether to accept the element into its solution and may preempt previously chosen elements. The goal is to maximize a submodular function over the set of elements in the solution. We study two special cases of this general problem and derive upper and lower bounds on the competitive ratio. Specifically, we design a 1/e-competitive algorithm for the unconstrained case in which the algorithm may hold any subset of the elements, and constant competitive ratio algorithms for the case where the algorithm may hold at most k elements in its solution.

We give the first polylogarithmic-competitive randomized online algorithm for the k -server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of Õ(log 3 n log 2 k ) for any metric space on n points. Our algorithm improves upon the deterministic (2 k -1)-competitive algorithm of Koutsoupias and Papadimitriou [Koutsoupias and Papadimitriou 1995] for a wide range of n .

We consider the \sf Unconstrained Submodular Maximization problem in which we are given a nonnegative submodular function $f:2^{\mathcal{N}}\rightarrow \mathbb{R}^+$, and the objective is to find a subset $S\subseteq \mathcal{N}$ maximizing $f(S)$. This is one of the most basic submodular optimization problems, having a wide range of applications. Some well-known problems captured by \sf Unconstrained Submodular Maximization include \sf Max-Cut, \sf Max-DiCut, and variants of \sf Max-SAT and maximum facility location. We present a simple randomized linear time algorithm achieving a tight approximation guarantee of 1/2, thus matching the known hardness result of Feige, Mirrokni, and Vondrák [SIAM J. Comput., 40 (2011), pp. 1133--1153]. Our algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem.

We provide a framework for designing competitive online algorithms using regularization, a widely used technique in online learning, particularly in online convex optimization. An online algorithm that uses regularization serves requests by computing a solution, in each step, to an objective function involving a smooth convex regularization function. Applying the technique of regularization allows us to obtain new results in the domain of competitive analysis. We remark that competitive analysis and online learning are two widely studied frameworks for online decision-making settings. We show that even though there are significant differences in assumptions, goals, and techniques between the two fields, one can still benefit by introducing techniques from one field to the other. In our new framework we exhibit a general O(log m)-competitive deterministic algorithm for generating a fractional solution that satisfies a time-varying set of online covering and precedence constraints, where m is the number of variables. This framework allows to incorporate both service costs (over time) and setup costs into a host of applications. We then provide an O(log m log n)-competitive randomized algorithm for the online set cover problem with service cost, where m is the number of sets and n is the number of elements. This model allows for sets to be both added and deleted over time from a solution.

We consider the problem of maximizing a (non-monotone) submodular function subject to a cardinality constraint. In addition to capturing well-known combinatorial optimization problems, e.g., Max-k-Coverage and Max-Bisection, this problem has applications in other more practical settings such as natural language processing, information retrieval, and machine learning. In this work we present improved approximations for two variants of the cardinality constraint for non-monotone functions. When at most k elements can be chosen, we improve the current best approximation to a factor that is in the range [ ], achieving a tight approximation of for and breaking the barrier for all values of k. When exactly k elements must be chosen, our algorithms improve the current best approximation to a factor that is in the range [0.356, ], again achieving a tight approximation of for . Additionally, some of the algorithms we provide are very fast with time complexities of O(nk), as opposed to previous known algorithms which are continuous in nature, and thus, too slow for applications in the practical settings mentioned above. Our algorithms are based on two new techniques. First, we present a simple randomized greedy approach where in each step a random element is chosen from a set of “reasonably good” elements. This approach might be considered a natural substitute for the greedy algorithm of Nemhauser, Wolsey and Fisher [45], as it retains the same tight guarantee of for monotone objectives and the same time complexity of O(nk), while giving an approximation of for general non-monotone objectives (while the greedy algorithm of Nemhauser et. al. fails to provide any constant guarantee). Second, we extend the double greedy technique, which achieves a tight approximation for unconstrained submodular maximization, to the continuous setting. This allows us to manipulate the natural rates by which elements change, thus bounding the total number of elements chosen.

The Multiway-Cut problem is a fundamental graph partitioning problem in which the objective is to find a minimum weight set of edges disconnecting a given set of special vertices called terminals. This problem is NP-hard and there is a well known geometric relaxation in which the graph is embedded into a high dimensional simplex. Rounding a solution to the geometric relaxation is equivalent to partitioning the simplex. We present a novel simplex partitioning algorithm which is based on em competing exponential clocks and distortion. Unlike previous methods, it utilizes cuts that are not parallel to the faces of the simplex. Applying this partitioning algorithm to the multiway cut problem, we obtain a simple (4/3)-approximation algorithm, thus, improving upon the current best known result. This bound is further pushed to obtain an approximation factor of 1.32388. It is known that under the assumption of the unique games conjecture, the best possible approximation for the Multiway-Cut problem can be attained via the geometric relaxation.

We consider the Unconstrained Submodular Maximization problem in which we are given a non-negative submodular function f : 2N→ ℝ+, and the objective is to find a subset S ⊆ N maximizing f(S). This is one of the most basic submodular optimization problems, having a wide range of applications. Some well known problems captured by Unconstrained Submodular Maximization include MaxCut, Max-DiCut, and variants of Max-SAT and maximum facility location. We present a simple randomized linear time algorithm achieving a tight approximation guarantee of 1/2, thus matching the known hardness result of Feige et al. [11]. Our algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem. Our method might seem counterintuitive, since it is known that the greedy algorithm fails to achieve any bounded approximation factor for the problem.

We study the weighted version of the classic online paging problem where there is a weight (cost) for fetching each page into the cache. We design a randomized O (log k )-competitive online algorithm for this problem, where k is the cache size. This is the first randomized o ( k )-competitive algorithm and its competitive ratio matches the known lower bound for the problem, up to constant factors. More generally, we design an O (log( k /( k − h + 1)))-competitive online algorithm for the version of the problem where the online algorithm has cache size k and it is compared to an optimal offline solution with cache size h ≤ k . Our solution is based on a two-step approach. We first obtain an O (log k )-competitive fractional algorithm based on an online primal-dual approach. Next, we obtain a randomized algorithm by rounding in an online manner the fractional solution to a probability distribution on the possible cache states. We also give an online primal-dual randomized O (log N )-competitive algorithm for the Metrical Task System problem (MTS) on a weighted star metric on N leaves.

We consider online algorithms for the generalized caching problem. Here we are given a cache of size k 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 $O(\log^2k)$, which gives the first $o(k)$ competitive algorithm for the problem. We also give improved $O(\log k)$-competitive algorithms for the special cases of the bit model and fault model, improving upon the previous $O(\log^2k)$ 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 $O(\log k)$-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.

A major problem in wireless networks is coping with limited resources, such as bandwidth and energy. These issues become a major algorithmic challenge in view of the dynamic nature of the wireless domain. We consider in this paper the single-transmitter power assignment problem under time-varying channels, with the objective of maximizing the data throughput. It is assumed that the transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, which leads to explicit “water-filling” solutions, by considering a realistic scenario where the channel state quality changes arbitrarily from one transmission to the other. The problem is accordingly tackled within the framework of competitive analysis, which allows for worst-case performance guarantees in setups with arbitrarily varying channel conditions. We address both a “discrete” case, where the transmitter can transmit only at a fixed power level, and a “continuous” case, where the transmitter can choose any power level out of a bounded interval. For both cases, we propose online power-allocation algorithms with proven worst-case performance bounds. In addition, we establish lower bounds on the worst-case performance of any online algorithm and show that our proposed algorithms are optimal.

We give the first polylogarithmic-competitive randomized algorithm for the k-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of Õ(log3n log2k) for any metric space on n points. This improves upon the (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou (J. ACM 1995) whenever n is sub-exponential in k.

We consider the power control problem in a time-slotted wireless channel, shared by a finite number of mobiles that transmit to a common base station. The channel between each mobile and the base station is time varying, and the system objective is to maximize the overall data throughput. It is assumed that each transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, by considering a realistic scenario where the channel quality of each mobile changes arbitrarily from one transmission to the other. Assuming first that each mobile is aware of the channel quality of all other mobiles, we propose an online power-allocation algorithm, and prove its optimality under mild assumptions. We then indicate how to implement the algorithm when only local state information is available, requiring minimal communication overhead. Notably, the competitive ratio of our algorithm (nearly) matches the one we previously obtained for the (much simpler) single-transmitter case [BLMNO09], albeit requiring significantly different algorithmic solutions.

Recently, Coté et al. [10] proposed an approach for solving the k-server problem on Hierchically Separated Trees (HSTs). In particular, they define a problem on a uniform metric, and show that if an algorithm with a certain refined guarantee exists for it, then one can obtain polylogarithmic (in diameter) competitive factors for the k-server problem on HSTs by solving this problem recursively. By designing such an algorithm for a two point metric, they obtained a logarithmic competitive algorithm for well-separated binary HSTs. Extending their result to uniform metrics on arbitrarily many points would imply a poly-logarithmic competitive algorithm for k-server on general HSTs (and hence general metrics) and is thus of major interest. Here, we design such an algorithm for any uniform metric, provided the instance satisfies a certain “convexity” property. Even though this does not give a result for k-server, convexity seems to be a very natural property, and we give evidence that instances arising in the Coté et al. [10] reduction from k-server essentially possess this property, suggesting that this might be a promising approach. Already, our setting is general enough to model the finely competitive paging problem proposed by Blum et al. [4], who motivated it as a first step towards achieving a polylog(k) competitive algorithm for k-server. Our result implies an r + O(log k)-competitive algorithm for finely competitive paging, resolving the main open problem of [4]. Our results are based on an extension of the primal-dual framework for online algorithms developed by Buchbinder and Naor [7]. The original approach works for problems whose offline version can be expressed as a packing or a covering linear program, possibly with box constraints. The online nature of the problem is modeled by revealing the constraints one by one and the requirement that variables can only be increased over time. Here, we consider more general types of constraints, where terms can be both positive and negative. Moreover, we allow the variables to both increase and decrease. This versatility allows us to model problems such as predicting with expert advice, which could not be modeled earlier. To show the simplicity and generality of this approach, we give an alternate O(log k)-competitive algorithm for weighted paging with a very simple proof. We also give an alternate primal-dual approach to design regret minimization algorithms for the problem of online prediction with expert advice. Our results suggest the possibility of a more general primal-dual framework for online problems beyond covering and packing LPs.

A major problem in wireless networks is coping with limited resources, such as bandwidth and energy. These issues become a major algorithmic challenge in view of the dynamic nature of the wireless domain. We consider in this paper the single-transmitter power assignment problem under time-varying channels, with the objective of maximizing the data throughput. It is assumed that the transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, which leads to explicit "water-filling" solutions, by considering a realistic scenario where the channel state quality changes arbitrarily from one transmission to the other. The problem is accordingly tackled within the framework of competitive analysis, which allows for worst case performance guarantees in setups with arbitrarily varying channel conditions. We address both a "discrete" case, where the transmitter can transmit only at a fixed power level, and a "continuous" case, where the transmitter can choose any power level out of a bounded interval. For both cases, we propose online power-allocation algorithms with proven worst-case performance bounds. In addition, we establish lower bounds on the worst-case performance of any online algorithm, and show that our proposed algorithms are optimal.

Let $X=\{1,2,\ldots,n\}$ be a ground set of n elements, and let ${\cal S}$ be a family of subsets of X, $|{\cal S}|=m$, with a positive cost $c_S$ associated with each $S\in{\cal S}$. 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 X one by one. Once a new element is given, the algorithm has to cover it by some set of ${\cal S}$ containing it. We assume that the elements of X and the members of ${\cal S}$ are known in advance to the algorithm; however, the set $X'\subseteq X$ of elements given by the adversary is not known in advance to the algorithm. (In general, $X'$ may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let ${\cal C}$ denote the family of sets in ${\cal S}$ that the algorithm chooses. At the end of the game the adversary also produces (offline) a family of sets ${\cal C}_{OPT}$ that covers $X'$. The performance of the algorithm is the ratio between the cost of ${\cal C}$ and the cost of ${\cal C}_{OPT}$. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. We present an $O(\log m\log n)$ competitive deterministic algorithm for the problem and establish a nearly matching $\Omega\bigl(\frac{\log n\log m}{\log\log m+\log\log n}\bigr)$ lower bound for all interesting values of m and n. 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 k 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. We give an online algorithm with competitive ratio O(log2k), which is the first algorithm for the problem with competitive ratio sublinear in k. We also give improved O(log k)-competitive algorithms for the special cases of the Bit Model and Fault model. In the Bit Model, the fetching cost is proportional to the size of the page and in the Fault model all fetching costs are uniform. Previously, an O(log2 k)-competitive algorithm due to Irani [14] was known for both of these models. Our algorithms are based on an extension of the primal-dual framework for online algorithms which was developed by Buchbinder and Naor [7]. We first generate an O(log k)-competitive fractional algorithm for the problem. This is done by using a strengthened LP formulation with knapsack-cover constraints, where exponentially many constraints are added upon arrival of a new request. Second, we round online the fractional solution and obtain a randomized online algorithm. Our techniques provide a unified framework for caching algorithms and are substantially simpler than those previously used.

In the weighted paging problem there is a weight (cost) for fetching each page into the cache. We design a randomized O(log k) -competitive online algorithm for the weighted paging problem, where k is the cache size. This is the first randomized o(k)-competitive algorithm and its competitiveness matches the known lower bound on the problem. More generally, we design an O(log(k/(k - h + I)))-competitive online algorithm for the version of the. problem where, the online algorithm has-cache size k and the online algorithm has cache size h les k. Weighted paging is a special case (weighted star metric) of the well known k-server problem for which it is a major open question whether randomization can be useful in obtaining sub-linear competitive algorithms. Therefore, abstracting and extending the insights from paging is a key step in the resolution of the k-server problem. Our solution for the weighted paging problem is based on a two-step approach. In the first step we obtain an O(log k)-competitive fractional algorithm which is based on a novel online primal-dual approach. In the second step we. obtain a randomized algorithm by rounding online the fractional solution to an actual distribution on integral cache, solutions. We conclude with a randomized O(log N)-competitive algorithm for the well studied Metrical Task System problem (MTS) on a metric defined by a weighted star on N leaves, improving upon a previous O(log2N)-competitive algorithm of Blum et al. [9].

In this work we study a wide range of online and offline routing and packing problems with various objectives. We provide a unified approach, based on a clean primal-dual method, for the design of online algorithms for these problems, as well as improved bounds on the competitive factor. In particular, our analysis uses weak duality rather than a tailor made (i.e., problem specific) potential function. We demonstrate our ideas and results in the context of routing problems. Using our primal-dual approach, we develop a new generic online routing algorithm that outperforms previous algorithms suggested earlier by Y. Azar et al. (1993, 1997). We then show the applicability of our generic algorithm to various models and provide improved algorithms for achieving coordinate-wise competitiveness, maximizing throughput, and minimizing maximum load. In particular, we improve the results obtained by A. Goel et al. (2001) by an O(log n) factor for the problem of achieving coordinate-wise competitiveness, and by an O(log log n) factor for the problem of maximizing the throughput. For some of the settings we also prove improved lower bounds. We believe our results further our understanding of the applicability of the primal-dual method to online algorithms, and we are confident that the method will prove useful to other online scenarios. Finally, we revisit the notions of coordinate-wise and prefix competitiveness in an offline setting. We design the first polynomial time algorithm that computes an almost optimal coordinate-wise routing for several routing models. We also revisit previously studied routing models by A. Kumar and J.M. Kleinberg (2000) and A. Goel and A. Meyerson (2005) and prove tight lower and upper bounds of Theta(log n) on prefix competitiveness for these models

We revisit from a fairness point of view the problem of online load balancing in the restricted assignment model and the 1-∞ model. We consider both a job-centric and a machine-centric view of fairness, as proposed by Goel et al. [11]. These notions are equivalent to the approximate notion of prefix competitiveness proposed by Kleinberg, Rabani and Tardos [14], as well as to the notion of approximate majorization, and they generalize the well studied notion of max-min fairness.We resolve a question posed by Goel,Meyerson and Plotkin [11] proving that the greedy strategy is globally O(logm)-fair, where m denotes the number of machines. This result improves upon the analysis of [11] who showed that the greedy strategy is globally O(log n)-fair, where n is the number of jobs. Typically, n > m, and therefore our improvement is significant. Our proof matches the known lower bound for the problem with respect to the measure of global fairness.The improved bound is obtained by analyzing, in a more accurate way, the more general restricted assignment model studied previously in [6]. We provide an alternative bound which is not worse than the bounds of [6], and it is strictly better in many cases. The bound we prove is, in fact, much more general and it bounds the load on any prefix of most loaded machines. As a corollary from this more general bound we get that the greedy algorithm results in an assignment that is globally O(logm)-balanced. The last result generalizes the previous result of [11] who proved that the greedy algorithm yields an assignment that is globally O(logm)-balanced for the 1-∞ model.

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 Räcke's new hierarchical decomposition of graphs.Specifically, our results for the integral case include an O (log m log 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 (log 2 n log k )-competitive randomized algorithm for the online group Steiner problem in trees and an O (log 3 n log 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 (log 3 n log log n )-competitive algorithm for the online multi-cut problem.

Let X=[1,2,•••,n] be a ground set of n elements, and let S be a family of subsets of X, |S|=m, with a positive cost cS associated with each S ∈ S.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 X one-by-one. Once a new element is given, the algorithm has to cover it by some set of S containing it. We assume that the elements of X and the members of S are known in advance to the algorithm, however, the set X' ⊆ X of elements given by the adversary is not known in advance to the algorithm. (In general, X' may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let C denote the family of sets in S that the algorithm chooses. At the end of the game the adversary also produces (off-line) a family of sets COPT that covers X'. The performance of the algorithm is the ratio between the cost of C and the cost of COPT. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm.We present an O(log m log n) competitive deterministic algorithm for the problem, and establish a nearly matching Ω(log n log m/log log m + log log n) lower bound for all interesting values of m and n. 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 the fractional solution they supply into a deterministic online algorithm.