Sampling from multiple distributions so as to maximize overlap has been studied by statisticians since the 1950s. Since the 2000s, such correlated sampling from the probability simplex has been a powerful building block in disparate areas of theoretical computer science. We study a generalization of this problem to sampling sets from given vectors in the hypersimplex, i.e., outputting sets of size (at most) some $k$ in $[n]$, while maximizing the sampled sets' overlap. Specifically, the expected difference between two output sets should be at most $α$ times their input vectors' $\ell_1$ distance. A value of $α=O(\log n)$ is known to be achievable, due to Chen et al.~(ICALP'17). We improve this factor to $O(\log k)$, independent of the ambient dimension~$n$. Our algorithm satisfies other desirable properties, including (up to a $\log^* n$ factor) input-sparsity sampling time, logarithmic parallel depth and dynamic update time, as well as preservation of submodular objectives. Anticipating broader use of correlated sampling algorithms for the hypersimplex, we present applications of our algorithm to online paging, offline approximation of metric multi-labeling and swift multi-scenario submodular welfare approximating reallocation.

Driven by the massive parallelism of modern multicore architectures and high-bandwidth networks, system throughput has increasingly outpaced physical latency limits. In such high-throughput environments, the ratio Z between retrieval latency and the request inter-arrival time becomes a dominant performance factor. We study the paging with delayed hits problem, a framework that captures these dynamics in systems such as CDNs and MEC. In this model, each page load incurs a delay of Z time steps, during which requests for the same page can be batched and served together, with costs proportional to both request weight and waiting time.

We introduce the abstract problem of rounding an unknown fractional bipartite b-matching x revealed online (e.g., output by an online fractional algorithm), exposed node-by-node on one side. The objective is to maximize the rounding ratio of the output matching 𝓜, which is the minimum over all fractional b-matchings x, and edges e, of the ratio Pr[e ∈ 𝓜]/xe. In analogy with the highly influential offline dependent rounding schemes of Gandhi et al. (FOCS’02, J.ACM’06), we refer to such algorithms as online dependent rounding schemes (ODRSes). This problem, with additional restrictions on the possible inputs x, has played a key role in recent developments in online computing.

Phase-change memory (PCM) is a promising memory technology known for its speed, high density, and durability. However, each PCM cell can endure only a limited number of erase and subsequent write operations before failing, and the failure of a single cell can limit the lifespan of the entire device. This vulnerability makes PCM particularly susceptible to adversarial attacks that induce excessive writes to accelerate device failure. To counter this, wear-leveling techniques aim to distribute write operations evenly across PCM cells. In this paper, we study the online PCM utilization problem , which seeks to maximize the number of write requests served before any cell reaches the erase limit. While extensively studied in the systems and architecture communities, this problem remains largely unexplored from a theoretical perspective. We bridge this gap by presenting a novel algorithm that leverages hardware feedback to optimize PCM utilization. We prove that our algorithm achieves near-optimal worst-case guarantees and outperforms state-of-the-art practical solutions both theoretically and empirically, providing an efficient approach to prolonging PCM lifespan.

In this work we study the classic problem of online weighted paging with a probabilistic prediction model, in which we are given additional information about the input in the form of distributions over page requests, known as distributional online paging (DOP). This work continues a recent line of research on learning-augmented algorithms that incorporates machine-learning predictions in online algorithms, so as to go beyond traditional worst-case competitive analysis, thus circumventing known lower bounds for online paging. We first provide an efficient online algorithm that achieves a constant factor competitive ratio with respect to the best online algorithm (policy) for weighted DOP that follows from earlier work on the stochastic k-server problem. Our main contribution concerns the question of whether distributional information over a limited horizon suffices for obtaining a constant competitive factor. To this end, we define in a natural way a new predictive model with limited horizon, which we call Per-Request Stochastic Prediction (PRSP). We show that we can obtain a constant factor competitive algorithm with respect to the optimal online algorithm for this model.

We formulate and study non-linear paging - a broad model of online paging where the size of subsets of pages is determined by a monotone non-linear set function of the pages. This model captures the well-studied classic weighted paging and generalized paging problems, and also submodular and supermodular paging, studied here for the first time, that have a range of applications from virtual memory to machine learning. Unlike classic paging, the cache threshold parameter k does not yield good competitive ratios for non-linear paging. Instead, we introduce a novel parameter 𝓁 that generalizes the notion of cache size to the non-linear setting. We obtain a tight deterministic 𝓁-competitive algorithm for general non-linear paging and a o(log²𝓁)-competitive lower bound for randomized algorithms. Our algorithm is based on a new generic LP for the problem that captures both submodular and supermodular paging, in contrast to LPs used for submodular cover settings. We finally focus on the supermodular paging problem, which is a variant of online set cover and online submodular cover, where sets are repeatedly requested to be removed from the cover. We obtain polylogarithmic lower and upper bounds and an offline approximation algorithm.

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).

Motivated by the design of real system storage hierarchies, we study the block-aware caching problem, a generalization of classic caching in which fetching (or evicting) pages from the same block incurs the same cost as fetching (or evicting) just one page from the block. Given a cache of size k, and a sequence of requests from n pages partitioned into given blocks of size β ≤ k, the goal is to minimize the total cost of fetching to (or evicting from) cache. This problem captures generalized caching as a special case, which is already NP-hard offline. We show the following suite of results:

The world is dynamic and changes over time, thus any optimization problem used to model real life problems must address this dynamic nature, taking into account the cost of changes to a solution over time. The multistage model was introduced with this goal in mind. In this model we are given a series of instances of an optimization problem, corresponding to different times, and a solution is provided for each instance. The strive for obtaining near-optimal solutions for each instance on one hand, while maintaining similar solutions for consecutive time units on the other hand, is quantified and integrated into the objective function. In this paper we consider the Generalized Multistage $d$-Knapsack problem, a generalization of the multistage variants of the Multiple Knapsack problem, as well as the $d$-Dimensional Knapsack problem. We present a PTAS for Generalized Multistage $d$-Knapsack.

Unstructured pruning reduces the memory footprint in deep neural networks (DNNs). Recently, researchers proposed different types of structural pruning intending to reduce also the computation complexity. In this work, we first suggest a new measure called mask-diversity which correlates with the expected accuracy of the different types of structural pruning. We focus on the recently suggested N:M fine-grained block sparsity mask, in which for each block of M weights, we have at least N zeros. While N:M fine-grained block sparsity allows acceleration in actual modern hardware, it can be used only to accelerate the inference phase. In order to allow for similar accelerations in the training phase, we suggest a novel transposable fine-grained sparsity mask, where the same mask can be used for both forward and backward passes. Our transposable mask guarantees that both the weight matrix and its transpose follow the same sparsity pattern; thus, the matrix multiplication required for passing the error backward can also be accelerated. We formulate the problem of finding the optimal transposable-mask as a minimum-cost flow problem. Additionally, to speed up the minimum-cost flow computation, we also introduce a fast linear-time approximation that can be used when the masks dynamically change during training. Our experiments suggest a 2x speed-up in the matrix multiplications with no accuracy degradation over vision and language models. Finally, to solve the problem of switching between different structure constraints, we suggest a method to convert a pre-trained model with unstructured sparsity to an N:M fine-grained block sparsity model with little to no training. A reference implementation can be found at https://github.com/papers-submission/structuredtransposablemasks.

We study the writeback-aware caching problem, a variant of classic paging where paging requests that modify data and requests that leave data intact are treated differently. We give an O(łog^2 k) competitive randomized algorithm, answering an open question of Beckmann ηl~BGHM20 and Even et al. (21) about the existence of a randomized poly-logarithmic competitive algorithm. Our algorithm also works for arbitrary page weights. We also give an O(k) competitive deterministic algorithm, extending the previous result of Beckmann et al. BGHM20 to the weighted setting.

Constrained submodular function maximization has been used in subset selection problems such as selection of most informative sensor locations. Although these models have been quite popular, the solutions obtained via this approach are unstable to perturbations in data defining the submodular functions. Robust submodular maximization has been proposed as a richer model that aims to overcome this discrepancy as well as increase the modeling scope of submodular optimization. In this work, we consider robust submodular maximization with structured combinatorial constraints and give efficient algorithms with provable guarantees. Our approach is applicable to constraints defined by single or multiple matroids and knapsack as well as distributionally robust criteria. We consider both the offline setting where the data defining the problem are known in advance and the online setting where the input data are revealed over time. For the offline setting, we give a general (nearly) optimal bicriteria approximation algorithm that relies on new extensions of classical algorithms for submodular maximization. For the online version of the problem, we give an algorithm that returns a bicriteria solution with sublinear regret. Summary of Contribution: Constrained submodular maximization is one of the core areas in combinatorial optimization with a wide variety of applications in operations research and computer science. Over the last decades, both communities have been interested on the design and analysis of new algorithms with provable guarantees. Sensor location, influence maximization and data summarization are some of the applications of submodular optimization that lie at the intersection of the aforementioned communities. Particularly, our work focuses on optimizing several submodular functions simultaneously. We provide new insights and algorithms to the offline and online variants of the problem which significantly expand the related literature. At the same time, we provide a computational study that supports our theoretical results.

Multi-access Edge Computing (MEC) is a new networking paradigm considered to be one of the enablers of 5G networks. In particular, it allows for network operators to provide low latency services by moving the service logic from centralized datacenters to small distributed locations at the edge of a network. However, computing and storage resources at these edge nodes are scarce and thus efficient resource allocation becomes an essential building block in any MEC orchestration solution. In this paper we address one particular challenge in this domain - how to place network functions at the edge nodes in a way that maximizes the customers benefit. Thus, we formulate the Capacitated MEC Allocation Problem (CMAP) and provide multiple algorithms with analytical performance guarantees for this problem. Furthermore, we use extensive simulations to evaluate the performance of our algorithms in realistic scenarios and show that they outperform both the analytical worst case guarantees, as well as currently used network function placement methods.

We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint (SMKP). The input is a set I of items, each associated with a non-negative weight, and a set of bins having arbitrary capacities. Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a subset of items A ⊆ I and a packing of these items in the bins, such that f(A) is maximized. SMKP is a natural extension of both Multiple Knapsack and the problem of monotone submodular maximization subject to a knapsack constraint. Our main result is a nearly optimal polynomial time (1-e^{-1}-ε)-approximation algorithm for the problem, for any ε > 0. Our algorithm relies on a refined analysis of techniques for constrained submodular optimization combined with sophisticated application of tools used in the development of approximation schemes for packing problems.

Constrained submodular function maximization has been used in subset selection problems such as selection of most informative sensor locations. While these models have been quite popular, the solutions obtained via this approach are unstable to perturbations in data defining the submodular functions. Robust submodular maximization has been proposed as a richer model that aims to overcome this discrepancy as well as increase the modeling scope of submodular optimization. In this work, we consider robust submodular maximization with structured combinatorial constraints and give efficient algorithms with provable guarantees. Our approach is applicable to constraints defined by single or multiple matroids, knapsack as well as distributionally robust criteria. We consider both the offline setting where the data defining the problem is known in advance as well as the online setting where the input data is revealed over time. For the offline setting, we give a nearly optimal bi-criteria approximation algorithm that relies on new extensions of the classical greedy algorithm. For the online version of the problem, we give an algorithm that returns a bi-criteria solution with sub-linear regret.

The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an n-vertex spanning tree T and an additional set L of edges (called links) with costs. Then, terminal pairs arrive one-by-one and our task is to maintain a low-cost subset of links F such that every terminal pair that has arrived so far is 2-edge-connected in T cup F. This online problem was first studied by Gupta, Krishnaswamy and Ravi (SICOMP 2012) who used it as a subroutine for the online survivable network design problem. They gave a deterministic O(log^2 n)-competitive algorithm and showed an Omega(log n) lower bound on the competitive ratio of randomized algorithms. The case when T is a path is also interesting: it is exactly the online interval set cover problem, which also captures as a special case the parking permit problem studied by Meyerson (FOCS 2005). The contribution of this paper is to give tight results for online weighted tree and path augmentation problems. The main result of this work is a deterministic O(log n)-competitive algorithm for online WTAP, which is tight up to constant factors.

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.

We consider a common setting where storage is disaggregated from the compute in data-parallel systems. Colocating caching tiers with the compute machines can reduce load on the interconnect but doing so leads to new resource management challenges. We design a system Netco, which prefetches data into the cache (based on workload predictability), and appropriately divides the cache space and network bandwidth between the prefetches and serving ongoing jobs. Netco makes various decisions (what content to cache, when to cache and how to apportion bandwidth) to support end-to-end optimization goals such as maximizing the number of jobs that meet their service-level objectives (e.g., deadlines). Our implementation of these ideas is available within the open-source Apache HDFS project. Experiments on a public cloud, with production-trace inspired workloads, show that Netco uses up to 5x less remote I/O compared to existing techniques and increases the number of jobs that meet their deadlines up to 80%.

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.

We introduce correlated randomized dependent rounding where, given multiple points y^1,...,y^n in some polytope P\subseteq [0,1]^k, the goal is to simultaneously round each y^i to some integral z^i in P while preserving both marginal values and expected distances between the points. In addition to being a natural question in its own right, the correlated randomized dependent rounding problem is motivated by multi-label classification applications that arise in machine learning, e.g., classification of web pages, semantic tagging of images, and functional genomics. The results of this work can be summarized as follows: (1) we present an algorithm for solving the correlated randomized dependent rounding problem in uniform matroids while losing only a factor of O(log{k}) in the distances (k is the size of the ground set); (2) we introduce a novel multi-label classification problem, the metric multi-labeling problem, which captures the above applications. We present a (true) O(log{k})-approximation for the general case of metric multi-labeling and a tight 2-approximation for the special case where there is no limit on the number of labels that can be assigned to an object.

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.

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.

We consider semidefinite programming through the lens of online algorithms - what happens if not all input is given at once, but rather iteratively? In what way does it make sense for a semidefinite program to be revealed? We answer these questions by defining a model for online semidefinite programming. This model can be viewed as a generalization of online coveringpacking linear programs, and it also captures interesting problems from quantum information theory. We design an online algorithm for semidefinite programming, utilizing the online primaldual method, achieving a competitive ratio of O(log(n)), where n is the number of matrices in the primal semidefinite program. We also design an algorithm for semidefinite programming with box constraints, achieving a competitive ratio of O(log F*), where F* is a sparsity measure of the semidefinite program. We conclude with an online randomized rounding procedure.

We initiate the study of scenarios that combine online decision making with interaction between noncooperative agents. To this end we introduce online games that model such scenarios as noncooperative games, and lay the foundations for studying this model. Roughly speaking, an online game captures systems in which independent agents serve requests in a common environment. The requests arrive in an online fashion, and each is designated to be served by a different agent. The cost incurred by serving a request is paid by the serving agent, and naturally the agents seek to minimize the total cost to themselves. Since the agents are independent, it is unlikely that some central authority can enforce a policy or an algorithm (centralized or distributed) on them, and thus, the agents can be viewed as selfish players in a noncooperative game. In this game, the players have to choose as a strategy an online algorithm according to which requests are served. To further facilitate the game-theoretic approach, we suggest the measure of competitive analysis as the players' decision criterion. As the expected result of noncooperative games is an equilibrium, the question of finding the equilibria of a game is of central importance, and thus it is the central issue on which we concentrate in this paper. We study some natural examples for online games; in order to obtain general insights and develop generic techniques, we present an abstract model for the study of online games generalizing metrical task systems. We suggest a method for constructing equilibria in this model and further devise techniques for implementing it.

Network Function Virtualization (NFV) is a new networking paradigm where network functions are executed on commodity servers located in small cloud nodes distributed across the network, and where software defined mechanisms are used to control the network flows. This paradigm is a major turning point in the evolution of networking, as it introduces high expectations for enhanced economical network services, as well as major technical challenges. In this paper, we address one of the main technical challenges in this domain: the actual placement of the virtual functions within the physical network. This placement has a critical impact on the performance of the network, as well as on its reliability and operation cost. We perform a thorough study of the NFV location problem, show that it introduces a new type of optimization problems, and provide near optimal approximation algorithms guaranteeing a placement with theoretically proven performance. The performance of the solution is evaluated with respect to two measures: the distance cost between the clients and the virtual functions by which they are served, as well as the setup costs of these functions. We provide bi-criteria solutions reaching constant approximation factors with respect to the overall performance, and adhering to the capacity constraints of the networking infrastructure by a constant factor as well. Finally, using extensive simulations, we show that the proposed algorithms perform well in many realistic scenarios.

We study online mechanisms for preemptive scheduling with deadlines, with the goal of maximizing the total value of completed jobs. This problem is fundamental to deadline-aware cloud scheduling, but there are strong lower bounds even for the algorithmic problem without incentive constraints. However, these lower bounds can be circumvented under the natural assumption of deadline slackness, i.e., that there is a guaranteed lower bound s > 1 on the ratio between a job's size and the time window in which it can be executed. In this paper, we construct a truthful scheduling mechanism with a constant competitive ratio, given slackness s > 1. Furthermore, we show that if s is large enough then we can construct a mechanism that also satisfies a commitment property: it can be determined whether or not a job will finish, and the requisite payment if so, well in advance of each job's deadline. This is notable because, in practice, users with strict deadlines may find it unacceptable to discover only very close to their deadline that their job has been rejected.

Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than (1-1/e)-competitive ([Karp et al. 1990; Mehta et al. 2007]), yet simple heuristics have been observed to perform much better in practice. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by [Buchbinder et al. 2007), graphs which we call (k,d)-bounded. In such graphs the maximal degree on the online side is at most d and the minimal degree on the offline side is at least k. We prove that for such graphs, these problems' natural greedy algorithms attain competitive ratio 1-(d-1)/(k+d-1), tending to one as d/k tends to zero. We prove this bound is tight for these algorithms. Next, we develop deterministic primal-dual algorithms for the above problems achieving competitive ratio 1-(1-1/d)k>1-1/ek/d, or exponentially better loss as a function of k/d, and strictly better than 1-1/e whenever k ≥ d. We complement our lower bounds with matching upper bounds for the vertex-weighted problem. Finally, we use our deterministic algorithms to prove by dual-fitting that simple randomized algorithms achieve the same bounds in expectation. Our algorithms and analysis differ from previous ad allocation algorithms, which largely scale bids based on the spent fraction of their bidder's budget, whereas we scale bids according to the number of times the bidder could have spent as much as her current bid. Our algorithms differ from previous online primal-dual algorithms, as they do not maintain dual feasibility, but only primal-to-dual ratio, and only attain dual feasibility upon termination. We believe our techniques could find applications to other well-behaved online packing problems.

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.

Software Defined Networks (SDNs) are becoming the leading technology behind many traffic engineering solutions, both for backbone and data-center networks, since it allows a central controller to globally plan the path of the flows according to the operator's objective. Nevertheless, networking devices' forwarding table is a limited and expensive resource (e.g., TCAM-based switches) which should thus be considered upon configuring the network. In this paper, we concentrate on satisfying global network objectives, such as maximum flow, in environments where the size of the forwarding table in network devices is limited. We formulate this problem as an (NP-hard) optimization problem and present approximation algorithms for it. We show through extensive simulations that practical use of our algorithms (both in Data Center and backbone scenarios) result in a significant reduction (factor 3) in forwarding table size, while having a small effect on the global objective (maximum flow).

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.

We consider the problem of Non-Uniform Graph Partitioning, where the input is an edge-weighted undirected graph G = (V, E) and k capacities n1, …, nk, and the goal is to find a partition {S1, S2, …, Sk} of V satisfying |Sj| ≤ nj for all 1 ≤ j ≤ k, that minimizes the total weight of edges crossing between different parts. This natural graph partitioning problem arises in practical scenarios, and generalizes well-studied balanced partitioning problems such as Minimum Bisection, Minimum Balanced Cut, and Minimum k-Partitioning. Unlike these problems, Non-Uniform Graph Partitioning seems to be resistant to many of the known partitioning techniques, such as spreading metrics, recursive partitioning, and Räcke's tree decomposition, because k can be a function of n and the capacities could be of different magnitudes. We present a bicriteria approximation algorithm for Non-Uniform Graph Partitioning that approximates the objective within O(logn) factor while deviating from the required capacities by at most a constant factor. Our approach is to apply stopping-time based concentration results to a simple randomized rounding of a configuration LP. These concentration bounds are needed as the commonly used techniques of bounded differences and bounded conditioned variances do not suffice.

This paper presents a novel algorithm for scheduling big data jobs on large compute clusters. In our model, each job is represented by a DAG consisting of several stages linked by precedence constraints. The resource allocation per stage is malleable, in the sense that the processing time of a stage depends on the resources allocated to it (the dependency can be arbitrary in general).The goal of the scheduler is to maximize the total value of completed jobs, where the value for each job depends on its completion time. We design an algorithm for the problem which guarantees an expected constant approximation factor when the cluster capacity is sufficiently high. To the best of our knowledge, this is the first constant-factor approximation algorithm for the problem. The algorithm is based on formulating the problem as a linear program and then rounding an optimal (fractional) solution into a feasible (integral) schedule using randomized rounding.

We study graph partitioning problems from a min-max perspective, in which an input graph on $n$ vertices should be partitioned into $k$ parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the $k$ parts need to be of equal size, and where they must separate a set of $k$ given terminals. We consider a common generalization of these two problems, and design for it an $O(\sqrt{\log n\log k})$ approximation algorithm. This improves over an $O(\log^2 n)$ approximation for the second version due to Svitkina and Tardos [Min-max multiway cut, in APPROX-RANDOM, 2004, Springer, Berlin, 2004], and roughly $O(k\log n)$ approximation for the first version that follows from other previous work. We also give an $O(1)$ approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the small-set expansion problem. In this problem, we are given a graph $G$ and the goal is to find a nonempty set $S\subseteq V$ of size $|S| \leq \rho n$ with minimum edge expansion. We give an $O(\sqrt{\log{n}\log{(1/\rho)}})$ bicriteria approximation algorithm for small-set expansion in general graphs, and an improved factor of $O(1)$ for graphs that exclude any fixed minor.

The recent growing popularity of cloud-based solutions and the variety of new applications present new challenges for cloud management and resource utilization. In this paper we concentrate on the networking aspect and consider the placement problem of virtual machines (VMs) of applications with intense bandwidth requirements. Optimizing the available network bandwidth is far more complex than optimizing resources like memory or CPU, since every network link may be used by many physical hosts and thus by the VMs residing in these hosts. We focus on maximizing the benefit from the overall communication sent by the VMs to a single designated point in the data center (called the root). This is the typical case when considering a storage area network of applications with intense storage requirements. We formulate a bandwidth-constrained VM placement optimization problem that models this setting. This problem is NP hard, and we present a polynomial-time constant approximation algorithm for its most general version, in which hosts are connected to the root by a general network graph. For more practical cases, in which the network topology is a tree and the revenue is a simple function of the allocated bandwidth, we present improved approximation algorithms that are more efficient in terms of running time. We evaluate the expected performance of our proposed algorithms through a simulation study over traces from a real production data center, providing strong indications to the superiority of our proposed solutions.

We consider mechanisms for online deadline-aware scheduling in large computing clusters. Batch jobs that run on such clusters often require guarantees on their completion time (i.e., deadlines). However, most existing scheduling systems implement fair-share resource allocation between users, an approach that ignores heterogeneity in job requirements and may cause deadlines to be missed.

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.

Clustering, the partitioning of objects with respect to a similarity measure, has been extensively studied as a global optimization problem. We investigate clustering from a game theoretic approach, and consider the class of hedonic clustering games. Here, a self organized clustering is obtained via decisions made by independent players, corresponding to the elements clustered. Being a hedonic setting, the utility of each player is determined by the identity of the other members of her cluster. This class of games seems to be quite robust, as it fits with rather different, yet commonly used, clustering criteria. Specifically, we investigate hedonic clustering games in two different models: fixed clustering, which subdivides into k-median and k-center, and correlation clustering. We provide a thorough and non-trivial analysis of these games, characterizing Nash equilibria, and proving upper and lower bounds on the price of anarchy and price of stability. For fixed clustering we focus on the existence of a Nash equilibrium, as it is a rather non-trivial issue in this setting. We study it both for general metrics and special cases, such as line and tree metrics. In the correlation clustering model, we study both minimization and maximization variants, and provide almost tight bounds on both price of anarchy and price of stability.

We consider a market-based resource allocation model for batch jobs in cloud computing clusters. In our model, we incorporate the importance of the due date of a job rather than the number of servers allocated to it at any given time. Each batch job is characterized by the work volume of total computing units (e.g., CPU hours) along with a bound on maximum degree of parallelism. Users specify, along with these job characteristics, their desired due date and a value for finishing the job by its deadline. Given this specification, the primary goal is to determine the scheduling} of cloud computing instances under capacity constraints in order to maximize the social welfare (i.e., sum of values gained by allocated users). Our main result is a new ( C/(C-k) ⋅ s/(s-1))-approximation algorithm for this objective, where C denotes cloud capacity, k is the maximal bound on parallelized execution (in practical settings, k l C) and s is the slackness on the job completion time i.e., the minimal ratio between a specified deadline and the earliest finish time of a job. Our algorithm is based on utilizing dual fitting arguments over a strengthened linear program to 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.

Abstract Problems dealing with assignment of clients to servers have been widely studied. However, they usually do not model the fact that the delay incurred by a client is a function of both the distance to the assigned server and the load on this server, under a given assignment. We study a problem referred to as the load‐distance balancing (LDB) problem, where the objective is assigning a set of clients to a set of given servers. Each client suffers a delay, that is, the sum of the network delay (which is proportional to the distance to its server) and the congestion delay at this server, a nondecreasing function of the number of clients assigned to the server. We address two flavors of LDB—the first one seeking to minimize the maximum incurred delay, and the second one targeted for minimizing the average delay. For the first variation, we present hardness results, a best possible approximation algorithm, and an optimal algorithm for a special case of linear placement of clients and servers. For the second one, we show the problem is NP‐hard in general, and present a 2‐approximation for concave delay functions and an exact algorithm, if the delay function is convex. We also consider the game theoretic version of the second problem and show the price of stability of the game is at most 2 and at least 4/3. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

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 study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are: (i) the k parts need to be of equal size, and (ii) the parts must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an O(√log n log k)-approximation algorithm. This improves over an O(log2n) approximation for the second version due to Svitkina and Tardos, and roughly O(k log n) approximation for the first version that follows from other previous work. We also give an improved O(1)-approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the Small Set Expansion problem. In this problem, we are given a graph G and the goal is to find a non-empty subset S of V of size at most pn with minimum edge-expansion. We give an O(√log n log (1/p)) bicriteria approximation algorithm for the general case of Small Set Expansion and O(1) approximation algorithm for graphs that exclude any fixed minor.

The study of combinatorial problems with a submodular objective function has attracted much attention in recent years, and is partly motivated by the importance of such problems to economics, algorithmic game theory and combinatorial optimization. Classical works on these problems are mostly combinatorial in nature. Recently, however, many results based on continuous algorithmic tools have emerged. The main bottleneck of such continuous techniques is how to approximately solve a non-convex relaxation for the sub- modular problem at hand. Thus, the efficient computation of better fractional solutions immediately implies improved approximations for numerous applications. A simple and elegant method, called "continuous greedy", successfully tackles this issue for monotone submodular objective functions, however, only much more complex tools are known to work for general non-monotone submodular objectives. In this work we present a new unified continuous greedy algorithm which finds approximate fractional solutions for both the non-monotone and monotone cases, and improves on the approximation ratio for many applications. For general non-monotone submodular objective functions, our algorithm achieves an improved approximation ratio of about 1/e. For monotone submodular objective functions, our algorithm achieves an approximation ratio that depends on the density of the polytope defined by the problem at hand, which is always at least as good as the previously known best approximation ratio of 1-1/e. Some notable immediate implications are an improved 1/e-approximation for maximizing a non-monotone submodular function subject to a matroid or O(1)-knapsack constraints, and information-theoretic tight approximations for Submodular Max-SAT and Submodular Welfare with k players, for any number of players k. A framework for submodular optimization problems, called the contention resolution framework, was introduced recently by Chekuri et al. [11]. The improved approximation ratio of the unified continuous greedy algorithm implies improved ap- proximation ratios for many problems through this framework. Moreover, via a parameter called stopping time, our algorithm merges the relaxation solving and re-normalization steps of the framework, and achieves, for some applications, further improvements. We also describe new monotone balanced con- tention resolution schemes for various matching, scheduling and packing problems, thus, improving the approximations achieved for these problems via the framework.

We obtain the first online algorithms for the node-weighted Steiner tree, Steiner forest and group Steiner tree problems that achieve a poly-logarithmic competitive ratio. Our algorithm for the Steiner tree problem runs in polynomial time, while those for the other two problems take quasi-polynomial time. Our algorithms can be viewed as online LP rounding algorithms in the framework of Buchbinder and Naor (Foundations and Trends in Theoretical Computer Science, 2009); however, while the natural LP formulation of these problems do lead to fractional algorithms with a poly-logarithmic competitive ratio, we are unable to round these LPs online without losing a polynomial factor. Therefore, we design new LP formulations for these problems drawing on a combination of paradigms such as spider decompositions, low-depth Steiner trees, generalized group Steiner problems, etc. and use the additional structure provided by these to round the more sophisticated LPs losing only a poly-logarithmic factor in the competitive ratio. As further applications of our techniques, we also design polynomial-time online algorithms with poly-logarithmic competitive ratios for two fundamental network design problems in edge-weighted graphs: the group Steiner forest problem (thereby resolving an open question raised by Chekuri et. al. (SODA 2008)) and the single source ℓ-vertex connectivity problem (which complements similar results for the corresponding edge-connectivity problem due to Gupta et. al. (STOC 2009)).

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.

The delivery of latency sensitive packets is a crucial issue in real time applications of communication networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. The deadline, however, applies only to the packet's journey through the entire network; individual routers along the packet's route face a more flexible deadline. We consider policies for admitting latency sensitive packets at a router. Each packet is tagged with a value and a packet waiting at a router loses value over time as its probability of arriving at its destination decreases. The router is modeled as a non-preemptive queue, and its objective is to maximize the total value of the forwarded packets. When a router receives a packet, it must either accept it (and possibly delay future packets), or reject it immediately. The best policy depends on the set of values that a packet can take. We consider three natural settings: unrestricted model, real-valued model, where any value above 1 is allowed, and an integral-valued model. We obtain the following results. For the unrestricted model, we prove that there is no constant competitive ratio algorithm. The real valued model has a randomized 4-competitive algorithm and a matching lower bound. We also give for the last model a deterministic lower bound of ¿3¿ 4.236, almost matching the previously known 4.24-competitive algorithm. For the integral-valued model, we show a deterministic 4-competitive algorithm, and prove that this is tight even for randomized algorithms.

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.

We consider the problem of embedding a directed graph onto evenly spaced points on a circle while minimizing the total weighted edge length. We present the first poly-logarithmic approximation factor algorithm for this problem which yields an approximation factor of O (log n log log n ), thus improving the previous Õ (√ n ) approximation factor. In order to achieve this, we introduce a new problem which we call the directed penalized linear arrangement . This problem generalizes both the directed feedback edge set problem and the directed linear arrangement problem. We present an O (log n log log n )-approximation factor algorithm for this newly defined problem. Our solution uses two distinct directed metrics (“right” and “left”) which together yield a lower bound on the value of an optimal solution. In addition, we define a sequence of new directed spreading metrics that are used for applying the algorithm recursively on smaller subgraphs. The new spreading metrics allow us to define an asymmetric region growing procedure that accounts simultaneously for both incoming and outgoing edges. To the best of our knowledge, this is the first time that a region growing procedure is defined in directed graphs that allows for such an accounting.

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 consider a multipacket reception channel shared by several communication applications. This is the case, for example, in a single radio mesh network where neighboring cells use the same radio channel. In such scenarios, unlike the common multiple access model, several transmissions may succeed simultaneously, depending on the actual locations of the sending and receiving stations, and thus channel utilization may be greater than 1. Our goal is to derive a decentralized access control mechanism that maximizes the channel utilization, while taking into account fairness among the different users. We focus on a simple case where each user can adjust a single parameter that determines its transmission probability in any time slot, and develop such a protocol for the general problem, where users are distributed arbitrarily, based on strong motivation which is derived from analytical bounds for homogeneous interferences. We further show, using extensive simulations, that this protocol achieves a high utilization of radio resources compared to any other protocol (not necessarily based on a simple parameter), while maintaining fairness between all users.

We consider the k-balanced partitioning problem, where the goal is to partition the vertices of an input graph G into k equally sized components, while minimizing the total weight of the edges connecting different components. We allow k to be part of the input and denote the cardinality of the vertex set by n. This problem is a natural and important generalization of well-known graph partitioning problems, including minimum bisection and minimum balanced cut. We present a (bi-criteria) approximation algorithm achieving an approximation of , which matches or improves over previous algorithms for all relevant values of k. Our algorithm uses a semidefinite relaxation which combines metrics with spreading metrics. Surprisingly, we show that the integrality gap of the semidefinite relaxation is Ω(log k) even for large values of k (e.g., k = nΩ(1)), implying that the dependence on k of the approximation factor is necessary. This is in contrast to previous approximation algorithms for k-balanced partitioning, which are based on linear programming relaxations and their approximation factor is independent of k.

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 present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds $B_v$ on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a $(2,2B_v+3)$-approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex v is at most $2B_v+3$. This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly k-Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost $\lambda$-edge-connected subgraph with at least k vertices, which we call the $(k,\lambda)$-subgraph problem. This generalizes some well-studied classical problems such as the k-MST and the minimum cost $\lambda$-edge-connected subgraph problems. We give a polylogarithmic approximation for the $(k,2)$-subgraph problem. However, by relating it to the Densest k-Subgraph problem, we provide evidence that the $(k,\lambda)$-subgraph problem might be hard to approximate for arbitrary $\lambda$.

We consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of n jobs and k parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or nonexplicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a nonpreemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + ε) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + ε, respectively. We also give approximation algorithms for two special cases when all release times are the same.

We consider a multicast game played by a set of selfish noncooperative players (i.e., nodes) on a rooted undirected graph. Players arrive one by one and each connects to the root by greedily choosing a path minimizing its cost; the cost of using an edge is split equally among all users using the edge. How large can the sum of the players' costs be, compared to the cost of a "socially optimal" solution, defined to be a minimum Steiner tree connecting the players to the root? We show that the ratio is O(log2 n) and ©(log n), when there are n players. One can view this multicast game as a variant of Online Steiner Tree with a different cost sharing mechanism.

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.

The connection between integrality gaps and computational hardness of discrete optimization problems is an intriguing question. In recent years, this connection has prominently figured in several tight UGC-based hardness results. We show in this paper a direct way of turning integrality gaps into hardness results for several fundamental classification problems. Specifically, we convert linear programming integrality gaps for the Multiway Cut, 0-Extension, and and Metric Labeling problems into UGC-based hardness results. Qualitatively, our result suggests that if the unique games conjecture is true then a linear relaxation of the latter problems studied in several papers (so-called earthmover linear program) yields the best possible approximation. Taking this a step further, we also obtain integrality gaps for a semi-definite programming relaxation matching the integrality gaps of the earthmover linear program. Prior to this work, there was an intriguing possibility of obtaining better approximation factors for labeling problems via semi-definite programming.

Consider the following classical network design problem: a set of terminals T = { t i } wishes to send traffic to a root r in an n -node graph G = ( V , E ). Each terminal t i sends d i units of traffic and enough bandwidth has to be allocated on the edges to permit this. However, bandwidth on an edge e can only be allocated in integral multiples of some base capacity u e and hence provisioning k × u e bandwidth on edge e incurs a cost of ⌈k⌉ times the cost of that edge. The objective is a minimum-cost feasible solution. This is one of many network design problems widely studied where the bandwidth allocation is governed by side constraints: edges can only allow a subset of cables to be purchased on them or certain quality-of-service requirements may have to be met. In this work, we show that this problem and, in fact, several basic problems in this general network design framework cannot be approximated better than Ω(log log n ) unless NP ⊆ DTIME ( n O (log log log n ) ), where | V | = n . In particular, we show that this inapproximability threshold holds for (i) the Priority-Steiner Tree problem, (ii) the (single-sink) Cost-Distance problem, and (iii) the single-sink version of an even more fundamental problem, Fixed Charge Network Flow. Our results provide a further breakthrough in the understanding of the level of complexity of network design problems. These are the first nonconstant hardness results known for all these problems.

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].

The forthcoming 4G cellular systems will provide broadband wireless access to a variety of advanced data and voice services. In order to do that, these networks will have a significantly larger number of base stations and a much higher bandwidth demand from their radio access networks. This will motivate operators to replace the commonly used star based architecture, in which an RNC is connected to a set of base stations via direct links, with a more complex tree structure, in which a base station can be connected to an RNC via other base stations. In this paper we address algorithmic aspects of this challenging design problem, in which tree-topology is used to connect base stations and RNCs. We formulate the problem as an optimization problem and prove that it is NP-hard to approximate it in the general case. For the metric case, however, we develop an O(log n)-approximation algorithm. We then study the performance of this algorithm and several other heuristics in practical scenarios. Our results indicate that a combination of a certain greedy heuristic and the proven approximation algorithm, generates a solution that produces close to optimal results in practical scenarios and can be efficiently computed for sufficiently large network sizes.

Routing traffic so as to maximize the lifetime of a transmission is a major problem in wireless networks. We address a two-way multicast problem, where a root wishes to transmit data to a subset of nodes, as well as receive data from them. In addition, we consider the anycast problem, wherethere is a subset of nodes that wish to communicate with each other. We consider both a per-hop multi-recipients environment, where over each hop, the transmission is received by all nodes within range, and a per-hop single-recipient environment, where over each hop the transmission is received by a single recipient. For both environments, our work consists of two parts. In the first part we focus on system optimization perspectives of the lifetime maximization problem, while in the second part we investigate the game-theoretic perspective of the respective problems.We first note that, for the per-hop multi-recipients environment, an optimal solution can be computed in polynomial time. Nevertheless, for the per-hop single-recipient environment, we observe that computing an optimal solution is NP-hard. Accordingly, we provide a polynomial time algorithm that finds a 2-approximate solution for the case of uniform transmission power levels. For different transmission power levels, we provide an O(log2n) approximation algorithm for the general problem, and an O(log n) approximation algorithm for the special case where the set of terminals equals the set of all nodes, whose size equals n.For each environment, we consider the corresponding noncooperative game scenario, and prove that by following the natural game course users converge to a Nash equilibrium. For the per-hop multi-recipients environment, we show that if the players join the game sequentially, the Nash equilibrium is (networkwide) optimal. For the per-hop single-recipient environment, we show that the price of anarchy is unbounded. On the other hand, we show that for both environments, the price of stability, where the best Nash equilibrium is considered, is 1; hence, optimal (networkwide) performance can be achieved if the initial configuration can be imposed on the players.

We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds Bv on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a (2, 2Bv +3)-approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex v is at most 2Bv + 3. This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly k-Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic

We consider a multicast game with selfish non- cooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model, where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium. The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with in players, we establish an upper bound of O(radicnlog2n) on the price of anarchy, and a lower bound of Omega(log n/log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm for computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium.

The metric labeling problem is an elegant and powerful mathematical model capturing a wide range of classification problems. The input to the problem consists of a set L of labels and a weighted graph $G=(V,E)$. Additionally, a metric distance function on the labels is defined, and for each label and each vertex, an assignment cost is given. The goal is to find a minimum‐cost assignment of the vertices to the labels. The cost of the solution consists of two parts: the assignment costs of the vertices and the separation costs of the edges (where each edge pays its weight times the distance between the two labels to which its endpoints are assigned). Due to the simple structure and the variety of applications, the problem and its special cases (with various distance functions on the labels) have recently received much attention. Metric labeling is known to have a logarithmic approximation, and it has been an open question for some time whether a constant approximation exists. We refute this possibility and prove that no constant factor approximation algorithm exists for metric labeling unless P=NP. Moreover, we prove that the problem is $\Omega((\log |V|)^{1/2-\delta})$‐hard to approximate for any constant $\delta: 0<\delta<1/2$, unless NP has quasi‐polynomial time algorithms.

We study algorithmic problems that are motivated by bandwidth trading in next-generation networks. Typically, bandwidth trading involves sellers (e.g., network operators) interested in selling bandwidth pipes that offer to buyers a guaranteed level of service for a specified time interval. The buyers (e.g., bandwidth brokers) are looking to procure bandwidth pipes to satisfy the reservation requests of end-users (e.g., Internet subscribers). Depending on what is available in the bandwidth exchange, the goal of a buyer is to either spend the least amount of money so as to satisfy all the reservations made by its customers, or to maximize its revenue from whatever reservations can be satisfied.

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 consider a multicast game with selfish non-cooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model, where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium.The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with n players, we establish an upper bound of O(√n log2n) on the price of anarchy, and a lower bound of Ω(log n/ log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm for computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium.

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 the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. In this problem, we are given a directed graph and a set of source-sink pairs. The goal is to route all the pairs with minimum congestion on the network edges. The second problem is machine scheduling , where we are given a set of jobs, and for each job, there is a list of intervals on which it can be scheduled. The goal is to find the smallest number of machines on which all jobs can be scheduled such that no two jobs overlap in their execution on any machine. Both problems are known to be O (log n /log log n )-approximable via the randomized rounding technique of Raghavan and Thompson [1987]. However, until recently, only Max SNP hardness was known for each problem. We make progress in closing this gap by showing that both problems are Ω(log log n )-hard to approximate unless NP ⊆ DTIME( n O (log log log n ) ).

We consider the problem of scheduling jobs that are given as groups of nonintersecting segments on the real line. Each job $J_j$ is associated with an interval, $I_j$, which consists of up to t segments, for some $t \geq 1$, and a weight (profit), $w_j$; two jobs are in conflict if their intervals intersect. Such jobs show up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g., bandwidth in linear processor arrays), and computational biology/geometry. The objective is to schedule a subset of nonconflicting jobs of maximum total weight. Our problem can be formulated as the problem of finding a maximum weight independent set in a t-interval graph (the special case of $t=1$ is an ordinary interval graph). We show that, for $t \geq 2$, this problem is APX-hard, even for highly restricted instances. Our main result is a $2t$-approximation algorithm for general instances. This is based on a novel fractional version of the Local Ratio technique. One implication of this result is the first constant factor approximation for nonoverlapping alignment of genomic sequences. We also derive a bicriteria polynomial time approximation scheme for a restricted subclass of t-interval graphs.

We consider the classical vertex cover and set cover problems with hard capacity constraints. This means that a set (vertex) can cover only a limited number of its elements (adjacent edges), and the number of available copies of each set (vertex) is bounded. This is a natural generalization of the classical problems which also captures resource limitations in practical scenarios. We obtain the following results. For the unweighted vertex cover problem with hard capacities we give a 3‐approximation algorithm that is based on randomized rounding with alterations. We prove that the weighted version is at least as hard as the set cover problem, yielding an interesting separation between the approximability of weighted and unweighted versions of a “natural” graph problem. A logarithmic approximation factor for both the set cover and the weighted vertex cover problem with hard capacities follows from the work of Wolsey [Combinatorica, 2 (1982), pp. 385–393] on submodular set cover. We provide here a simple and intuitive proof for this bound.

We consider the Steiner k-cut problem which generalizes both the k-cut problem and the multiway cut problem. The Steiner k-cut problem is defined as follows. Given an edge-weighted undirected graph $G=(V, E)$, a subset of vertices $X \subseteq V$ called {\em terminals}, and an integer $k \le |X|$, the objective is to find a minimum weight set of edges whose removal results in k disconnected components, each of which contains at least one terminal. We give two approximation algorithms for the problem: a greedy $(2-\frac{2}{k})$-approximation based on Gomory--Hu trees, and a $(2 - \frac{2}{|X|})$-approximation based on rounding a linear program. We use the insight from the rounding to develop an exact bidirected formulation for the global minimum cut problem (the k-cut problem with $k=2$).

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.

We consider the problem of scheduling a sequence of packets over a linear network, where every packet has a source and a target, as well as a release time and a deadline by which it must arrive at its target. The model we consider is bufferless, where packets are not allowed to be buffered in nodes along their paths other than at their source. This model applies to optical networks where opto-electronic conversion is costly, and packets mostly travel through bufferless hops. The offline version of this problem was previously studied in M. Adler et al. (2002). In this paper we study the online version of the problem, where we are required to schedule the packets without knowledge of future packet arrivals. We use competitive analysis to evaluate the performance of our algorithms. We present the first deterministic online algorithms for several versions of the problem. For the problem of throughput maximization, where all packets have uniform weights, we give an algorithm with a logarithmic competitive ratio, and present some lower bounds. For other weight functions, we show algorithms that achieve optimal competitive ratios. We complete our study with several experimental results.

Service providers rely on the management systems housed in their Network Operations Centers (NOCs) to remotely operate, monitor and provision their data networks. Lately there has been a tremendous increase in management traffic due to the growing complexity and size of the data networks and the services provisioned on them. Traffic engineering for management flows is essential for the smooth functioning of these networks to avoid congestion, which can result in loss of critical data such as billing records, network alarms, etc. As is the case with most intra-domain routing protocols, the management flows in many of these networks are routed on shortest paths connecting the NOC with the service provider's POPs (points of presence). This collection of paths thus forms a "confluent" tree rooted at the gateway router connected to the NOC. The links close to the gateway router may form a bottleneck in this tree resulting in congestion. Typically this congestion is alleviated by adding layer two tunnels (virtual links) that offload the traffic from some links of this tree by routing it directly to the gateway router. The traffic engineering problem is then to minimize the number of virtual links needed for alleviating congestion. The traffic engineering problem described above also has applications to alleviating congestion resulting from focused overloads in VoIP networks and for dealing with congesting resulting from flash crowds in the world wide web.In this paper we formulate a traffic engineering problem motivated by the above mentioned applications. We show that the general versions of this problem are hard to solve. However, for some simpler cases in which the underlying network is a tree, we design efficient algorithms. We use these algorithms as the basis for designing efficient heuristics for alleviating congestion in general (non-tree) service provider network topologies.

We define the balanced metric labeling problem, a generalization of the metric labeling problem, in which each label has a capacity, i.e., at most l vertices can be assigned to it. The balanced metric labeling problem is a generalization of fundamental problems in the area of approximation algorithms, e.g., arrangements and balanced partitions of graphs. It is also motivated by resource limitations in certain practical scenarios. We focus on the case where the given metric is uniform and note that this case alone encompasses various well-known graph partitioning problems. We present the first (pseudo) approximation algorithm for this problem, achieving for any ε, 0 < ε < 1, an approximation factor of O((ln n)/ε), while assigning at most min {O(ln k)/1 - ε, l + 1| ( 1 + ε) l vertices to each label (k is the number of labels). Our approximation algorithm is based on a novel randomized rounding of a linear programming formulation that combines an embedding of the graph in a simplex together with spreading metrics and additional constraints that strengthen the formulation. Our randomized rounding technique uses both a randomized metric decomposition technique and a randomized label assignment technique. At the heart of our approach is the fact that only limited dependency is created between the labels assigned to different vertices, allowing us to bound the expected cost of the solution and the number of vertices assigned to each label, simultaneously. We note that the number of vertices assigned to each label is bounded via a new inequality of Janson[15] for tail bounds of (partly) dependent random variables.

In the ASYMMETRIC k -CENTER problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to serve as centers and to assign all the points to the centers, so that the maximum distance of any point from its center is as small as possible.We show that the ASYMMETRIC k -CENTER problem is hard to approximate up to a factor of log * n − O (1) unless NP ⊆ DTIME ( n log log n ). Since an O (log * n )-approximation algorithm is known for this problem, this resolves the asymptotic approximability of ASYMMETRIC k -CENTER. This is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. We also resolve the approximability threshold of the metric (symmetric) k -Center problem with costs.

The problem of scheduling jobs with interval constraints is a well-studied classical scheduling problem. The input to the problem is a collection of n jobs where each job has a set of intervals on which it can be scheduled. The goal is to minimize the total number of machines needed to schedule all jobs subject to these interval constraints. In the continuous version, the allowed intervals associated with a job form a continuous time segment, described by a release date and a deadline. In the discrete version of the problem, the set of allowed intervals for a job is given explicitly. So far, only an O(log n/( log log n))-approximation is known for either version of the problem, obtained by a randomized rounding of a natural linear programming relaxation of the problem. In fact, we show here that this analysis is tight for both versions of the problem by providing a matching lower bound on the integrality gap of the linear program. Moreover, even when all jobs can be scheduled on a single machine, the discrete case has recently been shown to be /spl Omega/(log log n)-hard to approximate. In this paper, we provide improved approximation factors for the number of machines needed to schedule all jobs in the continuous version of the problem. Our main result is an O(1)-approximation algorithm when the optimal number of machines needed is bounded by a fixed constant. Thus, our results separate the approximability of the continuous and the discrete cases of the problem. For general instances, we strengthen the natural linear programming relaxation in a recursive manner by forbidding certain configurations which cannot arise in an integral feasible solution. This yields an O(OPT)-approximation, where OPT denotes the number of machines needed by an optimal solution. Combined with earlier results, our work implies an O(/spl radic/log n/(log log n))-approximation for any value of OPT.

The metric labeling problem is an elegant and powerful mathematical model capturing a wide range of classification problems. The input to the problem consists of a set of labels and a weighted graph. Additionally, a metric distance function on the labels is defined, and for each label and each vertex, an assignment cost is given. The goal is to find a minimum-cost assignment of the vertices to the labels. The cost of the solution consists of two parts: the assignment costs of the vertices and the separation costs of the edges (each edge pays its weight times the distance between the two labels to which its endpoints are assigned). Due to the simple structure and variety of the applications, the problem and its special cases (with various distance functions on the labels) have recently received much attention. Metric labeling has a known logarithmic approximation, and it has been an open question for several years whether a constant approximation exists. We refute this possibility and show that no constant approximation can be obtained for the problem unless P=NP, and we also show that the problem is /spl Omega/(/spl radic/logn)-hard to approximate, unless NP has quasi-polynomial time algorithms.

In the Asymmetric k-Center problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to serve as centers and to assign all the points to the centers, so that the maximum distance of any point to its center is as small as possible. We show that the Asymmetric k-Center problem is hard to approximate up to a factor of log* n - Θ(1) unless NP ⊆ DTIME(nlog log n). Since an O(log* n)-approximation algorithm is known for this problem, this essentially resolves the approximability of this problem. This is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. We also resolve the approximability threshold of the metric k-Center problem with costs.

We study the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. We are given a directed capacitated graph and a set of source-sink pairs. The goal is to route all pairs with minimum congestion on the network edges. A special well-studied case of this problem is the edge-disjoint paths problem, where all edges have unit capacities. The second problem is discrete machine scheduling, where we are given a set of jobs, and for each job a list of intervals in which it can be scheduled. The goal is to find the smallest number of machines on which all jobs can be scheduled, such that no two jobs assigned to the same machine overlap. Both problems are known to be O(log n/log log n)-approximable via the randomized rounding technique of Raghavan and Thompson. However, until recently, only a Max SNP hardness was known for each problem. We make some progress in closing this gap by showing that both problem are Ω(log log n)-hard to approximate unless NP ⊆ DTIME(nO(log log log n)). Our hardness proof for congestion minimization holds even for the special case of the edge-disjoint paths problem.

We consider approximation algorithms for the metric labeling problem. This problem was introduced in a paper by Kleinberg and Tardos [J. ACM, 49 (2002), pp. 616--630] and captures many classification problems that arise in computer vision and related fields. They gave an O(log k log log k) approximation for the general case, where k is the number of labels, and a 2-approximation for the uniform metric case. (In fact, the bound for general metrics can be improved to O(log k) by the work of Fakcheroenphol, Rao, and Talwar [Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 448--455].) Subsequently, Gupta and Tardos [Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 2000, pp. 652--658] gave a 4-approximation for the truncated linear metric, a metric motivated by practical applications to image restoration and visual correspondence. In this paper we introduce an integer programming formulation and show that the integrality gap of its linear relaxation either matches or improves the ratios known for several cases of the metric labeling problem studied until now, providing a unified approach to solving them. In particular, we show that the integrality gap of our linear programming (LP) formulation is bounded by O(log k) for a general k-point metric and 2 for the uniform metric, thus matching the known ratios. We also develop an algorithm based on our LP formulation that achieves a ratio of $2+\sqrt{2}\simeq 3.414$ for the truncated linear metric improving the earlier known ratio of 4. Our algorithm uses the fact that the integrality gap of the LP formulation is 1 on a linear metric.

We consider a network design problem, where applications require various levels of Quality-of-Service (QoS) while connections have limited performance. Suppose that a source needs to send a message to a heterogeneous set of receivers. The objective is to design a low-cost multicast tree from the source that would provide the QoS levels (e.g., bandwidth) requested by the receivers. We assume that the QoS level required on a link is the maximum among the QoS levels of the receivers that are connected to the source through the link. In accordance, we define the cost of a link to be a function of the QoS level that it provides. This definition of cost makes this optimization problem more general than the classical Steiner tree problem. We consider several variants of this problem all of which are proved to be NP-Hard. For the variant where QoS levels of a link can vary arbitrarily and the cost function is linear in its QoS level, we give a heuristic that achieves a multicast tree with cost at most a constant times the cost of an optimal multicast tree. The constant depends on the best constant approximation ratio of the classical Steiner tree problem. For the more general variant, where each link has a given QoS level and cost we present a heuristic that generates a multicast tree with cost O(min{logr,k}) times the cost of an optimal tree, where r denotes the number of receivers, and k denotes the number of different levels of QoS required. We generalize this result to hold for the case of many multicast groups.

A central problem in personal communication systems is to optimize bandwidth usage, while providing Quality of Service (QoS) guarantees to mobile users. Network mobility management, and in particular, location management, consumes a significant portion of bandwidth, which is a necessary overhead for supporting mobile users. We focus our efforts on minimizing this overhead. Unlike previous works, we concentrate on optimizing existing schemes, and so the algorithms we present are easily incorporated into current networks. We present the first polynomial time approximation algorithms for minimum bandwidth location management. In planar graphs, our algorithm provably generates a solution that uses no more than a constant factor more bandwidth than the optimal solution. In general graphs, our algorithm provably generates a solution that uses just a factor O(logn) more bandwidth than optimal where n is the number of base stations in the network. We show that, in practice, our algorithm produces near-optimal results and outperforms other schemes that are described in the literature. For the important case of the line graph, we present a polynomial-time optimal algorithm. Finally, we illustrate that our algorithm can also be used for optimizing the handoff mechanism.

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.

We consider the classical vertex cover and set cover problems with the addition of hard capacity constraints. This means that a set (vertex) can only cover a limited number of its elements (adjacent edges) and the number of available copies of each set (vertex) is bounded. This is a natural generalization of the classical problems that also captures resource limitations in practical scenarios. We obtain the following results. For the unweighted vertex cover problem with hard capacities we give a 3-approximation algorithm which is based on randomized rounding with alterations. We prove that the weighted version is at least as hard as the set cover problem. This is an interesting separation between the approximability of weighted and unweighted versions of a "natural" graph problem. A logarithmic approximation factor for both the set cover and the weighted vertex cover problem with hard capacities follows from the work of Wolsey (1982) on submodular set cover. We provide in this paper a simple and intuitive proof for this bound.

This paper presents a comprehensive study of the effect of job interleaving by preemption on the throughput of a single server where requests arrive with a given processing time and slack. The problem is to decide which requests to serve so as to maximize the server's utilization. This simple model captures many situations, both at the application (e.g., delivery of video) as well as at the network/transmission levels (e.g., scheduling of packets from input to output interface of a switch). The problem is on-line in nature, and thus we use competitive analysis for measuring the performance of our scheduling algorithms. We consider two modes of operation - with and without commitment - and derive upper and lower bounds for each case. Since competitive analysis is based on the worst-case scenario, the average-case performance of the algorithms is also examined by a simulation study.

This paper considers the design of handoff rerouting algorithms for reducing the overall session cost in personal communication systems (PCS). Most modern communication systems that are used as an infrastructure for PCS networks are based on connection-based technologies. In these systems, the session cost is composed of two components. The setup cost represents the cost associated with the handoff operations, and the hold cost determines the expense related to the use of network resources held by the connection. This work introduces for the first time, rerouting algorithms for general graphs which are cost effective in terms of their worst-case analysis. The algorithms are analyzed using a competitive analysis approach, and it is proved that the competitive ratio of the proposed algorithms is a small constant of which the precise value depends on the ratio between the setup costs and the hold costs of the links. We also prove a lower bound of 2 on the competitive ratio of any online algorithm, which means that the proposed algorithms are close in terms of worst case behavior to the best possible rerouting algorithm. In addition, experimental results also show that the proposed algorithms indeed balance between the session setup cost and the hold cost, yielding overall lower cost when compared to other algorithms described in the literature.

We present a general framework for solving resource allocation and scheduling problems. Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor. Our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines, (ii) bandwidth allocation for sessions between two endpoints, (iii) general caching, (iv) dynamic storage allocation, and (v) bandwidth allocation on optical line and ring topologies. For some of these problems we provide the first constant factor approximation algorithm. Our algorithms are simple and efficient and are based on the local-ratio technique. We note that they can equivalently be interpreted within the primal-dual schema.

In a hierarchical server environment jobs are to be assigned in an on-line fashion to a collection of servers which form a hierarchy of capability: each job requests a specific server meeting its needs, but the system is free to assign it either to that server or to any other server higher in the hierarchy. Each job carries a certain load, which it imparts to the server it is assigned to. The goal is to find a competitive assignment in which the maximum total load on a server is minimized. We consider the linear hierarchy in which the servers are totally ordered in terms of their capabilities. We investigate several variants of the problem. In the unweighted (as opposed to weighted) problem all jobs have unit weight. In the fractional (as opposed to integral) model a job may be assigned to several servers, each receiving some fraction of its weight. Finally, temporary (as opposed to permanent) jobs may depart after being active for some finite duration of time. We show an optimal e-competitive algorithm for the unweighted integral permanent model. The same algorithm is (e+1)-competitive in the weighted case. Its fractional version is e-competitive even if temporary jobs are allowed. For the integral model with temporary jobs we show an algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case. We show a lower bound of e for the unweighted case (both integral and fractional). This bound is valid even with respect to randomized algorithms. We also show a lower bound of 3 for the unweighted integral model when temporary jobs are allowed. We generalize the problem and consider hierarchies in which the servers form a tree. In the tree hierarchy, any job assignable to a node is also assignable to the node's ancestors. We show a deterministic algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case, where only permanent jobs are allowed. Randomizing this algorithm improves its competitiveness to e and e+1, respectively. We also show an $\Omega(\sqrt{n})$ lower bound when temporary jobs are allowed.

We consider the following fundamental scheduling problem. The input to the problem consists of n jobs and k machines. Each of the jobs is associated with a release time, a deadline, a weight, and a processing time on each of the machines. The goal is to find a nonpreemptive schedule that maximizes the weight of jobs that meet their respective deadlines. We give constant factor approximation algorithms for four variants of the problem, depending on the type of the machines (identical vs. unrelated) and the weight of the jobs (identical vs. arbitrary). All these variants are known to be NP-hard, and the two variants involving unrelated machines are also MAX-SNP hard. The specific results obtained are as follows: For identical job weights and unrelated machines: a greedy 2-approximation algorithm. For identical job weights and k identical machines: the same greedy algorithm achieves a tight $\frac{(1+1/k)^k}{(1+1/k)^k-1}$ approximation factor. For arbitrary job weights and a single machine: an LP formulation achieves a 2-approximation for polynomially bounded integral input and a 3-approximation for arbitrary input. For unrelated machines, the factors are 3 and 4, respectively. For arbitrary job weights and k identical machines: the LP-based algorithm applied repeatedly achieves a $\frac{(1+1/k)^k}{(1+1/k)^k-1}$ approximation factor for polynomially bounded integral input and a $\frac{(1+1/2k)^k}{(1+1/2k)^k-1}$ approximation factor for arbitrary input. For arbitrary job weights and unrelated machines: a combinatorial $(3+2\sqrt{2} \approx 5.828)$-approximation algorithm.

A directed multiway cut separates a set of terminals T={s 1 , . . . , s k } in a directed capacitated graph G=(V,E). Finding a minimum directed multiway cut is an NP-hard problem. We give a polynomial-time algorithm that achieves an approximation factor of 2 for this problem. This improves the result of Garg, Vazirani, and Yannakakis [Proceedings of the 21st International Colloquium on Automata, Languages, and Programming, Jerusalem, Israel, 1994, pp. 487--498], who gave an algorithm that achieves an approximation factor of 2 log k. Our approximation algorithm uses a novel technique for relaxing a multiway flow function in order to find a directed multiway cut. It also implies that the integrality gap of the linear program for the directed multiway cut problem is at most 2.

This paper considers the design of handoff rerouting algorithms for reducing the overall session cost in personal communication systems (PCS). Most modern communication systems that are used as an infrastructure for PCS networks are based on connection-based technologies. In these systems the session cost is composed of two components. The setup cost represents the cost associated with the handoff operations and the hold cost determines the expense related to the use of network resources held by the connection. Using an efficient handoff rerouting algorithm is important for the efficient management of PCS networks. This work introduces for the first time rerouting algorithms for general graphs which are cost-effective in terms of their worst-case analysis. The algorithms are analyzed using a competitive analysis approach and it is proved that the competitive ratio of the proposed algorithms is a small constant whose precise value depends on the ratio between the setup costs and the hold costs of the links. We also prove that the competitive ratio of the best online algorithm is at least 2, which means that the proposed algorithms are close in terms of worst-case behavior to the best possible rerouting algorithm. In addition, experimental results also show that the proposed algorithms indeed balance between the session setup cost and the hold cost, yielding overall lower cost when compared to other algorithms described in the literature.

We consider a network design problem, where applications require various levels of quality-of-service (QoS) while connections have limited performance. Suppose that a source needs to send a message to a heterogeneous set of receivers. The objective is to design a low cost multicast tree from the source that would provide the QoS levels (e.g., bandwidth) requested by the receivers. We assume that the QoS level required on a link is the maximum among the QoS levels of the receivers that are connected to the source through the link. In accordance, we define the cost of a link to be a function of the QoS level that it provides. This definition of cost makes this optimization problem more general than the classical Steiner tree problem. We consider several variants of this problem all of which are proved to be NP-hard. For the variant where QoS levels of a link can vary arbitrarily and the cost function is linear in its QoS level, we give a heuristic that achieves a multicast tree with cost at most a constant times the cost of an optimal multicast tree. The constant depends on the best constant approximation ratio of the classical Steiner tree problem. For the more general variant, where each link has a given QoS level and cost we present a heuristic that generates a multicast tree with cost O(min{logr,k}) times the cost of an optimal tree, where r denotes the number of receivers, and k denotes the number of different levels of QoS required. We generalize this result to hold for the case of many multicast groups.

In a satellite and wireless networks and in advanced traffic information systems in which the up-link bandwidth is very limited, a server broadcasts data files in a round-robin manner. The data files are provided by different providers and are accessed by many clients. The providers are independent and therefore files may share information. The clients who access these files may have different patterns of access. Some clients may wish to access more than one file at a time in any order, some clients may access one file out of of several files, and some clients may wish to access a second file only after accessing another file. The goal of the server is to order the files in a way that minimizes the access time of the clients given some a-priori knowledge of their access patterns. This paper introduces a clients-providers-servers model that represents certain environments better than the traditional clients-servers model. Then, we show that a random order of the data files performs well independent of the specific access pattern. Our main technical contribution is showing how to de-randomize the randomized algorithm that is based on selecting a random order. The resulting algorithm is a polynomial time deterministic algorithm that finds an order that achieves the bounds of the random order.

We present a general framework for solving resource allocation and scheduling problems.Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor.Our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines; (ii) bandwidth allocation for sessions between two endpoints; (iii) general caching; (iv) dynamic storage allocation; (v) bandwidth allocation on optical line and ring topologies.For some of these problems we provide the first constant factor approximation algorithm.Our algorithms are simple and efficient.They use the local-ratio technique and can be equivalently interpreted within the primal-dual schema.

We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns lengths to either edges or vertices of the input graph, such that all subgraphs for which the optimization problem is nontrivial have large diameters. In addition, the spreading metric provides a lower bound, τ, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modeled by our paradigm whose approximation factor is O (min{log τ, log log τ, log k log log k }) where k denotes the number of “interesting” vertices in the problem instance, and is at most the number of vertices. We present seven problems that can be formulated to fit the paradigm. For all these problems our algorithm improves previous results. The problems are: (1) linear arrangement; (2) embedding a graph in a d -dimensional mesh; (3) interval graph completion; (4) minimizing storage-time product; (5) subset feedback sets in directed graphs and multicuts in circular networks; (6) symmetric multicuts in directed networks; (7) balanced partitions and p -separators (for small values of p ) in directed graphs.

In heterogeneous networks, sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well-studied telephone model is obtained when all link delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the nodes of size k. The problem is NP-hard even in the basic telephone model. We present a polynomial-time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the telephone model by a factor of $O(\frac{\log n}{\log\log k})$. No approximation algorithms were known for the general model considered in this paper.

We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set (or subset-fvs, in short). The input in this problem consists of an undirected graph G=(V,E) with vertex weights c(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset-fvs with respect to S if it intersects every interesting cycle. The goal is to find a minimum weight subset-fvs. The best previous algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset-fvs problem generalizes two NP-complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multicommodity flow, which we call relaxed multicommodity flow. Relaxed multicommodity flow is a hybrid of multicommodity flow and multiterminal flow.

Let G=(V,E) be a weighted undirected graph where all weights are at least one. We consider the following generalization of feedback set problems. Let $S \subset V$ be a subset of the vertices. A cycle is called interesting if it intersects the set S. A subset feedback edge (vertex) set is a subset of the edges (vertices) that intersects all interesting cycles. In minimum subset feedback problems the goal is to find such sets of minimum weight. This problem has a variety of applications, among them genetic linkage analysis and circuit testing. The case in which S consists of a single vertex is equivalent to the multiway cut problem, in which the goal is to separate a given set of terminals. Hence, the subset feedback problem is NP-complete and also generalizes the multiway cut problem. We provide a polynomial time algorithm for approximating the subset feedback edge set problem that achieves an approximation factor of two. This implies a $\Delta$-approximation algorithm for the subset feedback vertex set problem, where $\Delta$ is the maximum degree in G. We also consider the multicut problem and show how to achieve an $O(\log \tau^*)$ approximation factor for this problem, where $\tau^*$ is the value of the optimal fractional solution. To achieve the $O(\log \tau^*)$ factor we employ a bootstrapping technique.

We consider the following fundamental scheduling problem.The input to the problem consists of n jobs and k machines.Each of the jobs is associated with a release time, a deadline, a weight, and a processing time on each of the machines.The goal is to find a schedule that maximizes the weight ofjobs that meet their deadline.We give constant factor approximation algorithms for four variants of the problem, depending on the type of the machines (identical vs. unrelated), and the weight of the jobs (identical vs. arbitrary).All these variants are known to be NP-Hard, and we observe that the two variants involving unrelated machines are also MAX-SNP hard.To the best of our knowledge, these are the first approximation algorithms for such problems in the non-preemptive off-line setting.1 Introduction Wcconsiderthefollowing fundamentalschedulingprohlem.The input lo the problem consists of n jobs and k machines.Each of the jobs is associated with a release time, a deadline, a weight, and a processing time on each of the machines.The goal is to find a schedulethat maximizes the weight of the jobs that meet theirdead-*Part of this work was done while the first three authors visited IBM T.I.

Article Efficient recovery from power outage (extended abstract) Share on Authors: Sudipto Guha Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile , Anna Moss Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile , Joseph (Seffi) Naor Bell Laboratories, Lucent Technologies, 600 Mountain Ave., Murray Hill, NJ Bell Laboratories, Lucent Technologies, 600 Mountain Ave., Murray Hill, NJView Profile , Baruch Schieber IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NYView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 574–582https://doi.org/10.1145/301250.301406Online:01 May 1999Publication History 27citation742DownloadsMetricsTotal Citations27Total Downloads742Last 12 Months39Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We study graph partitioning problems on graphs with edge capacities and vertex weights. The problems of b-balanced cuts and k-balanced partitions are unified into a new problem called minimum capacity $\rho$-separators. A $\rho$-separator is a subset of edges whose removal partitions the vertex set into connected components such that the sum of the vertex weights in each component is at most $\rho$ times the weight of the graph. We present a new and simple O(log n)-approximation algorithm for minimum capacity $\rho$-separators which is based on spreading metrics yielding an O(log n)-approximation algorithm both for b-balanced cuts and k-balanced partitions. In particular, this result improves the previous best known approximation factor for k-balanced partitions in undirected graphs by a factor of O(log k). We enhancethese results by presenting a version of the algorithm that obtains an O(log OPT)-approximation factor. The algorithm is based on a technique called spreading metrics that enables us to formulate directly the minimum capacity $\rho$-separator problem as an integer program. We also introduce a generalization called the simultaneous separator problem, where the goal is to find a minimum capacity subset of edges that separates a given collection of subsets simultaneously. We extend our results to directed graphs for values of $\rho \geq 1/2$. We conclude with an efficient algorithm for computing an optimal spreading metric for $\rho$-separators. This yields more efficient algorithms for computing b-balanced cuts than were previously known.

In heterogeneous networks sending messages may incur different delays on different edges, and each processor may have a different switching time between messages.The well studied Telephone model is obtained when all edge delays and switching times are equal to one unit.We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the processors of size k.The problem is NP-hard even in the basic Telephone model.We present a polynomial time algorithm that approximates the minimum multicast time within a factor of O(log k).Our algorithm improves on the best known approximation factor for the Telephone model by a factor of 0 (e).No approximation algorithms were known for the general model considered in this paper. IntroductionThe task of disseminating a message from a source node to the rest of the nodes in a communication network is called bruudcczsting.The goal is to completethetask as fast as possible assuming all nodes in the network participate in the effort.When the message needs to be disseminated only to a subset of the nodes this task is referred to as mulricarring.Broadcasting and multicasting are important and basic communication primitives in many multiprocessor systems.Current networks usually provide point-to-point communication only between some of the pairs of the nodes in the network.Yet,

A feedback vertex set of an undirected graph is a subset of vertices that intersects with the vertex set of each cycle in the graph. Given an undirected graph G with n vertices and weights on its vertices, polynomial-time algorithms are provided for approximating the problem of finding a feedback vertex set of G with smallest weight. When the weights of all vertices in G are equal, the performance ratio attained by these algorithms is 4-(2/n). This improves a previous algorithm which achieved an approximation factor of $O(\sqrt{\log n})$ for this case. For general vertex weights, the performance ratio becomes $\min\{2\Delta^2, 4 \log_2 n\}$ where $\Delta$ denotes the maximum degree in G. For the special case of planar graphs this ratio is reduced to 10. An interesting special case of weighted graphs where a performance ratio of 4-(2/n) is achieved is the one where a prescribed subset of the vertices, so-called blackout vertices, is not allowed to participate in any feedback vertex set. It is shown how these algorithms can improve the search performance for constraint satisfaction problems. An application in the area of Bayesian inference of graphs with blackout vertices is also presented.

We consider the bicriteria optimization problem of computing a shallow-light tree. Given a directed graph with two unrelated cost functions defined on its edges: weight and length, and a designated root vertex, the goal is to find a minimum weight spanning tree such that the path lengths from its root to the rest of the vertices are bounded. This problem has several applications in network and VLSI design, and information retrieval. We give a polynomial time algorithm for finding a spanning tree whose weight is O(log |V|) times the weight of an optimal shallow-light tree, where the path lengths from the root to the rest of the vertices are at most twice the given bounds. We extend our technique to handle two variants of the problem: one in which the length bound is given on the average length of a path from the root to a vertex, and another tricriteria budgeted version. Our paper provides the first non-trivial approximation factors for directed graphs, and improves on previous results for undirected graphs.

A directed multiway cut separates a set of terminals s/sub 1/,...,s/sub /spl kappa// in a directed capacitated graph G=(V, E). Finding a minimum capacity directed multiway cut is an NP-complete problem. We give a polynomial-time algorithm that achieves an approximation factor of 2 for this problem. This improves the result of Garg, Vazirani and Yannakakis (1994) who gave an algorithm that achieves an approximation factor of 2 log /spl kappa/. Our approximation algorithm uses a novel technique for relaxing a multiway flow function in order to find a directed multiway cut. It also implies that the integrality gap of the linear program for the directed multiway cut problem is at most 2.

We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set. The input in this problem consists of an undirected graph G=(V,E) with vertex weights w(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset feedback vertex set with respect to S if it intersects every interesting cycle The goal is to find a minimum weight subset feedback vertex set. The best pervious algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset feedback vertex set problem generalizes two NP-Complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multi-commodity flow which we call relaxed multi-commodity flow. Relaxed multi-commodity flow is a hybrid of multi-commodity flow and multi-terminal flow.

This paper is concerned with on-line storage allocation to processes in a dynamic environment. This problem has been extensively studied in the past. We provide a new, tighter bound for the competitive ratio of the well-known First Fit algorithm. This bound is obtained by considering a new parameter, namely the maximum number of concurrent active processes. We observe that this bound is also a lower bound on the competitive ratio of any deterministic on-line algorithm. Our second contribution is an on-line allocation algorithm that uses coloring techniques. We show that the competitive ratio of this algorithm is the same as that of First Fit. Furthermore, we indicate that this algorithm may be advantageous in certain applications. Our third contribution is to analyze the performance of randomized algorithms for this problem. We obtain lower bounds on the competitive ratio that are close to the best deterministic upper bounds.

Modern fast packet switching networks are being forced to rethink the routing schemes that are used in more traditional networks. The reexamination is necessitated because in these fast networks switches on the message's route can afford to make only minimal and simple operations. For example, examining a table of a size proportional to the network size is out of the question. We examine routing strategies for such networks based on flooding and predefined routes. Our concern is to get both efficient routing and an even (balanced) use of network resources. We present efficient algorithms for assigning weights to edges in a controlled flooding scheme but show that the flooding scheme is not likely to yield a balanced use of the resources. We then present efficient algorithms for choosing routes along: bfs trees and shortest paths. We show that in both cases a balanced use of network resources can be guaranteed.

In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the machines. Each machine has a loading time that is incurred only for the first task that is scheduled on the machine in a particular run. This basic scheduling problem arises in the context of machining on numerically controlled machines, query optimization in databases, and in other artificial intelligence applications. We give the first non-trivial approximation algorithm for this problem. We also prove non-trivial lower bounds on best possible approximation ratios for these problems. These improve on the non-approximability results that are implied by the non-approximability results for the shortest common supersequence problem. We use the same algorithmic technique to obtain approximation algorithms for a problem arising in the context of code generation for parallel machines, and for the weighted shortest common supersequence problem.

We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns fractional lengths to either edges or vertices of the input graph, such that all subgraphs on which the optimisation problem is non-trivial have large diameters. In addition, the spreading metric provides a lower bound, /spl tau/, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modelled by our paradigm whose approximation factor is O (mi.

The problem of maximum flow in planar graphs has always been investigated under the assumption that there is only one source and one sink. Here we consider the case where there are many sources and sinks (single commodity) in a directed planar graph. An algorithm for the case when the demands of the sources and sinks are fixed and given in advance is presented. The algorithm can be implemented efficiently sequentially and in parallel, and its complexity is dominated by the complexity of computing all shortest paths from a single source in a planar graph. If the demands are not known, an algorithm for computing the maximum flow is presented for the case where the number of faces that contain sources and sinks is bounded by a slowly growing function, Our result places the problem of computing a perfect matching in a planar bipartite graph in NC and improves a previous parallel algorithm for the case of a single source, single sink in a planar directed (and undirected) graph, both in terms of processor bounds and its simple presentation.

The authors present an $O(mn^2 \log m)$ algorithm for solving feasibility in linear programs with up to two variables per inequality which is derived directly from the Fourier–Motzkin elimination method. (The number of variables and inequalities are denoted by n and m, respectively.) The running time of the algorithm dominates that of the best known algorithm for the problem, and is far simpler. Integer programming on monotone inequalities, i.e., inequalities where the coefficients are of opposite sign, is then considered. This problem includes as a special case the simultaneous approximation of a rational vector with specified accuracy, which is known to be NP-complete. However, it is shown that both a feasible solution and an optimal solution with respect to an arbitrary objective function can be computed in pseudo-polynomial time.

It is shown how to efficiently construct a small probability space on n binary random variables such that for every subset, its parity is either zero or one with “almost” equal probability. They are called $\epsilon $-biased random variables. The number of random bits needed to generate the random variables is $O(\log n + \log \frac{1}{\epsilon })$. Thus, if $\epsilon $ is polynomially small, then the size of the sample space is also polynomial. Random variables that are $\epsilon $-biased can be used to construct “almost” k-wise independent random variables where $\epsilon $ is a function of k. These probability spaces have various applications: l. Derandomization of algorithms: Many randomized algorithms that require only k-wise independence of their random bits (where k is bounded by $O(\log n)$), can be derandomized by using $\epsilon $-biased random variables. 2. Reducing the number of random bits required by certain randomized algorithms, e.g., verification of matrix multiplication. 3. Exhaustive testing of combinatorial circuits. The smallest known family for such testing is provided. 4. Communication complexity: Two parties can verify equality of strings with high probability exchanging only a logarithmic number of bits. 5. Hash functions: A polynomial sized family of hash functions such that with high probability the sum of a random function over two different sets is not equal can be constructed.

Flow in planar graphs has been extensively studied, and very efficient algorithms have been developed to compute max-flows, min-cuts, and circulations. Intimate connections between solutions to the planar circulation problem and with “consistent” potential functions in the dual graph are shown. It is also shown that the set of integral circulations in a planar graph very naturally forms a distributive lattice whose maximum corresponds to the shortest path tree in the dual graph. Further characterized is the lattice in terms of unidirectional cycles with respect to a particular face called the root face. It is shown how to compactly encode the entire lattice and it is also shown that the set of solutions to the min-cost flow problem forms a sublattice in the presented lattice.

The authors examine routing strategies for fast packet switching networks based on flooding and predefined routes. The concern is to get both efficient routing and an even balanced use of network resources. They present efficient algorithms for assigning weights to edges in a controlled flooding scheme but show that the flooding scheme is not likely to yield a balanced use of the resources. Efficient algorithms are presented for choosing routes along breadth-first search trees and shortest paths. It is shown that in both cases a balanced use of network resources can be guaranteed.>

The set maxima problem is as follows: given a family of subsets $\mathcal{S}$ of a totally ordered set $X = \{ x_1 , \cdots ,x_n \}$, find the maximum in each subset. The computational model is the comparison tree. One possible solution is to sort the set X, which requires $O( n \log n )$ comparisons. The open question is whether set maxima is easier than sorting. Here, a solution is presented that requires a linear number of comparisons for the following two cases: • The sets are hyperplanes in a d-dimensional projective geometry $PG ( d,q )$. In particular, the interesting case is $PG ( 2,q )$, when the intersection of any two subsets is exactly one. • The sets are chosen randomly with probability $p ( n )$ for each element to be in a set. The random choices are mutually independent and the number of comparisons needed is linear with probability approaching 1 asymptotically.

A novel technique, based on the pseudo-random properties of certain graphs known as expanders, is used to obtain novel simple explicit constructions of asymptotically good codes. In one of the constructions, the expanders are used to enhance Justesen codes by replicating, shuffling, and then regrouping the code coordinates. For any fixed (small) rate, and for a sufficiently large alphabet, the codes thus obtained lie above the Zyablov bound. Using these codes as outer codes in a concatenated scheme, a second asymptotic good construction is obtained which applies to small alphabets (say, GF(2)) as well. Although these concatenated codes lie below the Zyablov bound, they are still superior to previously known explicit constructions in the zero-rate neighborhood.

We show how to efficiently construct a small probability space on n binary random variables such that for every subset, its parity is either zero or one with "almost" equal probability.They are called e-biased random variables.The number of random bits needed to generate the random variables is O(logn ÷ log ~).Thus, if e is polynomially small, then the size of the sample space is also polynomial.e-biased random variables can be used to construct "almost" k-wise independent random variables where e is a function of k.Applications are shown to derandomization of algorithms, reducing the number of random bits required by certain randomized algorithms, exhaustive testing of combinatorial circuits, communication complexity and construction of hash functions.

A general method is presented for translating sorting by comparisons algorithms to algorithms that compute a Hamilton path in a tournament. The translation is based on the relation between minimal feedback sets and Hamilton paths in tournaments. It is proven that there is a one to one correspondence between the set of minimal feedback sets and the set of Hamilton paths. In the comparison model, all the tradeoffs for sorting between the number of processors and the number of rounds hold as well for computing Hamilton paths. For the CRCW model, with $O( n )$ processors, we show the following: (i) Two paths in a tournament can be merged in $O(\log \log n)$ time (Valiant’s algorithm [SIAM J. Comput., 4 (1975), pp. 348–355], (ii) a Hamilton path can be computed in $O(\log n)$ time (Cole’s algorithm). This improves a previous algorithm for computing a Hamilton path whose running time was $O(\log^2 n)$ using $O(n^2 )$ processors.

Given a planar network with many sources and sinks, the problem of computing the maximum flow from the sources to the sinks is investigated. An algorithm that runs in O(log/sup 2/n) time using O(n/sup 1.5/) processors on an exclusive-read-exclusive-write parallel random-access machine (EREW PRAM) is obtained, when the amount of flow (demand) at each source and sink is assumed as input. When the demands are unknown, the problem remains open. However, in the special case in which the sources and sinks are all on one face (and the demands unknown), an algorithm that computes the maximum flow with time complexity O(log/sup 3/n log log n) using O(n/sup 1.5/) processors is given. The results also hold for more general networks, namely, when the edge capacities have both lower and upper bounds.>

A method is provided for converting randomized parallel algorithms into deterministic parallel algorithms. The approach is based on a parallel implementation of the method of conditional probabilities. Results obtained by applying the method to the set balancing problem, lattice approximation, edge-coloring graphs, random sampling, and combinatorial constructions are presented. The general form in which the method of conditional probabilities is applied sequentially is described. The reason why this form does not lend itself to parallelization are discussed. The general form of the case for which the method of conditional probabilities can be applied in the parallel context is given.>

Let. o~(G) denote the independence numbe>~f a graph G, that is the ma.xinmrn number of pairwise independent vertices in G.We present a parallel algorithm that computes in a planar graph G-= (V, E), an independent set I C V such that III >_ a(G)/2.The algorithm runs in time O(log 2 n) and requires a linear number of processors.This is achieved by defining a set. of reductions that can be executed "locally" and simultaneously; fllrtherrnore, it is shown that a constant fraction of the vertices in the graph are reducible.This is the best known approximation scheme when the number of processors available is linear; parallel implementation of known sequential algorithms requires many more processors.

Techniques for parallel algorithms on chordal graphs are developed. An NC algorithm for recognizing chordal graphs is developed, as are NC algorithms for finding the following objects in chordal graphs: all maximal cliques, an intersection graph representation, an optimal coloring, a perfect elimination scheme, a weighted maximum independent set, and a minimum clique cover. The recognition algorithm presented in this paper is simpler than previous algorithms given by Edenbrandt and by Chandrasekharan and Iyengar; the other problems were apparently open. The known polynomial-time algorithms for these problems seem highly sequential, and therefore a different approach to find parallel algorithms is used.

Many algorithms in distributed systems assume that the size of a single message depends on the number of processors.In this paper, we assume that messages consist of only one bit.Our main goal is to explore how the onebit translation of unbounded message algorithms can be sped up by pipelining.We consider three problems.The first is routing between two processors in an arbitrary network and in some special networks (ring, grid, hypercube).The second problem is coloring a synchronous ring with three colors, and the third is counting the number of processors in a synchronous network where each processor knows only its neighbors.The routing problem is a very basic subroutine in many distributed al-

We present an NC algorithm for recognizing chordal graphs, and we present NC algorithms for finding the following objects on chordal graphs: all maximal cliques, an intersection graph representation, an optimal coloring, a perfect elimination scheme, a maximum independent set, a minimum clique cover, and the chromatic polynomial. The well known polynomial algorithms for these problems seem highly sequential, and therefore a different approach is needed to find parallel algorithms.

Textures are classified based on the change in their properties with changing resolution. The area of the gray level surface is measured at serveral resolutions. This area decreases at coarser resolutions since fine details that contribute to the area disappear. Fractal properties of the picture are computed from the rate of this decrease in area, and are used for texture comparison and classification. The relation of a texture picture to its negative, and directional properties, are also discussed.