We consider algorithms for “smoothed online convex optimization” problems, a variant of the class of online convex optimization problems that is strongly related to metrical task systems. Prior literature on these problems has focused on two performance metrics: regret and the competitive ratio. There exist known algorithms with sublinear regret and known algorithms with constant competitive ratios; however, no known algorithm achieves both simultaneously. We show that this is due to a fundamental incompatibility between these two metrics - no algorithm (deterministic or randomized) can achieve sublinear regret and a constant competitive ratio, even in the case when the objective functions are linear. However, we also exhibit an algorithm that, for the important special case of one dimensional decision spaces, provides sublinear regret while maintaining a competitive ratio that grows arbitrarily slowly.

No abstract available.

Clustering is a popular problem with many applications. We consider the k-means problem in the situation where the data is too large to be stored in main memory and must be accessed sequentially, such as from a disk, and where we must use as little memory as possible. Our algorithm is based on recent theoretical results, with significant improvements to make it practical. Our approach greatly simpli(cid:173) fies a recently developed algorithm, both in design and in analysis, and eliminates large constant factors in the approximation guarantee, the memory requirements, and the running time. We then incorporate approximate nearest neighbor search to compute k-means in o(nk) (where n is the number of data points; note that com(cid:173) puting the cost, given a solution, takes 8(nk) time). We show that our algorithm compares favorably to existing algorithms - both theoretically and experimentally, thus providing state-of-the-art performance in both theory and practice.

One of the central problems in data-analysis is k-means clustering. In recent years, considerable attention in the literature addressed the streaming variant of this problem, culminating in a series of results (Har-Peled and Mazumdar; Frahling and Sohler; Frahling, Monemizadeh, and Sohler; Chen) that produced a (1 + ε)-approximation for k-means clustering in the streaming setting. Unfortunately, since optimizing the k-means objective is Max-SNP hard, all algorithms that achieve a (1 + ε)-approximation must take time exponential in k unless P=NP. Thus, to avoid exponential dependence on k, some additional assumptions must be made to guarantee high quality approximation and polynomial running time. A recent paper of Ostrovsky, Rabani, Schulman, and Swamy (FOCS 2006) introduced the very natural assumption of data separability: the assumption closely reflects how k-means is used in practice and allowed the authors to create a high-quality approximation for k-means clustering in the non-streaming setting with polynomial running time even for large values of k. Their work left open a natural and important question: are similar results possible in a streaming setting? This is the question we answer in this paper, albeit using substantially different techniques. We show a near-optimal streaming approximation algorithm for k-means in high-dimensional Euclidean space with sublinear memory and a single pass, under the same data separability assumption. Our algorithm offers significant improvements in both space and running time over previous work while yielding asymptotically best-possible performance (assuming that the running time must be fully polynomial and P ≠ NP). The novel techniques we develop along the way imply a number of additional results: we provide a high-probability performance guarantee for online facility location (in contrast, Meyerson's FOCS 2001 algorithm gave bounds only in expectation); we develop a constant approximation method for the general class of semi-metric clustering problems; we improve (even without σ-separability) by a logarithmic factor space requirements for streaming constant-approximation for k-median; finally we design a “re-sampling method” in a streaming setting to convert any constant approximation for clustering to a [1 + O(σ2)]-approximation for σ-separable data.

With the power consumption issue of mobile handset taken into account, single-carrier FDMA (SC-FDMA) has been selected for 3GPP long-term evolution (LTE) uplink multiple access scheme. Like in OFDMA downlink, it enables multiple users to be served simultaneously in uplink as well. However, its single carrier property requires that all the subcarriers allocated to a single user must be contiguous in frequency within each time slot. This contiguous allocation constraint limits the scheduling flexibility, and frequency-domain packet scheduling algorithms in such system need to incorporate this constraint while trying to maximize their own scheduling objectives. In this paper we explore this fundamental problem of LTE SC-FDMA uplink scheduling by adopting the conventional time-domain proportional fair algorithm to maximize its objective (i.e. proportional fair criteria) in the frequency-domain setting. We show the NP-hardness of the frequency-domain scheduling problem under this contiguous allocation constraint and present a set of practical algorithms fine tuned to this problem. We demonstrate that competitive performance can be achieved in terms of system throughput as well as fairness perspective, which is evaluated using 3GPP LTE system model simulations.

We study the relationship between the social cost of correlated equilibria and the social cost of Nash equilibria. In contrast to previous work focusing on the possible benefits of a benevolent mediator, we define and bound the Price of Mediation (PoM): the ratio of the cost of the worst correlated equilibrium to the cost of the worst Nash. We observe that in practice, the heuristics used for mediation are frequently non-optimal, and from an economic perspective mediators may be inept or self-interested. Recent results on computation of equilibria also motivate our work.

We present the first constant approximation to the single sink buy-at-bulk network design problem, where we have to design a network by buying pipes of different costs and capacities per unit length to route demands at a set of sources to a single sink. The distances in the underlying network form a metric. This result improves the previous bound of $O(\log|R|)$, where R is the set of sources. We also present a better constant approximation to the related Access Network Design problem. Our algorithms are randomized and combinatorial. As a subroutine in our algorithm, we use an interesting variant of facility location with lower bounds on the amount of demand an open facility needs to serve. We call this variant load balanced facility location and present a constant factor approximation for it, while relaxing the lower bounds by a constant factor.

We consider the problem of simultaneous source location: selecting locations for sources in a capacitated graph such that a given set of demands can be satisfied simultaneously, with the goal of minimizing the number of locations chosen. For general directed and undirected graphs we give an O (log D )-approximation algorithm, where D is the sum of demands, and prove matching Ω(log D ) hardness results assuming P ≠ NP . For undirected trees, we give an exact algorithm and show how this can be combined with a result of Räcke to give a solution that exceeds edge capacities by at most O (log 2 n log log n ), where n is the number of nodes. For undirected graphs of bounded treewidth we show that the problem is still NP -hard, but we are able to give a PTAS with at most (1 + ϵ) violation of the capacities for arbitrarily small ϵ, or a ( k +1) approximation with exact capacities, where k is the treewidth.

We design a randomized online algorithm for k-server on binary trees with hierarchical edge lengths, with expected competitive ratio O(log Delta), where Delta is the diameter of the metric. This is one of the first k-server algorithms with competitive ratio poly-logarithmic in the natural problem parameters, and represents substantial progress on the randomized k-server conjecture. Extending the algorithm to trees of higher degree would give a competitive ratio of O(log2 Delta log n) for the k-server problem on general metrics with n points and diameter Delta.

We present the Cost-Distance problem: finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the first known $O(\log k)$ randomized approximation scheme for Cost-Distance, where k is the number of sources. We reduce several common network design problems to Cost-Distance, obtaining (in some cases) the first known logarithmic approximation for them. These problems include single-sink buy-at-bulk with variable pipe types between different sets of nodes, facility location with buy-at-bulk–type costs on edges (integrated logistics), constructing single-source multicast trees with good cost and delay properties, priority Steiner trees, and multilevel facility location. Our algorithm is also easier to implement and significantly faster than previously known algorithms for buy-at-bulk design problems.

In this paper, we examine a duopolistic market where the two firms compete to sell a system of components. Components are digital (firms haveunlimited supply at no marginal cost), and customers are homogeneous in their component preferences. Each customer will assemble a utility maximizing system by purchasing each necessary component from one of the two firms. While components from the same firm are always compatible, pairwise compatibility of components from rival firms may vary; in addition to utility due to the quality of the system purchased, customers have negative utility for purchasing incompatible parts. We investigate algorithms and hardness results for profit-maximizing decisions of the firms with regards to their price-setting, component value-enhancing and compatibility-enabling strategies. The users' behavior can be modeled as a minimum cut computation, and the company's strategies require addressing novel and interesting questions about graph cuts and flows. We develop a polynomial-time algorithm for finding profit-maximizing prices if the qualities and compatibilities are fixed. On the other hand, we show that finding profit-maximizing quality improvements is equivalent to the Maximum Size Bounded Capacity Cut problem, and thus NP-complete. Finally, for the problem of improving compatibilities to maximize the price, we give polynomial approximation hardness results even in very restricted cases, but show that if all components have uniform prices, and quality differences are small, then an approximation can be found in polynomial time.

In this paper, we give the first constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward traveling salesman problem (TSP), motivated by robot navigation. In both problems, we are given a graph with lengths on edges and rewards on nodes, and a start node s. In the Orienteering problem, the goal is to find a path starting at s that maximizes the reward collected, subject to a hard limit on the total length of the path. In the Discounted-Reward TSP, instead of a length limit we are given a discount factor $\gamma$, and the goal is to maximize the total discounted reward collected, where the reward for a node reached at time t is discounted by $\gamma^t$. This problem is motivated by an approximation to a planning problem in the Markov decision process (MDP) framework under the commonly employed infinite horizon discounted reward optimality criterion. The approximation arises from a need to deal with exponentially large state spaces that emerge when trying to model one-time events and nonrepeatable rewards (such as for package deliveries). We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted Orienteering problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as k-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem in [E. M. Arkin, J. S. B. Mitchell, and G. Narasimhan, Proceedings of the $14$th ACM Symposium on Computational Geometry, 1998, pp. 307–316] and [B. Awerbuch, Y. Azar, A. Blum, and S. Vempala, SIAM J. Comput., 28 (1998), pp. 254–262]. We complement our approximation result for Orienteering by showing that the problem is APX-hard.

We consider online problems where purchases have time durations which expire regardless of whether the purchase is used or not. The parking permit problem is the natural analog of the well-studied ski rental problem in this model, and we provide matching upper and lower bounds on the competitive ratio for this problem. By extending the techniques thus developed, we give an online-competitive algorithm for the problem of renting steiner forest edges with time durations.

This article relates the notion of fairness in online routing and load balancing to vector majorization as developed by Hardy et al. [1929]. We define α -supermajorization as an approximate form of vector majorization, and show that this definition generalizes and strengthens the prefix measure proposed by Kleinberg et al. [2001] as well as the popular notion of max-min fairness .The article revisits the problem of online load-balancing for unrelated 1-∞ machines from the viewpoint of fairness. We prove that a greedy approach is O (log n )-supermajorized by all other allocations, where n is the number of jobs. This means the greedy approach is globally O (log n )- fair . This may be contrasted with polynomial lower bounds presented by Goel et al. [2001] for fair online routing.We also define a machine-centric view of fairness using the related concept of submajorization . We prove that the greedy online algorithm is globally O (log m )- balanced , where m is the number of machines.

The technique of k-anonymization has been proposed in the literature as an alternative way to release public information, while ensuring both data privacy and data integrity. We prove that two general versions of optimal k-anonymization of relations are NP-hard, including the suppression version which amounts to choosing a minimum number of entries to delete from the relation. We also present a polynomial time algorithm for optimal k-anonymity that achieves an approximation ratio independent of the size of the database, when k is constant. In particular, it is a O(k log k)-approximation where the constant in the big-O is no more than 4, However, the runtime of the algorithm is exponential in k. A slightly more clever algorithm removes this condition, but is a O(k log m)-approximation, where m is the degree of the relation. We believe this algorithm could potentially be quite fast in practice.

This paper presents the first polylogarithmic-competitive online algorithms for two-metric network design problems. These problems arise naturally in the design of computer networks (wired and wireless) as well as many other applications. In most cases the natural applications involve changing sets of communicating nodes, making the online model essential for addressing them.

Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible by their deadlines. We also consider the more general Vehicle Routing with Time-Windows problem, in which each node v also has a release-time R(v) and the goal is to visit as many nodes as possible within their "time-windows" [R(v),D(v)]. No good approximations were known previously for these problems on general metric spaces. We give an O(logn) approximation algorithm for Deadline-TSP, and extend this algorithm to an O(log2n) approximation for the Time-Window problem. We also give a bicriteria approximation algorithm for both problems: Given an ε>0, our algorithm produces a (1/ε) approximation, while exceeding the deadlines by a factor of 1+ε. We use as a subroutine for these results a constant-factor approximation that we develop for a generalization of the orienteering problem in which both the start and the end nodes of the path are fixed. In the process, we give a 3-approximation to the orienteering problem, improving on the previously best known 4-approximation of [6].

We analyze local search heuristics for the metric k-median and facility location problems. We define the locality gap of a local search procedure for a minimization problem as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k-median, we show that local search with swaps has a locality gap of 5. Furthermore, if we permit up to p facilities to be swapped simultaneously, then the locality gap is 3+2/p. This is the first analysis of a local search for k-median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For uncapacitated facility location, we show that local search, which permits adding, dropping, and swapping a facility, has a locality gap of 3. This improves the bound of 5 given by M. Korupolu, C. Plaxton, and R. Rajaraman [Analysis of a Local Search Heuristic for Facility Location Problems, Technical Report 98-30, DIMACS, 1998]. We also consider a capacitated facility location problem where each facility has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new local search operation which opens one or more copies of a facility and drops zero or more facilities. We prove that this local search has a locality gap between 3 and 4.

In this paper, we give the first constant-factor approximation algorithm for the rooted orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot navigation. In both problems, we are given a graph with lengths on edges and prizes (rewards) on nodes, and a start node s. In the orienteering problem, the goal is to find a path that maximizes the reward collected, subject to a hard limit on the total length of the path. In the Discounted-Reward TSP, instead of a length limit we are given a discount factor /spl gamma/, and the goal is to maximize total discounted reward collected, where reward for a node reached at time t is discounted by /spl gamma//sup t/. This is similar to the objective considered in Markov decision processes (MDPs) except we only receive a reward the first time a node is visited. We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted orienteering problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as k-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem based on B. Awerbuch et al. (1999) and E.M. Arkin (1998).

In this paper we present a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to within a constant factor of optimal, and cost to within alogarithmic factor. The class of networks that our algorithm applies to includes the one used by Akamai Technologies to deliver live media streams over the Internet. In particular, we analyze networks consisting of three stages of nodes. The nodes in the first stage are the sources where live streams originate. A source forwards each of its streams to one or more nodes in the second stage, which are called reflectors. A reflector can split an incoming stream into multiple identical outgoing streams, which are then sent on to nodes in the third and final stage, which are called the sinks. As the packets in a stream trave from one stage to the next, some of them may be lost. The job of a sink is to combine the packets from multiple instances of the same stream (by reordering packets and discarding duplicates) to form a single instance of the stream with minimal loss. We assume that the loss rate between any pair of nodes in the network is known, and that losses between different pairs are independent, but discuss extensions in which some losses may be correlated.

We consider an online version of the oblivious routing problem. Oblivious routing is the problem of picking a routing between each pair of nodes (or a set of flows), without knowledge of the traffic or demand between each pair, with the goal of minimizing the maximum congestion on any edge in the graph. In the online version of the problem, we consider a "repeated game" setting, in which the algorithm is allowed to choose a new routing each night, but is still oblivious to the demands that will occur the next day. The cost of the algorithm at every time step is its competitive ratio, or the ratio of its congestion to the minimum possible congestion for the demands at that time step.We present an algorithm that is (1+ε) competitive with respect to the best algorithm that uses a single routing for the entire sequence of days (known as the optimal static routing). Our result is a strengthening of the recent result of Azar et al [4], who gave a polynomial time algorithm to find an oblivious routing with the best possible competitive ratio, in that our algorithm achieves a competitive ratio arbitrarily to close to that of Azar et al [4], while at the same time performing nearly as well as the optimal static routing for the given sequence of demands. Our work was done independently, but subsequent to that of Azar et al [4].

We describe a general technique for converting an online algorithm Β to a truthtelling mechanism. We require that the original online competitive algorithm has certain "niceness" properties in that actions on future requests are independent of the actual value of requests which were accepted (though these actions will of course depend upon the set of accepted requests). Under these conditions, we are able to give an online truthtelling mechanism (where the values of requests are given by bids which may not accurately represent the valuation of the requesters) such that our total profit is within O(ρ + log μ) of the optimum offline profit obtained by an omniscient algorithm (one which knows the true valuations of the users). Here ρ is the competitive ratio of Β for the optimization version of the problem, and μ is the ratio of the maximum to minimum valuation for a request. In general there is an Ω(log μ) lower bound on the ratio of worst-case profit for a truthtelling mechanism when compared to the profit obtained by an omniscient algorithm, so this result is in some sense best possible. In addition, we prove that our construction is resilient against many forms of "cheating" attempts, such as forming coalitions.We demonstrate applications of this result to several problems. We develop online truthtelling mechanisms for online routing and admission control of path or multicast requests, assuming large network capacities. Assuming the existance of an algorithm Β for the optimization version of the problem, our techniques provide truthtelling mechanisms for general combinatorial auctions. However, designing optimization algorithms may be difficult in general because of online or approximation lower bounds. For the cases described above, we are able to design optimization algorithms Β by amortizing the lost benefit from online computation (and from approximation hardness in the case of multicast) against the benefit obtained from accepted requests.We comment that our upper bounds on profit competitiveness imply, as an obvious corollary, similar bound on global efficiency, namely overall well-being of all the users. This contrasts with most other work on truthtelling mechanisms for general online resource allocation, where only efficiency is maximized, and competitiveness can be arbitrarily poor.

The data stream model has recently attracted attention for its applicability to numerous types of data, including telephone records, Web documents, and clickstreams. For analysis of such data, the ability to process the data in a single pass, or a small number of passes, while using little memory, is crucial. We describe such a streaming algorithm that effectively clusters large data streams. We also provide empirical evidence of the algorithm's performance on synthetic and real data streams.

Streaming data analysis has recently attracted attention in numerous applications including telephone records, Web documents and click streams. For such analysis, single-pass algorithms that consume a small amount of memory are critical. We describe such a streaming algorithm that effectively clusters large data streams. We also provide empirical evidence of the algorithm's performance on synthetic and real data streams.

We consider the online variant of facility location, in which demand points arrive one at a time and we must maintain a set of facilities to service these points. We provide a randomized online O(1)-competitive algorithm in the case where points arrive in random order. If points are ordered adversarially, we show that no algorithm can be constant-competitive, and provide an O(log n)-competitive algorithm. Our algorithms are randomized and the analysis depends heavily on the concept of expected waiting time. We also combine our techniques with those of M. Charikar and S. Guha (1999) to provide a linear-time constant approximation for the offline facility location problem.

We consider the problem of incrementally designing a network to route demand to a single sink on an underlying metric space. We are given cables whose costs per unit length scale in a concave fashion with capacity. Under certain natural restrictions on the costs (called the Access Network Design constraints), we present a simple and efficient randomized algorithm that is competitive to the minimum cost solution when the demand points arrive online. In particular, if the order of arrival is a random permutation, we can prove a O(1) competitive ratio. For the fully adversarial case, the algorithm is O(K) -competitive, where K is the number of different pipe types. Since the value of K is typically small, this improves the previous O(log n log log n)-competitive algorithm which was based on probabilistically approximating the underlying metric by a tree metric. Our algorithm also improves the best known approximation ratio and running time for the offline version of this problem.

In this paper, we analyze local search heuristics for the k-median and facility location problems. We define the {\em locality gap\/} of a local search procedure as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k-median, we show that local search with swaps has a locality gap of exactly 5. When we permit p facilities to be swapped simultaneously then the locality gap of the local search procedure is exactly 3+2/p. This is the first analysis of local search for k-median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For Uncapacitated facility location, we show that local search, which permits adding, dropping and swapping a facility, has a locality gap of exactly 3. This improves the 5 bound of Korupolu et al. We also consider a capacitated facility location problem where each facilitym has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new operation which opens one or more copies of a facility and drops zero or more facilities. We prove that local search which permits this new operation has a locality gap between 3 and 4.

We present the first constant approximation to the single sink buy-at-bulk network design problem, where we have to design a network by buying pipes of different costs and capacities per unit length to route demands at a set of sources to a single sink. The distances in the underlying network form a metric. This result improves the previous bound of O(\log |R|), where R is the set of sources. Our algorithms are combinatorial and can be derandomized easily at the cost of a constant factor loss in the approximation ratio.

We consider opening facilities in order to gain a profit. We are given a set of demand points, and we must open some set of facilities such that every demand may be satisfied from a local facility and the total profit gained in this process is maximized. This contrasts with previous work on facility location and k-center problems, where opening a facility incurred a cost. The profit gained by opening a facility is a function of the amount of demand the facility satisfies. We model the dependence of profit on demand by creating many different possible facilities at each location, each of which provides a certain profit if opened and requires at least a certain amount of demand in order to open. Our model captures problem instances where profits may be positive or negative, and also instances where it is not necessary to satisfy every demand. Our algorithms provide the optimum total profit, while stretching the definition of locality by a constant and violating the required demands by a constant. We prove that without this stretch, the problem becomes NP-Hard to approximate.

Gives constant approximations for a number of layered network design problems. We begin by modeling hierarchical caching, where the caches are placed in layers and each layer satisfies a fixed percentage of the demand (bounded miss rates). We present a constant approximation to the minimum total cost of placing the caches and to the routing demand through the layers. We extend this model to cover more general layered caching scenarios, giving a constant combinatorial approximation to the well-studied multi-level facility location problem. We consider a facility location variant, the load-balanced facility location problem, in which every demand is served by a unique facility and each open facility must serve at least a certain amount of demand. By combining load-balanced facility location with our results on hierarchical caching, we give a constant approximation for the access network design problem.

Presents the cost-distance problem, which consists of finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the first known O(log k) randomized approximation scheme for the cost-distance problem, where k is the number of sources. We reduce several common network design problems to cost-distance problems, obtaining (in some cases) the first known logarithmic approximation for them. These problems include a single-sink buy-at-bulk problem with variable pipe types between different sets of nodes, facility location with buy-at-bulk-type costs on edges, constructing single-source multicast trees with good cost and delay properties, and multi-level facility location. Our algorithm is also easier to implement and significantly faster than previously known algorithms for buy-at-bulk design problems.

This paper presents online algorithms for routing and bandwidth allocation which simultaneously approximate fair and max-throughput solutions.In fact, the algorithms solve a more difficult problem: for any bandwidth b, the number of sessions that get bandwidth b in the online algorithm is not smaller than the number of sessions receiving vb offiine, where V is the competitive ratio.This problem is provably harder than the problem of maximizing throughput (e.g.[4]) or the problem of maximizing the bandwidth assigned to the most starved session (e.g.[3]).For the case where the algorithm assigns bandwidths, we present an O(log 2 n log 1+~ U/e)-competitive algorithm, for any e, where U is the minimum (over all choices of routes) of the 'maximum number of sessions routed along any single link.We also show an ~(log 1+~ U/e) lower bound in this model.For a more practically interesting model where the algorithm assigns routes and weights, and where these weights are used to drive the Weighted Fair Queuing policy in the routers, we present an O(log2nlogU)competitive algorithm.We also show that the dependence on U is necessary by presenting an ~(~) lower bound. The upper and lower bounds presented in [4] for online maximization of throughput become invalid if we