We show that running gradient descent with variable learning rate guarantees loss $f(x) ≤ 1.1 \cdot f(x^*)+\epsilon$ for the logistic regression objective, where the error $\epsilon$ decays exponentially with the number of iterations and polynomially with the magnitude of the entries of an arbitrary fixed solution $x$. This is in contrast to the common intuition that the absence of strong convexity precludes linear convergence of first-order methods, and highlights the importance of variable learning rates for gradient descent. We also apply our ideas to sparse logistic regression, where they lead to an exponential improvement of the sparsity-error tradeoff.

We propose a simple modification to the iterative hard thresholding (IHT) algorithm, which recovers asymptotically sparser solutions as a function of the condition number. When aiming to minimize a convex function f(x) with condition number $\kappa$ subject to x being an s-sparse vector, the standard IHT guarantee is a solution with relaxed sparsity $O(s\kappa^2)$, while our proposed algorithm, regularized IHT, returns a solution with sparsity $O(s\kappa)$. Our algorithm significantly improves over ARHT [Axiotis & Sviridenko, 2021] which also achieves $O(s\kappa)$, as it does not require re-optimization in each iteration (and so is much faster), is deterministic, and does not require knowledge of the optimal solution value f(x*) or the optimal sparsity level s. Our main technical tool is an adaptive regularization framework, in which the algorithm progressively learns the weights of an l_2 regularization term that will allow convergence to sparser solutions. We also apply this framework to low rank optimization, where we achieve a similar improvement of the best known condition number dependence from $\kappa^2$ to $\kappa$.

Coming up with effective ad text is a time consuming process, and particularly challenging for small businesses with limited advertising experience. When an inexperienced advertiser onboards with a poorly written ad text, the ad platform has the opportunity to detect low performing ad text, and provide improvement suggestions. To realize this opportunity, we propose an ad text strength indicator (TSI) which: (i) predicts the click-through-rate (CTR) for an input ad text, (ii) fetches similar existing ads to create a neighborhood around the input ad, (iii) and compares the predicted CTRs in the neighborhood to declare whether the input ad is strong or weak. In addition, as suggestions for ad text improvement, TSI shows anonymized versions of superior ads (higher predicted CTR) in the neighborhood. For (i), we propose a BERT based text-to-CTR model trained on impressions and clicks associated with an ad text. For (ii), we propose a sentence-BERT based semantic-ad-similarity model trained using weak labels from ad campaign setup data. Offline experiments demonstrate that our BERT based text-to-CTR model achieves a significant lift in CTR prediction AUC for cold start (new) advertisers compared to bag-of-words based baselines. In addition, our semantic-textual-similarity model for similar ads retrieval achieves a [email protected] of 0.93 (for retrieving ads from the same product category); this is significantly higher compared to unsupervised TF-IDF, word2vec, and sentence-BERT baselines. Finally, we share promising online results from advertisers in the Yahoo (Verizon Media) ad platform where a variant of TSI was implemented with sub-second end-to-end latency.

Numerous online stock image libraries offer high quality yet copyright free images for use in marketing campaigns. To assist advertisers in navigating such third party libraries, we study the problem of automatically fetching relevant ad images given the ad text (via a short textual query for images). Motivated by our observations in logged data on ad image search queries (given ad text), we formulate a keyword extraction problem, where a keyword extracted from the ad text (or its augmented version) serves as the ad image query. In this context, we propose VisualTextRank: an unsupervised method to (i) augment input ad text using semantically similar ads, and (ii) extract the image query from the augmented ad text. VisualTextRank builds on prior work on graph based context extraction (biased TextRank in particular) by leveraging both the text and image of similar ads for better keyword extraction, and using advertiser category specific biasing with sentence-BERT embeddings. Using data collected from the Verizon Media Native (Yahoo Gemini) ad platform's stock image search feature for onboarding advertisers, we demonstrate the superiority of VisualTextRank compared to competitive keyword extraction baselines (including an 11% accuracy lift over biased TextRank). For the case when the stock image library is restricted to English queries, we show the effectiveness of VisualTextRank on multilingual ads (translated to English) while leveraging semantically similar English ads. Online tests with a simplified version of VisualTextRank led to a 28.7% increase in the usage of stock image search, and a 41.6% increase in the advertiser onboarding rate in the Verizon Media Native ad platform.

The goal of Sparse Convex Optimization is to optimize a convex function f under a sparsity constraint s <= s* γ, where s* is the target number of non-zero entries in a feasible solution (sparsity) and γ >= 1 is an approximation factor. There has been a lot of work to analyze the sparsity guarantees of various algorithms (LASSO, Orthogonal Matching Pursuit (OMP), Iterative Hard Thresholding (IHT)) in terms of the Restricted Condition Number κ. The best known algorithms guarantee to find an approximate solution of value f(x*)+ε with the sparsity bound of γ = O(κ min{log ((f(x0)-f(x*)) / ε), κ}), where x* is the target solution. We present a new Adaptively Regularized Hard Thresholding (ARHT) algorithm that makes significant progress on this problem by bringing the bound down to γ=O(κ), which has been shown to be tight for a general class of algorithms including LASSO, OMP, and IHT. This is achieved without significant sacrifice in the runtime efficiency compared to the fastest known algorithms. We also provide a new analysis of OMP with Replacement (OMPR) for general f, under the condition s > s* κ^2 / 4, which yields compressed sensing bounds under the Restricted Isometry Property (RIP). When compared to other compressed sensing approaches, it has the advantage of providing a strong tradeoff between the RIP condition and the solution sparsity, while working for any general function f that meets the RIP condition.

The goal of Sparse Convex Optimization is to optimize a convex function $f$ under a sparsity constraint $s\leq s^*\gamma$, where $s^*$ is the target number of non-zero entries in a feasible solution (sparsity) and $\gamma\geq 1$ is an approximation factor. There has been a lot of work to analyze the sparsity guarantees of various algorithms (LASSO, Orthogonal Matching Pursuit (OMP), Iterative Hard Thresholding (IHT)) in terms of the Restricted Condition Number $\kappa$. The best known algorithms guarantee to find an approximate solution of value $f(x^*)+\epsilon$ with the sparsity bound of $\gamma = O\left(\kappa\min\left\{\log \frac{f(x^0)-f(x^*)}{\epsilon}, \kappa\right\}\right)$, where $x^*$ is the target solution. We present a new Adaptively Regularized Hard Thresholding (ARHT) algorithm that makes significant progress on this problem by bringing the bound down to $\gamma=O(\kappa)$, which has been shown to be tight for a general class of algorithms including LASSO, OMP, and IHT. This is achieved without significant sacrifice in the runtime efficiency compared to the fastest known algorithms. We also provide a new analysis of OMP with Replacement (OMPR) for general $f$, under the condition $s > s^* \frac{\kappa^2}{4}$, which yields Compressed Sensing bounds under the Restricted Isometry Property (RIP). When compared to other Compressed Sensing approaches, it has the advantage of providing a strong tradeoff between the RIP condition and the solution sparsity, while working for any general function $f$ that meets the RIP condition.

This paper considers optimizing a submodular function subject to a set of downward closed constraints. Previous literature on this problem has often constructed solutions by (1) discovering a fractional solution to the multi-linear extension and (2) rounding this solution to an integral solution via a contention resolution scheme. This line of research has improved results by either optimizing (1) or (2). Diverging from previous work, this paper introduces a principled method called contention resolution extensions of submodular functions. A contention resolution extension combines the contention resolution scheme into a continuous extension of a discrete submodular function. The contention resolution extension can be defined from effectively any contention resolution scheme. In the case where there is a loss in both (1) and (2), by optimizing them together, the losses can be combined resulting in an overall improvement. This paper showcases the concept by demonstrating that for the problem of optimizing a non-monotone submodular subject to the elements forming an independent set in an interval graph, the algorithm gives a .188-approximation. This improves upon the best known 1/(2e)~eq .1839 approximation.

Unit demand auctions power today's search and native ad marketplaces. Traditional implementations make an extreme "separability" assumption: the relative value of any two ad slots is the same for all advertisers. Under this assumption, the optimal assignment problem can be conveniently solved simply by sorting; without it, efficient allocation requires solving a full-blown weighted matching problem. Motivated by prior work and our own empirical evidence against separability, we abandon that assumption and tackle the algorithmic problems of assignment and pricing for general unit demand ad auctions. Instead of computing prices directly, we take a novel approach and compute bidders' full allocation curves---complete mappings from each agent's bid space to their allocation under the optimal assignment function---from which it is trivial to compute most prices of interest, like those of the Generalized Second Price (GSP) or Vickrey-Clarke-Groves (VCG) auctions. Remarkably, we show that these full allocation curves (and therefore prices) can be computed in the same asymptotic runtime required to compute the optimal matching alone.

We consider the supply chain problem of minimizing ordering, distribution, and inventory holding costs of a supply chain formed by a set of warehouses and retailers over a finite time horizon, which we call the production and distribution problem. This is a common generalization of the classical metric facility location problem and joint replenishment problem that coordinates the network design and inventory management decisions in an integrated manner. This coordination can represent significant economy for many applications, where network design and operational costs are normally considered separately. This problem is considered when the instances satisfy assumptions such as metric space of warehouse and retailer locations, and monotonic increasing inventory holding costs. In this work, we give a 2.77-approximation based on the randomized rounding of the natural mixed-integer programming relaxation. Also, we give a 5-approximation for the case that objective function includes retailer ordering setup costs.

We present a new framework for solving optimization problems with a diseconomy of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain task. The cost of resources grows superlinearly, as x q , q ≥ 1, with the amount x of resources used. We define a novel linear programming relaxation for such problems and then show that the integrality gap of the relaxation is A q , where A q is the q -th moment of the Poisson random variable with parameter 1. Using our framework, we obtain approximation algorithms for the Minimum Energy Efficient Routing, Minimum Degree Balanced Spanning Tree, Load Balancing on Unrelated Parallel Machines, and Unrelated Parallel Machine Scheduling with Nonlinear Functions of Completion Times problems. Our analysis relies on the decoupling inequality for nonnegative random variables. The inequality states that ║∑ i =1 n X i ║ q ≤ C q ║∑ i =1 n Y i ║ q , where X i are independent nonnegative random variables, Y i are possibly dependent nonnegative random variables, and each Y i has the same distribution as X i . The inequality was proved by de la Peña in 1990. De la Peña, Ibragimov, and Sharakhmetov showed that C q ≤ 2 for q ∈(1,2) and C q ≤ A q 1/ q for q ≥ 2. We show that the optimal constant is C q = A q 1/ q for any q ≥ 1. We then prove a more general inequality: For every convex function φ, E[φ(∑ i =1 n X i )] ≤ E[φ ( P ∑ i =1 n Y i )], and, for every concave function ψ, E[ψ (∑ i =1 n X i )] ≥ E[ψ(P∑ i =1 n Y i )], where P is a Poisson random variable with parameter 1 independent of the random variables Y i .

With an exploding global market and the recent introduction of online cash prize tournaments, fantasy sports contests are quickly becoming a central part of the social gaming and sports industries. For sports fans and online media companies, fantasy sports contests are an opportunity for large financial gains. However, they present a host of technical challenges that arise from the complexities involved in running a web-scale, prize driven fantasy sports platform. We initiate the study of these challenges by examining one concrete problem in particular: how to algorithmically generate contest payout structures that are 1) economically motivating and appealing to contestants and 2) reasonably structured and succinctly representable. We formalize this problem and present a general two-staged approach for producing satisfying payout structures given constraints on contest size, entry fee, prize bucketing, etc. We then propose and evaluate several potential algorithms for solving the payout problem efficiently, including methods based on dynamic programming, integer programming, and heuristic techniques. Experimental results show that a carefully designed heuristic scales very well, even to contests with over 100,000 prize winners. Our approach extends beyond fantasy sports – it is suitable for generating engaging payout structures for any contest with a large number of entrants and a large number of prize winners, including other massive online games, poker tournaments, and real-life sports tournaments.

Many problems in data mining and unsupervised machine learning take the form of minimizing a set function with cardinality constraints. More explicitly, denote by [n] the set {1,...,n} and let f(S) be a function from 2^[n] to R+. Our goal is to minimize f(S) subject to |S| <= k. These problems include clustering and covering problems as well as sparse regression, matrix approximation problems and many others. These combinatorial problems are hard to minimize in general. Finding good (e.g. constant factor) approximate solutions for them requires significant sophistication and highly specialized algorithms. In this paper we analyze the behavior of the greedy algorithm to all of these problems. We start by claiming that the functions above are special. A trivial observation is that they are non-negative and non-increasing, that is, f(S) >= f(union(S,T)) >= 0 for any S and T. This immediately shows that expanding solution sets is (at least potentially) beneficial in terms of reducing the function value. But, monotonicity is not sufficient to ensure that any number of greedy extensions of a given solution would significantly reduce the objective function.

The generalized second price (GSP) auction has served as the core selling mechanism for sponsored search ads for over a decade. However, recent trends expanding the set of allowed ad formats---to include a variety of sizes, decorations, and other distinguishing features---have raised critical problems for GSP-based platforms. Alternatives such as the Vickrey-Clarke-Groves (VCG) auction raise different complications because they fundamentally change the way prices are computed. In this paper we report on our efforts to redesign a search ad selling system from the ground up in this new context, proposing a mechanism that optimizes an entire slate of ads globally and computes prices that achieve properties analogous to those held by GSP in the original, simpler setting of uniform ads. A careful algorithmic coupling of allocation-optimization and pricing-computation allows our auction to operate within the strict timing constraints inherent in real-time ad auctions. We report performance results of the auction in Yahoo's Gemini Search platform.

We study the q -adic assignment problem. We first give an O ( n (q−1)/2) )-approximation algorithm for the Koopmans--Beckman version of the problem, improving upon the result of Barvinok. Then, we introduce a new family of instances satisfying “tensor triangle inequalities” and give a constant factor approximation algorithm for them. We show that many classical optimization problems can be modeled by q -adic assignment problems from this family. Finally, we give several integrality gap examples for the natural LP relaxations of the problem.

This paper shows that one can be competitive with the k-means objective while operating online. In this model, the algorithm receives vectors v1, …, vn one by one in an arbitrary order. For each vector vt the algorithm outputs a cluster identifier before receiving vt+1. Our online algorithm generates O(k log n log γn) clusters whose expected k-means cost is O(W* log n). Here, W* is the optimal k-means cost using k clusters and γ is the aspect ratio of the data. The dependence on γ is shown to be unavoidable and tight. We also show that, experimentally, it is not much worse than k-means++ while operating in a strictly more constrained computational model.

We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha times the to the cost of the optimal set of k clusters. We argue that this approach is natural in many settings, for which the exact number of clusters is a priori unknown, or unimportant up to a constant factor. We give new bi-criteria approximation algorithms, based on linear programming and local search, respectively, which attain a guarantee alpha(beta) depending on the number beta*k of clusters that may be opened. Our guarantee alpha(beta) is always at most 9 + epsilon and improves rapidly with beta (for example: alpha(2) < 2.59, and alpha(3) < 1.4). Moreover, our algorithms have only polynomial dependence on the dimension of the input data, and so are applicable in high-dimensional settings.

In this article, we present improved inapproximability results for the k -level uncapacitated facility location problem. In particular, we show that there is no polynomial time approximation algorithm with performance guarantee better than 1.539 unless P = NP for the case when k = 2. For the case of general k (tending to infinity), we obtain a better hardness factor of 1.61. Interestingly, our results show that the two-level problem is computationally harder than the well-known uncapacitated facility location problem ( k = 1) since the best-known approximation guarantee for the latter problem is 1.488 due to Li [2013], and our inapproximability is a factor of 1.539 for the two-level problem. The only inapproximability result known before for this class of metric facility location problems is the bound of 1.463 due to Guha and Khuller [1999], which holds even for the case of k = 1.

We revisit the pull-based broadcast scheduling model. In this model, there are n unit-sized pages of information available at the server. Clients send their requests to the server over time asking for specific pages. The server can transmit only one page at each time. When the server transmits a page, all outstanding requests for the page are simultaneously satisfied, and this is what distinguishes broadcast scheduling from the standard scheduling setting where each job must be processed separately by the server. Broadcast scheduling has received a considerable amount of attention due to the algorithmic challenges that it gives in addition to its applications in multicast systems and wireless and LAN networks. In this paper, we give the following new approximation results for two popular objectives: For the objective of minimizing the maximum flow time, we give the first PTAS. Previously, it was known that the algorithm First-In-First-Out (FIFO) is a 2-approximation, and it is tight [14, 16]. It has been suggested as an open problem to obtain a better approximation [14, 4, 25, 31]. For the objective of maximizing the throughput, we give a 0.7759-approximation which improves upon the previous best known 0.75-approximation [23]. Our key techniques for these improvements are novel variants of α-point rounding that can effectively reduce congestion in schedule which is often the main hurdle in designing scheduling algorithms based on linear programming. We believe that our new rounding schemes could be of potential use for other scheduling problems.

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature c. In the case of submodular maximization with curvature c, we obtain a (1 — c/e)-approximation — the first improvement over the greedy (1 — e−c)/c-approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.

We present a new framework for solving optimization problems with a diseconomy of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain task. The cost of resources grows superlinearly, as xq, q ≥ 1, with the amount x of resources used. We define a novel linear programming relaxation for such problems, and then show that the integrality gap of the relaxation is Aq, where Aqis the q-th moment of the Poisson random variable with parameter 1. Using our framework, we obtain approximation algorithms for the Minimum Energy Efficient Routing, Minimum Degree Balanced Spanning Tree, Load Balancing on Unrelated Parallel Machines, and Unrelated Parallel Machine Scheduling with Nonlinear Functions of Completion Times problems. Our analysis relies on the decoupling inequality for nonnegative random variables. The inequality states that ||Σi=1nXi||q≤ Cq ||Σi=1nYi||q, where Xi are independent nonnegative random variables, Yi are possibly dependent nonnegative random variable, and each Yihas the same distribution as Xi. The inequality was proved by de la Peña in 1990. However, the optimal constant Cq was not known. We show that the optimal constant is Cq= Aq1/q.

In a stochastic probing problem we are given a universe E, where each element e in E is active independently with probability p in [0,1], and only a probe of e can tell us whether it is active or not. On this universe we execute a process that one by one probes elements - if a probed element is active, then we have to include it in the solution, which we gradually construct. Throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. This abstract model was presented in [Gupta and Nagaraja, IPCO 2013], and provides a unified view of a number of problems. Thus far all the results in this general framework pertain only to the case in which we are maximizing a linear objective function of the successfully probed elements. In this paper we generalize the stochastic probing problem by considering a monotone submodular objective function. We give a (1-1/e)/(k_in+k_out+1)-approximation algorithm for the case in which we are given k_in greater than 0 matroids as inner constraints and k_out greater than 1 matroids as outer constraints. There are two main ingredients behind this result. First is a previously unpublished stronger bound on the continuous greedy algorithm due to Vondrak. Second is a rounding procedure that also allows us to obtain an improved 1/(k_in+k_out)-approximation for linear objective functions.

Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the sizes of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. Here, the processing time of job j on machine i is governed by random variable P_{ij} , and its realization becomes known only upon job completion. With w_j being the given weight of job j, we study the objective to minimize the expected total weighted completion time E[Sum w_j.C_j] , where C_j is the completion time of job j. By means of a novel time-indexed linear programming relaxation, we compute in polynomial time a scheduling policy with performance guarantee (3+D)/2+e. Here, e>0 is arbitrarily small, and D is an upper bound on the squared coefficient of variation of the processing times. When jobs also have individual release dates r_{ij}, our bound is (2+D)+e. We also show that the dependence of the performance guarantees on D is tight. Via D=0, currently best known bounds for deterministic scheduling on unrelated machines are contained as special case.

We show that for every positive ε > 0, unless NP ⊂ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2 log 1-ε n by a reduction from the maximum label cover problem. Our result also implies that Approximate Graph Isomorphism is not robust and is, in fact, 1 - ε versus ε hard assuming the Unique Games Conjecture. Then, we present an O (√n)-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in state-of-the-art exact algorithms.

We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed-scalable processors in a fully heterogeneous setting. For both the preemptive-non-migratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-non-migratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.

In the three-dimensional (3D) strip packing problem, we are given a set of 3D rectangular items and a 3D box $B$. The goal is to pack all the items in $B$ such that the height of the packing is minimized. We consider the most basic version of the problem, where the items must be packed with their edges parallel to the edges of $B$ and cannot be rotated. Building upon Caprara's work for the two-dimensional (2D) bin packing problem, we obtain an algorithm that, given any $\epsilon>0$, achieves an approximation of $T_{\infty}+\epsilon\approx1.69103+\epsilon$, where $T_{\infty}$ is the well-known number that occurs naturally in the context of bin packing. Our key idea is to establish a connection between bin packing solutions for an arbitrary instance $I$ and the strip packing solutions for the corresponding instance obtained from $I$ by applying the harmonic transformation to certain dimensions. Based on this connection, we also give a simple alternate proof of the $T_{\infty}+\epsilon$ approximation for 2D bin packing due to Caprara. In particular, we show how his result follows from a simple modification of the asymptotic approximation scheme for 2D strip packing due to Kenyon and Rémila.

We consider the classical matroid matching problem. Unweighted matroid matching for linearly represented matroids was solved by Lovász, and the problem is known to be intractable for general matroids. We present a polynomial-time approximation scheme for unweighted matroid matching for general matroids. In contrast, we show that natural linear-programming relaxations that have been studied have an $\Omega(n)$ integrality gap, and, moreover, $\Omega(n)$ rounds of the Sherali--Adams hierarchy are necessary to bring the gap down to a constant. More generally, for any fixed $k \geq 2$ and $\epsilon>0$, we obtain a $(k/2+\epsilon)$-approximation for matroid matching in $k$-uniform hypergraphs, also known as the matroid $k$-parity problem. As a consequence, we obtain a $(k/2+\epsilon)$-approximation for the problem of finding the maximum-cardinality set in the intersection of $k$ matroids. We also give a $3/2$-approximation for the weighted version of a special case of matroid matching, the matchoid problem.

In this paper, we present improved inapproximability results for the k-level uncapacitated facility location problem. In particular, we show that there is no polynomial time approximation algorithm with performance guarantee better than 1.539 unless NP is contained in DTIME(nO(log log n)) for the case when k = 2. For the case of general k (tendining to infinity) we obtain a better hardness factor of 1.61. Interestingly, our results show that the two-level problem is computationally harder than the well known uncapacitated facility location problem (k = 1) since the best known approximation guarantee for the latter problem is 1.488 due to Li [22], and our inapproximability is a factor of 1.539 for the two-level problem. The only inapproximability result known before for this class of metric facility location problems is the bound of 1.463 due to Guha and Khuller [17], which holds even for the case of k = 1.

In this work we design a general method for proving moment inequalities for polynomials of independent random variables.Our method works for a wide range of random variables including Gaussian, Boolean, exponential, Poisson and many others.We apply our method to derive general concentration inequalities for polynomials of independent random variables.We show that our method implies concentration inequalities for some previously open problems, e.g.permanent of random symmetric matrices.We show that our concentration inequality is stronger than the wellknown concentration inequality due to Kim and Vu [29].The main advantage of our method in comparison with the existing ones is a wide range of random variables we can handle and bounds for previously intractable regimes of high degree polynomials and small expectations.On the negative side we show that even for boolean random variables each term in our concentration inequality is tight.

In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets S = {S_1, S_2, ..., S_m} where each set S_i in 2^{[n]} has a positive requirement k(S_i) that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set S_i is defined as the first index j in the ordering such that the first j elements in the ordering contain k(S_i) elements in S_i. This problem was introduced by [Azar, Gamzu and Yin, 2009] with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known [Bansal, Gupta and Krishnaswamy, 2010][Skutella and Williamson, 2011]. We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set S is covered in the moment when k(S) amount of elements in S are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming and analysis are completely different from [Bansal, Gupta and Krishnaswamy, 2010][Skutella and Williamson, 2011]. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved 12.4-approximation for the non-preemptive problem.

We consider the scheduling of biprocessor jobs under sum objective (BPSMSM). Given a collection of unit-length jobs where each job requires the use of two processors, find a schedule such that no two jobs involving the same processor run concurrently. The objective is to minimize the sum of the completion times of the jobs. Equivalently, we would like to find a sum edge coloring of a given multigraph, that is, a partition of its edge set into matchings M 1 ,…, M t minimizing Σ i =1 t i | M i |. This problem is APX-hard, even in the case of bipartite graphs [Marx 2009]. This special case is closely related to the classic open shop scheduling problem. We give a 1.8298-approximation algorithm for BPSMSM improving the previously best ratio known of 2 [Bar-Noy et al. 1998]. The algorithm combines a configuration LP with greedy methods, using nonstandard randomized rounding on the LP fractions. We also give an efficient combinatorial 1.8886-approximation algorithm for the case of simple graphs, which gives an improved 1.79568 + O (log d¯/d¯)-approximation in graphs of large average degree d¯.

We consider the classical matroid matching problem. Unweighted matroid matching for linear matroids was solved by Lovasz, and the problem is known to be intractable for general matroids. We present a PTAS for unweighted matroid matching for general matroids. In contrast, we show that natural LP relaxations have an Ω(n) integrality gap and moreover, Ω(n) rounds of the Sherali-Adams hierarchy are necessary to bring the gap down to a constant. More generally, for any fixed k>=2 and ε>0, we obtain a (k/2+ε)-approximation for matroid matching in k-uniform hypergraphs, also known as the matroid k-parity problem. As a consequence, we obtain a (k/2+ε)-approximation for the problem of finding the maximum-cardinality set in the intersection of k matroids. We have also designed a 3/2-approximation for the weighted version of a special case of matroid matching, the matchoid problem.

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any nonnegative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for nonmonotone submodular functions. In particular, for any constant k, we present a $(\frac{1}{k+2+\frac{1}{k}+\epsilon})$-approximation for the submodular maximization problem under k matroid constraints, and a $(\frac{1}{5}-\epsilon)$-approximation algorithm for this problem subject to k knapsack constraints ($\epsilon>0$ is any constant). We improve the approximation guarantee of our algorithm to $\frac{1}{k+1+\frac{1}{k-1}+\epsilon}$ for $k\geq2$ partition matroid constraints. This idea also gives a $(\frac{1}{k+\epsilon})$-approximation for maximizing a monotone submodular function subject to $k\geq2$ partition matroids, which is an improvement over the previously best known guarantee of $\frac{1}{k+1}$.

We study the following problem related to pricing over time. Assume there is a collection of bidders, each of whom is interested in buying a copy of an item of which there is an unlimited supply. Every bidder is associated with a time interval over which the bidder will consider buying a copy of the item, and a maximum value the bidder is willing to pay for the item. On every time unit, the seller sets a price for the item. The seller's goal is to set the prices so as to maximize revenue from the sale of copies of items over the time period. In the first model considered, we assume that all bidders are impatient , that is, bidders buy the item at the first time unit within their bid interval that they can afford the price. To the best of our knowledge, this is the first work that considers this model. In the offline setting, we assume that the seller knows the bids of all the bidders in advance. In the online setting we assume that at each time unit the seller only knows the values of the bids that have arrived before or at that time unit. We give a polynomial time offline algorithm and prove upper and lower bounds on the competitiveness of deterministic and randomized online algorithms, compared with the optimal offline solution. The gap between the upper and lower bounds is quadratic. We also consider the envy-free model in which bidders are sold the item at the minimum price during their bid interval, as long as it is not over their limit value. We prove tight bounds on the competitiveness of deterministic online algorithms for this model, and upper and lower bounds on the competitiveness of randomized algorithms with quadratic gap. The lower bounds for the randomized case in both models use a novel general technique.

Quadratic Assignment is a basic problem in combinatorial optimization, which generalizes several other problems such as Traveling Salesman, Linear Arrangement, Dense k Subgraph, and Clustering with given sizes. The input to the Quadratic Assignment Problem consists of two n × n symmetric non-negative matrices W = (wi,j) and D = (di,j). Given matrices W, D, and a permutation π : [n] → [n], the objective function is . In this paper, we study the Maximum Quadratic Assignment Problem, where the goal is to find a permutation π that maximizes Q(π). We give an Õ(√n) approximation algorithm, which is the first non-trivial approximation guarantee for this problem. The above guarantee also holds when the matrices W, D are asymmetric. An indication of the hardness of Maximum Quadratic Assignment is that it contains as a special case, the Dense k Subgraph problem, for which the best known approximation ratio ≈ n1/3 (Feige et al. [8]). When one of the matrices W, D satisfies triangle inequality, we obtain a approximation algorithm. This improves over the previously best-known approximation guarantee of 4 (Arkin et al. [4]) for this special case of Maximum Quadratic Assignment. The performance guarantee for Maximum Quadratic Assignment with triangle inequality can be proved relative to an optimal solution of a natural linear programming relaxation, that has been used earlier in Branch-and-Bound approaches (see eg. Adams and Johnson [1]). It can also be shown that this LP has an integrality gap of for general Maximum Quadratic Assignment.

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for non-monotone submodular functions. In particular, for any constant k, we present a (1/k+2+1/k+ε)-approximation for the submodular maximization problem under k matroid constraints, and a (1/5-ε)-approximation algorithm for this problem subject to k knapsack constraints (ε>0 is any constant). We improve the approximation guarantee of our algorithm to 1/k+1+{1/k-1}+ε for k≥2 partition matroid constraints. This idea also gives a ({1/k+ε)-approximation for maximizing a monotone submodular function subject to k≥2 partition matroids, which improves over the previously best known guarantee of 1/k+1.

This issue contains the polished, extended, and fully refereed versions of a selection of papers that were presented at the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC 2007), which was held June 11–13, 2007, in San Diego, California, in conjunction with the Federated Computing Research Conference (FCRC 2007). Unrefereed preliminary versions of these papers were published by ACM in the proceedings of the meeting, along with the other papers presented at the symposium. The conference program included 77 papers, selected from among a record 312 submissions by a program committee chaired by Uriel Feige and consisting of Eric Allender, Andris Ambainis, Chandra Chekuri, Artur Czumaj, Yevgeniy Dodis, Michel Goemans, Martin Grohe, Russell Impagliazzo, Valerie King, Robert Kleinberg, Vladlen Koltun, Robi Krauthgamer, Jiří Matoušek, Milena Mihail, Ryan O'Donnell, Vijaya Ramachandran, Leonard Schulman, Maxim Sviridenko, Mikkel Thorup, Salil Vadhan, and Santosh Vempala. The authors of 14 of these 77 papers were invited to submit revised versions for this special section; nine accepted the invitation, although one paper was not completed in time to appear in this volume. One paper that appears in this special issue (by Haitner et al.) is the result of merging a STOC 2007 paper with a FOCS 2006 paper that had been invited for the special issue of SIAM Journal on Computing devoted to FOCS 2006; the authors felt that a single, streamlined paper would be more beneficial to the community, and the editors concurred. The paper by Martin Fürer appearing in this issue is one of two papers that shared the award for best paper in STOC 2007. All of these papers were refereed in accordance with the stringent standards of SIAM Journal on Computing. We thank the anonymous referees and the authors for their efforts, resulting in substantial improvements in the end product. We also thank the rest of the program committee members for their help in the selection process. The three of us listed below are honored to have had the opportunity to serve as guest editors in preparing this special issue.

In this paper we introduce a new general approximation method for set covering problems, based on the combination of randomized rounding of the (near-) optimal solution of the linear programming (LP) relaxation, leading to a partial integer solution and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. For d-dimensional vector packing, we obtain a polynomial-time randomized algorithm with asymptotic approximation guarantee arbitrarily close to $\ln d + 1$. For $d=2$, this value is $1.693\dots$; i.e., we break the natural 2 “barrier” for this case. Moreover, for small values of d this is a notable improvement over the previously known $O(\ln d)$ guarantee by Chekuri and Khanna [SIAM J. Comput., 33 (2004), pp. 837–851]. For two-dimensional bin packing with and without rotations, we obtain polynomial-time randomized algorithms with asymptotic approximation guarantee $1.525\dots$, improving upon previous algorithms with asymptotic performance guarantees arbitrarily close to 2 by Jansen and van Stee [On strip packing with rotations, in Proceedings of the 37th Annual ACM Symposium on the Theory of Computing, 2005, pp. 755–761] for the problem with rotations and $1.691\ldots$ by Caprara [Math. Oper. Res., 33 (2008), pp. 203–215] for the problem without rotations. The previously unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker [Combinatorica, 1 (1981), pp. 349–355]. We prove that their approximation scheme is “subset oblivious,” which leads to numerous applications.

We consider the well-known minimum quadratic assignment problem. In this problem we are given two n × n nonnegative symmetric matrices A = ( a ij ) and B = ( b ij ). The objective is to compute a permutation π of V = {1,…, n } so that ∑ i , j ∈ V i ≠ j a π( i ),π( j ) b i , j is minimized. We assume that A is a 0/1 incidence matrix of a graph, and that B satisfies the triangle inequality. We analyze the approximability of this class of problems by providing polynomial bounded approximations for some special cases, and inapproximability results for other cases.

We consider scheduling policies in a client-server system where the server delivers data by broadcasting it to the users. In thesimplest model of the problem, there is a single server that holds n pages of unit size. Multiple requests for these pages arrive over time. At each time slot the server broadcasts exactly one page which satisfies all of the outstanding requests for this page at that time. We consider the problem of minimizing the average response time of requests, where the response time of the request is the duration since the request is placed until the time it is satisfied. For the offline version of this problem we give an algorithm with an approximation ratio of $O(\log^2(n) / \log \log(n))$. More generally, for any $\epsilon>0$, the algorithm achieves an average response time of $(2+\epsilon) \cdot \text{OPT} + O(\log n \cdot \log_{(1+\epsilon)} n)$, which is useful when the optimum value is large. This substantially improves the previously best known approximation factor of $O(\sqrt{n})$ for the problem [N. Bansal, M. Charikar, S. Khanna, and J. Naor, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, British Columbia, ACM, New York, SIAM, Philadelphia, 2005, pp. 215–221]. Our result is based on iteratively relaxing and rounding an auxiliary linear program derived from a natural linear programming relaxation of the problem.

In the rectangle stabbing problem, we are given a set of axis parallel rectangles and a set of horizontal and vertical lines, and our goal is to find a minimum size subset of lines that intersect all the rectangles. In this article, we study the capacitated version of this problem in which the input includes an integral capacity for each line. The capacity of a line bounds the number of rectangles that the line can cover. We consider two versions of this problem. In the first, one is allowed to use only a single copy of each line ( hard capacities ), and in the second, one is allowed to use multiple copies of every line, but the multiplicities are counted in the size (or weight) of the solution ( soft capacities ). We present an exact polynomial-time algorithm for the weighted one dimensional case with hard capacities that can be extended to the one dimensional weighted case with soft capacities. This algorithm is also extended to solve a certain capacitated multi-item lot-sizing inventory problem with joint set-up costs. For the case of d -dimensional rectangle stabbing with soft capacities, we present a 3 d -approximation algorithm for the unweighted case. For d -dimensional rectangle stabbing problem with hard capacities, we present a bi-criteria algorithm that computes 4 d -approximate solutions that use at most two copies of every line. Finally, we present hardness results for rectangle stabbing when the dimension is part of the input and for a two-dimensional weighted version with hard capacities.

In this paper we introduce a new general framework for set covering problems, based on the combination of randomized rounding of the (near-)optimal solution of the linear programming (LP) relaxation, leading to a partial integer solution, and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. Applying our general framework we obtain a polynomial-time randomized algorithm for d-dimensional vector packing with approximation guarantee arbitrarily close to ln d + 1. For d = 2, this value is 1.693 ..., i.e., we break the natural 2 "barrier" for this case. Moreover, for small values of d this is a notable improvement over the previously-known O(ln d) guarantee by Chekuri and Khanna (2004). For 2-dimensional bin packing with and without rotations, we construct algorithms with performance guarantee arbitrarily close to 1.525..., improving upon previous algorithms with performance guarantee of 2 + epsiv by Jansen and Zhang (2004) for the problem with rotations and1.691... by Caprara (2002) for the problem without rotations. The previously-unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker (1981). We prove that their approximation scheme is "subset oblivious", which leads to numerous applications. Another byproduct of our paper is an algorithm that solves a well-known configuration LP for 2-dimensional bin packing within a factor of (1 + epsiv) for any epsiv gt; 0. Interestingly, we do it without using an approximate separation oracle, which would correspond to a well-known geometric 2-dimensional knapsack. Although separation and optimization are equivalent (M. Grotschel et al, 1988) and the existence of an approximation scheme for the separation problem remains open, we are able to design an approximation scheme for the configuration LP since its objective function is unweighed

We consider the following problem: The Santa Claus has n presents that he wants to distribute among m kids. Each kid has an arbitrary value for each present. Let pij be the value that kid i has for present j. The Santa's goal is to distribute presents in such a way that the least lucky kid is as happy as possible, i.e he tries to maximize mini=1,...,m sumj ∈ Si pij where Si is a set of presents received by the i-th kid.Our main result is an O(log log m/log log log m) approximation algorithm for the restricted assignment case of the problem when pij ∈ pj,0 (i.e. when present j has either value pj or 0 for each kid). Our algorithm is based on rounding a certain natural exponentially large linear programming relaxation usually referred to as the configuration LP. We also show that the configuration LP has an integrality gap of Ω(m1/2) in the general case, when pij can be arbitrary.

We introduce and evaluate a middleware clustering technology capable of allocating resources to web applications through dynamic application instance placement. We define application instance placement as the problem of placing application instances on a given set of server machines to adjust the amount of resources available to applications in response to varying resource demands of application clusters. The objective is to maximize the amount of demand that may be satisfied using a configured placement. To limit the disturbance to the system caused by starting and stopping application instances, the placement algorithm attempts to minimize the number of placement changes. It also strives to keep resource utilization balanced across all server machines. Two types of resources are managed, one load-dependent and one load-independent. When putting the chosen placement in effect our controller schedules placement changes in a manner that limits the disruption to the system.

The 2-dimensional bin packing problem (2BP) is a generalization of the classical Bin Packing problem and is defined as follows: Given a collection of rectangles specified by their width and height, pack these into the minimum number of square bins of unit size. We study the case of 'orthogonal packing without rotations', where rectangles cannot be rotated and must be packed parallel to the edges of a bin. Often in practical cases of 2BP problems there are additional constraints on how complicated the packing patterns in a bin can be. A well-studied and frequently used constraint is that every rectangle in the packing must be obtainable by recursively applying a sequence of edge-to-edge cuts parallel to the edges of the bin. Such cuts are known as guillotine cuts. Our main result is that the guillotine 2BP problem admits an asymptotic polynomial time approximation scheme. This is in sharp contrast with the fact that the general 2BP problem is APX-Hard. En route to our main result, we show a structural theorem about approximating general guillotine packings by simpler packings, which could be of independent interest.

A directed multigraph is said to be d -regular if the indegree and outdegree of every vertex is exactly d . By Hall's theorem, one can represent such a multigraph as a combination of at most n 2 cycle covers, each taken with an appropriate multiplicity. We prove that if the d -regular multigraph does not contain more than ⌊ d/2 ⌋ copies of any 2-cycle then we can find a similar decomposition into n 2 pairs of cycle covers where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such a decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give an alternative, simpler algorithm to extract a single such pair.This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum Traveling Salesman Problem (TSP) problem. The first stage of the rounding procedure obtains two cycle covers that do not share a 2-cycle with weight at least twice the weight of the optimal solution. Then we show how to extract a tour from the 2 cycle covers, whose weight is at least 2/3 of the weight of the longest tour. This improves upon the previous 5/8 approximation with a simpler algorithm. Utilizing a reduction from maximum TSP to the shortest superstring problem, we obtain a 2.5-approximation algorithm for the latter problem, which is again much simpler than the previous one.For minimum asymmetric TSP, the same technique gives two cycle covers, not sharing a 2-cycle, with weight at most twice the weight of the optimum. Assuming triangle inequality, we then show how to obtain from this pair of cycle covers a tour whose weight is at most 0.842 log 2 n larger than optimal. This improves upon a previous approximation algorithm with approximation guarantee of 0.999 log 2 n . Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2/3, previously 3/5) and maximum asymmetric TSP with triangle inequality (factor 10/13, previously 3/4).

We consider two types of buffering policies that are used in network switches supporting Quality of Service (QoS). In the FIFO type, packets must be transmitted in the order in which they arrive; the constraint in this case is the limited buffer space. In the bounded-delay type, each packet has a maximum delay time by which it must be transmitted, or otherwise it is lost. We study the case of overloads resulting in packet loss. In our model, each packet has an intrinsic value, and the goal is to maximize the total value of transmitted packets. Our main contribution is a thorough investigation of some natural greedy algorithms in various models. For the FIFO model we prove tight bounds on the competitive ratio of the greedy algorithm that discards packets with the lowest value when an overflow occurs. We also prove that the greedy algorithm that drops the earliest packets among all low-value packets is the best greedy algorithm. This algorithm can be as much as 1.5 times better than the tail-drop greedy policy, which drops the latest lowest-value packets. In the bounded-delay model we show that the competitive ratio of any on-line algorithm for a uniform bounded-delay buffer is bounded away from 1, independent of the delay size. We analyze the greedy algorithm in the general case and in three special cases: delay bound 2, link bandwidth 1, and only two possible packet values. Finally, we consider the off-line scenario. We give efficient optimal algorithms and study the relation between the bounded-delay and FIFO models in this case.

A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem one can represent such a multigraph as a combination of at most n/sup 2/ cycle covers each taken with an appropriate multiplicity. We prove that if the d-regular multigraph does not contain more than /spl lfloor/d/2/spl rfloor/ copies of any 2-cycle then we can find a similar decomposition into 0(n/sup 2/) pairs of cycle covers where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give a simpler algorithm to extract a single such pair. This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum and minimum TSP problems. For maximum TSP, we obtain a tour whose weight is at least 2/3 of the weight of the longest tour, improving a previous 5/8 approximation. For minimum TSP we obtain a tour whose weight is at most 0.842log/sub 2/ n times the optimal, improving a previous 0.999log/sub 2/ n approximation. Utilizing a reduction from maximum TSP to the shortest superstring problem we obtain a 2.5-approximation algorithm for the latter problem which is again much simpler than the previous one. Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2/3, previously 3/5) and maximum asymmetric TSP with triangle inequality (factor 10/13, previously 3/4 ).

In this paper we present a linear time approximation scheme for the job shop scheduling problem with a fixed number of machines and fixed number of operations per job. This improves on the previously best $2+\epsilon$, $\epsilon > 0$, approximation algorithm for the problem by Shmoys, Stein, and Wein [SIAM J. Comput., 23 (1994), pp. 617--632]. Our approximation scheme is very general and it can be extended to the case of job shop scheduling problems with release and delivery times, multistage job shops, dag job shops, and preemptive variants of most of these problems.

The maximum asymmetric traveling salesperson problem, also known as the taxicab rip-off problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with nonnegative weights. We propose a polynomial time approximation algorithm for the problem with a 5/8 approximation guarantee. This (1) improves upon the approximation factors of previous results and (2) presents a simpler solution to the previously fairly involved algorithms. Our solution uses a simple linear programming formulation. Previous solutions were combinatorial. We make use of the linear programming in a novel manner and strengthen the path-coloring method originally proposed in [S. R. Kosaraju, J. K. Park, and C. Stein, Long tours and short superstrings, in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 166--177].

We investigate the approximability of a no-wait permutation flow shop scheduling problem under the makespan criterion. We present a polynomial time approximation scheme (PTAS) for the problem on any fixed number of machines.

A web content hosting service provider needs to dynamically allocate servers in a server farm to its customers' web sites. Ideally, the allocation to a site should always suffice to handle its load. However, due to a limited number of servers and the overhead incurred in changing the allocation of a server from one site to another, the system may become overloaded. The problem faced by the web hosting service provider is how to allocate the available servers in the most profitable way. Adding to the complexity of this problem is the fact that future loads of the sites are either unknown or known only for the very near future.In this paper we model this server allocation problem, and consider both its offline and online versions. We give a polynomial time algorithm for computing the optimal offline allocation. In the online setting, we show almost optimal algorithms (both deterministic and randomized) for any positive lookahead. The quality of the solution improves as the lookahead increases. We also consider several special cases of practical interest. Finally, we present some experimental results using actual trace data that show that one of our online algorithm performs very close to optimal.Interestingly, the online server allocation problem can be cast as a more general benefit task system that we define. Our results extend to this task system, which captures also the benefit maximization variants of the k-server problem and the metrical task system problem. It follows that the benefit maximization variants of these problems are more tractable than their cost minimization variants.

We consider two types of buffering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be released in the order they arrive; the difficulty in this case is the limited buffer space. In the bounded-delay type, each packet has a maximum delay time by which it must be released, or otherwise it is lost. We study the cases where the incoming streams overload the buffers, resulting in packet loss. In our model, each packet has an intrinsic value; the goal is to maximize the total value of packets transmitted

Given a directed graph G and an arc weight function $w: E(G)\rightarrow\mathbb{R}_+$, the maximum directed cut problem ({\sc max dicut}) is that of finding a directed cut $\delta (X)$ with maximum total weight. In this paper we consider a version of {\sc max dicut}---{\sc max dicut} with given sizes of parts or {\sc max dicut with gsp}---whose instance is that of {\sc max dicut} plus a positive integer p, and it is required to find a directed cut $\delta (X)$ having maximum weight over all cuts $\delta (X)$ with $|X|=p$. Our main result is a $0.5$-approximation algorithm for solving the problem. The algorithm is based on a tricky application of the pipage rounding technique developed in some earlier papers by two of the authors and a remarkable structural property of basic solutions to a linear relaxation. The property is that each component of any basic solution is an element of a set $\{0,\delta,1/2,1-\delta,1 \}$, where $\delta$ is a constant that satisfies $0 < \delta < 1/2$ and is the same for all components.

We investigate the approximability of no-wait shop scheduling problems under the makespan criterion. In a flow shop, all jobs pass through the machines in the same ordering. In the more general job shop, the routes of the jobs are job-dependent. We present a polynomial time approximation scheme (PTAS) for the no-wait flow shop problem on any fixed number of machines. Unless P=NP, this result cannot be extended to the job shop problem on a fixed number of machines: We show that the no-wait job shop problem is APX-hard on (i) two machines with at most five operations per job, and on (ii) three machines with at most three operations per job.

We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for /spl alpha/(1+/spl epsiv/) approximation is of the form f(1//spl epsiv/, m)poly(n).