We consider the online sparse linear regression problem, which is the problem of sequentially making predictions observing only a limited number of features in each round, to minimize regret with respect to the best sparse linear regressor, where prediction accuracy is measured by square loss. We give an \em inefficient algorithm that obtains regret bounded by \tildeO(\sqrtT) after T prediction rounds. We complement this result by showing that no algorithm running in polynomial time per iteration can achieve regret bounded by O(T^1-δ) for any constant δ> 0 unless \textsfNP ⊆\textsfBPP. This computational hardness result resolves an open problem presented in COLT 2014 (Kale, 2014) and also posed by Zolghadr et al. (2013). This hardness result holds even if the algorithm is allowed to access more features than the best sparse linear regressor up to a logarithmic factor in the dimension.

Variable selection for sparse linear regression is the problem of finding, given an m\times p matrix B and a target vector \bfy, a sparse vector \bfx such that B\bfx approximately equals \bfy. Assuming a standard complexity hypothesis, we show that no polynomial-time algorithm can find a k’-sparse \bfx with \|B\bfx-\bfy\|^2\le h(m,p), where k’=k⋅2^\log ^1-δ p and h(m,p)= p^C_1 m^1-C_2, where δ>0,C_1>0,C_2>0 are arbitrary. This is true even under the promise that there is an unknown k-sparse vector \bfx^* satisfying B\bfx^*=\bfy. We prove a similar result for a statistical version of the problem in which the data are corrupted by noise. To the authors’ knowledge, these are the first hardness results for sparse regression that apply when the algorithm simultaneously has k’>k and h(m,p)>0.

In Overlapping Correlation Clustering (OCC), a number of objects are assigned to clusters. Two objects in the same cluster have correlated characteristics. As opposed to traditional clustering where objects are assigned to a single cluster, in OCC objects may be assigned to one or more clusters. In this paper, we present Biased Random-Key Genetic Algorithms for OCC. We present computational experiments such results outperformed the state of art methods for OCC.

With the widespread use of shared-nothing clusters of servers, there has been a proliferation of distributed object stores that offer high availability, reliability and enhanced performance for MapReduce-style workloads. However, data-intensive scientific workflows and join-intensive queries cannot always be evaluated efficiently using MapReduce-style processing without extensive data migrations, which cause network congestion and reduced query throughput. In this paper, we study the problem of computing data placement strategies that minimize the data communication costs incurred by such workloads in a distributed setting.

Many applications process data in which there exists a “conservation law” between related quantities. For example, in traffic monitoring, every incoming event, such as a packet's entering a router or a car's entering an intersection, should ideally have an immediate outgoing counterpart. We propose a new class of constraints-Conservation Rules-that express the semantics and characterize the data quality of such applications. We give confidence metrics that quantify how strongly a conservation rule holds and present approximation algorithms (with error guarantees) for the problem of discovering a concise summary of subsets of the data that satisfy a given conservation rule. Using real data, we demonstrate the utility of conservation rules and we show order-of-magnitude performance improvements of our discovery algorithms over naive approaches.

Abstract Given a very large, node‐weighted, rooted tree on, say, n nodes, if one has only enough space to display a k‐node summary of the tree, what is the most informative way to draw the tree? We define a type of weighted tree that we call a summary tree of the original tree that results from aggregating nodes of the original tree subject to certain constraints. We suggest that the best choice of which summary tree to use (among those with a fixed number of nodes) is the one that maximizes the information‐theoretic entropy of a natural probability distribution associated with the summary tree, and we provide a (pseudopolynomial‐time) dynamic‐programming algorithm to compute this maximum entropy summary tree, when the weights are integral. The result is an automated way to summarize large trees and retain as much information about them as possible, while using (and displaying) only a fraction of the original node set. We illustrate the computation and use of maximum entropy summary trees on five real data sets whose weighted tree representations vary widely in structure. We also provide an additive approximation algorithm and a greedy heuristic that are faster than the optimal algorithm, and generalize to trees with real‐valued weights.

Many applications process data in which there exists a ``conservation law'' between related quantities. For example, in traffic monitoring, every incoming event, such as a packet's entering a router or a car's entering an intersection, should ideally have an immediate outgoing counterpart. We propose a new class of constraints -- Conservation Rules -- that express the semantics and characterize the data quality of such applications. We give confidence metrics that quantify how strongly a conservation rule holds and present approximation algorithms (with error guarantees) for the problem of discovering a concise summary of subsets of the data that satisfy a given conservation rule. Using real data, we demonstrate the utility of conservation rules and we show order-of-magnitude performance improvements of our discovery algorithms over naive approaches.

This paper is a theoretical and experimental study of two related facility location problems that emanated from networking. Suppose we are given a network modeled as a directed graph G = (V, A), together with (not-necessarily-disjoint) subsets C and F of V, where C is a set of customer locations and F is a set of potential facility locations (and typically C ⊆ F). Our goal is to find a minimum sized subset F′ ⊆ F such that for every customer c ∊ C there are two locations f1, f2 ∊ F′ such that traffic from c to f1 and to f2 is routed on disjoint paths (usually shortest paths) under the network's routing protocols. Although we prove that this problem is impossible to approximate in the worst case even to within a factor of 2log1−εn for any ε > 0 (assuming no NP-complete language can be solved in quasipolynomial time), we show that the situation is much better in practice. We propose three algorithms that build solutions and determine lower bounds on the optimum solution, and evaluate them on several large real ISP topologies and on synthetic networks designed to reflect real-world LAN/WAN network structure. Our main algorithms are (1) an algorithm that performs multiple runs of a straightforward randomized greedy heuristic and returns the best result found, (2) a genetic algorithm that uses the greedy algorithm as a subroutine, and (3) a new “Double Hitting Set” algorithm. All three approaches perform surprising well, although, in practice, the most cost-effective approach is the multi-run greedy algorithm. This yields results that average within 0.7% of optimal for our synthetic instances and within 2.9% for our real-world instances, excluding the largest (and most realistic) one. For the latter instance, the other two algorithms come into their own, finding solutions that are more than three times better than those of the multi-start greedy approach. In terms of our motivating monitoring application, where every customer location can be a facility location, the results are even better. Here the above Double Hitting Set solution is 90% better than the default solution which places a monitor at each customer location - such comparisons help justify the proposed alternative monitoring scheme of [8]. Our results also show that, on average for our real-world instances, we could save an additional 18% by choosing the (shortest path) routes ourselves, rather than taking the simpler approach of relying on the network to choose them for us.

We introduce Capacitated Metric Labeling. As in Metric Labeling, we are given a weighted graph G = (V, E), a label set L, a semimetric dL on this label set, and an assignment cost function ϕ : V × L → ℜ+. The goal in Metric Labeling is to find an assignment f : V → L that minimizes a particular two-cost function. Here we add the additional restriction that each label ti receive at most li nodes, and we refer to this problem as Capacitated Metric Labeling. Allowing the problem to specify capacities on each label allows the problem to more faithfully represent the classification problems that Metric Labeling is intended to model. Our main positive result is a polynomial-time, O(log |V|)-approximation algorithm when the number of labels is fixed, which is the most natural parameter range for classification problems. We also prove that it is impossible to approximate the value of an instance of Capacitated Metric Labeling to within any finite factor, if P ≠ NP. Yet this does not address the more interesting question of how hard Capacitated Metric Labeling is to approximate when we are allowed to violate capacities. To study this question, we introduce the notion of the “congestion” of an instance of Capacitated Metric Labeling. We prove that (under certain complexity assumptions) there is no polynomial-time approximation algorithm that can approximate the congestion to within O((log|L|)1/2–ε) (for any ε > 0) and this implies as a corollary that any polynomial-time approximation algorithm that achieves a finite approximation ratio must multiplicatively violate the label capacities by Ω((log |L|)1/2–ε). We also give a O(log |L|)-approximation algorithm for congestion.

This paper studies the ``explanation problem'' for tree- and linearly-ordered array data, a problem motivated by database applications and recently solved for the one-dimensional tree-ordered case. In this paper, one is given a matrix A=(a_{ij}) whose rows and columns have semantics: special subsets of the rows and special subsets of the columns are meaningful, others are not. A submatrix in A is said to be meaningful if and only if it is the cross product of a meaningful row subset and a meaningful column subset, in which case we call it an ``allowed rectangle.'' The goal is to ``explain'' A as a sparse sum of weighted allowed rectangles. Specifically, we wish to find as few weighted allowed rectangles as possible such that, for all i,j, a_ij equals the sum of the weights of all rectangles which include cell (i,j). In this paper we consider the natural cases in which the matrix dimensions are tree-ordered or linearly-ordered. In the tree-ordered case, we are given a rooted tree $T_1$ whose leaves are the rows of $A$ and another, $T_2$, whose leaves are the columns. Nodes of the trees correspond in an obvious way to the sets of their leaf descendants. In the linearly-ordered case, a set of rows or columns is meaningful if and only if it is contiguous. For tree-ordered data, we prove the explanation problem NP-Hard and give a randomized $2$-approximation algorithm for it. For linearly-ordered data, we prove the explanation problem NP-Har and give a $2.56$-approximation algorithm. To our knowledge, these are the first results for the problem of sparsely and exactly representing matrices by weighted rectangles.

We study the prize-collecting Steiner tree (PCST), prize-collecting traveling salesman (PCTSP), and prize-collecting path (PC-Path) problems. Given a graph $(V,E)$ with a cost on each edge and a penalty (a.k.a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or path (for PC-Path) that minimizes the sum of the edge costs in the tree/cycle/path and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, a 2-approximation algorithm for each, appeared first in 1992; a 2-approximation for PC-Path appeared in 2003. The natural linear programming relaxation of PCST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present $(2-\epsilon)$-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier. Specifically, our approximation ratio for prize-collecting Steiner tree is below 1.9672.

We study the problem of finding a most profitable subset of n given tasks, each with a given start and finish time as well as profit and resource requirement, that at no time exceeds the quantity B of available resource. We show that this NP-hard Resource Allocation problem can be (1/2 − ε)-approximated in randomized polynomial time, which improves upon earlier approximation results.

The problem of Set Cover—to find the smallest subcollection of sets that covers some universe—is at the heart of many data and analysis tasks. It arises in a wide range of settings, including operations research, machine learning, planning, data quality and data mining. Although finding an optimal solution is NP-hard, the greedy algorithm is widely used, and typically finds solutions that are close to optimal. However, a direct implementation of the greedy approach, which picks the set with the largest number of uncovered items at each step, does not behave well when the input is very large and disk resident. The greedy algorithm must make many random accesses to disk, which are unpredictable and costly in comparison to linear scans. In order to scale Set Cover to large datasets, we provide a new algorithm which finds a solution that is provably close to that of greedy, but which is much more efficient to implement using modern disk technology. Our experiments show a ten-fold improvement in speed on moderately-sized datasets, and an even greater improvement on larger datasets.

In recent years the MapReduce framework has emerged as one of the most widely used parallel computing platforms for processing data on terabyte and petabyte scales.Used daily at companies such as Yahoo!, Google, Amazon, and Facebook, and adopted more recently by several universities, it allows for easy parallelization of data intensive computations over many machines.One key feature of MapReduce that differentiates it from previous models of parallel computation is that it interleaves sequential and parallel computation.We propose a model of efficient computation using the MapReduce paradigm.Since MapReduce is designed for computations over massive data sets, our model limits the number of machines and the memory per machine to be substantially sublinear in the size of the input.On the other hand, we place very loose restrictions on the computational power of of any individual machineour model allows each machine to perform sequential computations in time polynomial in the size of the original input.We compare MapReduce to the PRAM model of computation.We prove a simulation lemma showing that a large class of PRAM algorithms can be efficiently simulated via MapReduce.The strength of MapReduce, however, lies in the fact that it uses both sequential and parallel computation.We demonstrate how algorithms can take advantage of this fact to compute an MST of a dense graph in only two rounds, as opposed to Ω(log(n)) rounds needed in the standard PRAM model.We show how to evaluate a wide class of functions using the MapReduce framework.We conclude by applying this result to show how to compute some basic algorithmic problems such as undirected s-t connectivity in the MapReduce framework.

We present Data Auditor, a tool for exploring data quality and data semantics. Given a rule or an integrity constraint and a target relation, Data Auditor computes pattern tableaux , which concisely summarize subsets of the relation that (mostly) satisfy or (mostly) fail the constraint. This paper describes 1) the architecture and user interface of Data Auditor, 2) the supported constraints for testing data consistency and completeness, 3) the heuristics used by Data Auditor to "tune" a given constraint or its associated parameters for better fit with the data, and 4) several demonstration scenarios. using real data sets.

We study the prize-collecting versions of the Steiner tree, traveling salesman, and stroll (a.k.a. Path-TSP) problems (PCST, PCTSP, and PCS, respectively): given a graph (V, E) with costs on each edge and a penalty (a.k.a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or stroll (for PCS) that minimizes the sum of the edge costs in the tree/cycle/stroll and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, giving a 2-approximation algorithm for each, appeared first in 1992. (A 2-approximation for PCS appeared in 2003.) The natural linear programming (LP) relaxation of PCST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present (2 · ¿)-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier.

We study scheduling algorithms for loading data feeds into real time data warehouses, which are used in applications such as IP network monitoring, online financial trading, and credit card fraud detection. In these applications, the warehouse collects a large number of streaming data feeds that are generated by external sources and arrive asynchronously. Data for each table are generated at a constant rate, different tables possibly at different rates. For each data feed, the arrival of new data triggers an update that seeks to append the new data to the corresponding table; if multiple updates are pending for the same table, they are batched together before being loaded. At time τ, if a table has been updated with information up to time r≤τ, its staleness is defined as τ--r.

We study sequential dependencies that express the semantics of data with ordered domains and help identify quality problems with such data. Given an interval g , we write X → g Y to denote that the difference between the Y -attribute values of any two consecutive records, when sorted on X , must be in g. For example, time → (0,∞) sequence_number indicates that sequence numbers are strictly increasing over time, whereas sequence_number → [4, 5] time means that the time "gaps" between consecutive sequence numbers are between 4 and 5. Sequential dependencies express relationships between ordered attributes, and identify missing (gaps too large), extraneous (gaps too small) and out-of-order data. To make sequential dependencies applicable to real-world data, we relax their requirements and allow them to hold approximately (with some exceptions) and conditionally (on various subsets of the data). This paper proposes the notion of conditional approximate sequential dependencies and provides an efficient framework for discovering pattern tableaux, which are compact representations of the subsets of the data (i.e., ranges of values of the ordered attributes) that satisfy the underlying dependency. We present analyses of our proposed algorithms, and experiments on real data demonstrating the efficiency and utility of our framework.

We study the fundamental classification problems 0-Extension and Metric Labeling. A generalization of Multiway Cut, 0-Extension is closely related to partitioning problems in graph theory and to Lipschitz extensions in Banach spaces; its generalization Metric Labeling is motivated by applications in computer vision. Researchers had proposed using earthmover metrics to get polynomial–time-solvable relaxations for these problems. A conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant. We prove (1) that the integrality ratio of the earthmover relaxation for Metric Labeling is $\Omega(\log k)$ (which is asymptotically tight), k being the number of labels, whereas the best previous lower bound on the integrality ratio was only constant; (2) that the integrality ratio of the earthmover relaxation for 0-Extension is $\Omega(\sqrt{\log k})$, k being the number of terminals (it was known to be $O((\log k)/\log\log k)$), whereas the best previous lower bound was only constant; (3) that for no $\epsilon>0$ is there a polynomial-time $O((\log n)^{1/4-\epsilon})$-approximation algorithm for 0-Extension, n being the number of vertices, unless NP$\subseteq$DTIME$(n^{\mathrm{poly}(\log n)})$, whereas the strongest inapproximability result known before was only MAX SNP-hardness; and (4) that there is a polynomial-time approximation algorithm for 0-Extension with performance ratio $O(\sqrt{\mathrm{diam}(d)})$, where $\mathrm{diam}(d)$ is the ratio of the largest to smallest nonzero distances in the terminal metric.

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

Conditional functional dependencies (CFDs) have recently been proposed as a useful integrity constraint to summarize data semantics and identify data inconsistencies. A CFD augments a functional dependency (FD) with a pattern tableau that defines the context (i.e., the subset of tuples) in which the underlying FD holds. While many aspects of CFDs have been studied, including static analysis and detecting and repairing violations, there has not been prior work on generating pattern tableaux, which is critical to realize the full potential of CFDs. This paper is the first to formally characterize a "good" pattern tableau, based on naturally desirable properties of support, confidence and parsimony. We show that the problem of generating an optimal tableau for a given FD is NP-complete but can be approximated in polynomial time via a greedy algorithm. For large data sets, we propose an "on-demand" algorithm providing the same approximation bound, that outperforms the basic greedy algorithm in running time by an order of magnitude. For ordered attributes, we propose the range tableau as a generalization of a pattern tableau, which can achieve even more parsimony. The effectiveness and efficiency of our techniques are experimentally demonstrated on real data.

We study the fundamental classification problems O-EXTENSION and METRIC LABELING. MINIMUM WEIGHT TRIANGULATION is closely related to partitioning problems in graph theory and to Lipschitz extensions in Banach spaces; its generalization METRIC LABELING is motivated by applications in computer vision. Researchers had proposed using earthmover metrics to get polynomial time-solvable relaxations for these problems. A conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant.We prove

We prove that if a linear error-correcting code C:{0, 1} n →{0, 1} m is such that a bit of the message can be probabilistically reconstructed by looking at two entries of a corrupted codeword, then m = 2Ω (n). We also present several extensions of this result. We show a reduction from the complexity of one-round, information-theoretic Private Information Retrieval Systems (with two servers) to Locally Decodable Codes, and conclude that if all the servers’ answers are linear combinations of the database content, then t = Ω (n/2 a ), where t is the length of the user’s query and a is the length of the servers’ answers. Actually, 2 a can be replaced by O(a k ), where k is the number of bit locations in the answer that are actually inspected in the reconstruction.

The traveling salesman problem comes in two variants. The symmetric version (STSP) assumes that the cost c/sub ij/ of going to city i to city j is equal to c/sub ji/, while the more general asymmetric version (ATSP) does not make this assumption. In both cases, it is usually assumed that we are in the metric case, i.e., the costs satisfy the triangle inequality: c/sub ij/ + c/sub jk/ /spl ges/ c/sub ik/ for all i, j, k. In this assumption, we improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP (with triangle inequality) from 4/3 to 2.

Dynamic storage allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L= is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that $\ensuremath{\text{\it OPT}}\ge \ensuremath{\text{\it LOAD}}$; previous work showed that $\ensuremath{\text{\it OPT}}\le 3\cdot LOAD. We continue the study of the relationship between OPT and LOAD, proving that OPT=L+O((h max /L) 1/7 )L, where h max is the maximum job height. Conversely, we prove that for any $\epsilon > 0$, there exists a c>0 such that for all sufficiently large integers $h_{\max}$, there is a dynamic storage allocation instance with maximum job height $h_{\max}$, maximum load at most L, and $\ensuremath{\text{\it OPT}}\geq L+c(h_{\max}/L)^{1/2+\epsilon}L$, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a $(2+\epsilon)$-approximation algorithm for the general case and polynomial-time approximation schemes for several natural special cases.

In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of Dahlhaus et al. [SIAM J. Comput.}, 23 (1994), pp. 864--894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14--23]. We present approximation algorithms for {\sc 0-Extension}. In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 (1998), pp. 71--101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [SIAM J. Comput.}, 25 (1996), pp. 235--251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least $c \sqrt{\lg k}$ for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations.

DYNAMIC STORAGE ALLOCATION is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L=LOAD is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT≥LOAD; previous work showed that OPT≤ 3• LOAD. We continue the study of the relationship between OPT and LOAD, proving that OPT=L+O((hmax/L)1/7)L, where hmax is the maximum job height. Conversely, we prove that for any ε>0, there exists a c>0 such that for all sufficiently large integers hmax, there is a DYNAMIC STORAGE ALLOCATION instance with maximum job height hmax, maximum load at most L, and OPT≥ L+c(hmax/L)1/2+εL, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for DYNAMIC STORAGE ALLOCATION.

We propose a natural, mathematically tractable model of TCP which captures both its additive-increase, multiplicative-decrease behavior and its feedback mechanism. Neither a fluid nor a mean-field model, our model does not explicitly model the loss process; the losses are entirely determined by the rates of the sources at the time of buffer overflow. The system involves two sources competing to send packets into one recipient buffer of size B, from which bytes are drained at the rate of d per step. We prove that for many choices of the pairs (B,d), the long term behavior of the system is fractal. We conjecture that this fact continues to hold for all B > d and d > 2.

The seminal paper of F.T. Leighton and S. Rao (1988) and subsequent papers presented approximate min-max theorems relating multicommodity flow values and cut capacities in undirected networks, developed the divide-and-conquer method for designing approximation algorithms, and generated novel tools for utilizing linear programming relaxations. Yet, despite persistent research efforts, these achievements could not be extended to directed networks, excluding a few cases that are "symmetric" and therefore similar to undirected networks. The paper is an attempt to remedy the situation. We consider the problem of finding a minimum multicut in a directed multicommodity flow network, and give the first nontrivial upper bounds on the maxflow-to-min multicut ratio. Our results are algorithmic, demonstrating nontrivial approximation guarantees.

A lower bound of $\Omega(\sqrt{\log k / \log \log k})$ is proved for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (having at least k+1 points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of $\Omega(\log \log k)$ for arbitrary metric spaces [H.J. Karloff, Y. Rabani, and Y. Ravid, SIAM J. Comput., 23 (1994), pp. 293--312] and more closely approaches the conjectured lower bound of $\Omega(\log k)$. For the server problem on k+1 equally spaced points on a line, which corresponds to a natural motion-planning problem, a lower bound of $\Omega(\frac{\log k}{\log \log k})$ is obtained. The results are deduced from a general decomposition theorem for a simpler version of both the k-server and the metrical task system problems, called the "pursuit-evasion game." It is shown that if a metric space $\cal M$ can be decomposed into two spaces $\cal M_L$ and $\cal M_R$ such that the distance between them is sufficiently large compared to their diameter, then the competitive ratio for this game on $\cal M$ can be expressed nearly exactly in terms of the ratios on each of the two subspaces. This yields a divide-and-conquer approach to bounding the competitive ratio of a space.

A commonly used and powerful technique for improving query response time over very large databases is to precompute ('Lmaterialize") frequently' asked queries ("views").

Local search with k-change neighborhoods is perhaps the oldest and most widely used heuristic method for the traveling salesman problem, yet almost no theoretical performance guarantees for it were previously known. This paper develops several results, some worst-case and some probabilistic, on the performance of 2- and k-opt local search for the traveling salesman problem, with respect to both the quality of the solution and the speed with which it is obtained.

The celebrated semidefinite programming algorithm for MAX CUT introduced by Goemans and Williamson was known to have a performance ratio of at least $\alpha=\frac 2 {\pi} \min_{0 < \theta\le \pi} \frac \theta {1-\cos \theta}$ ($0.87856 < \alpha < 0.87857$); the exact performance ratio was unknown. We prove that the performance ratio of their algorithm is exactly $\alpha$. Furthermore, we show that it is impossible to add valid linear constraints to improve the performance ratio.

Given an undirected graph wit.h edge co&s and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest.~iULTIW.~yCUT is the problem of finding a multiway cut of minimum cost..Previously, a very simple combinatorial algorithm due to Dahlhaus, Johnson, Papadimitriou, Seymour, and %nnr-lkakis gave a performance guarantee of 2 (1 -$), In this paper, we present a new linear programming rslax-&ion for ~fULTIW&Y CUT and a new approximation dgorithm based on it.The algorithm breaks the threshold of 2 for approximating MULTIWAY CUT, achieving a performance ratio of at.most 1.5 -$.This improves the previous result for every value of k.In particular, for k = 3 we get a ratio ofZ

A layered graph is a connected graph whose vertices are partitioned into sets L 0 =s, L 1 , L 2 ,..., and whose edges, which have nonnegative integral weights, run between consecutive layers. Its width is $\max\{|L_i|\}$. In the on-line layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. We give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. We give a deterministic on-line algorithm which is O(9 w )-competitive on width-w graphs and prove that for no w can a deterministic on-line algorithm have a competitive ratio better than 2 w-2 on width-w graphs. We prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized on-line layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, we give a randomized on-line algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor.

We describe a randomized approximation algorithm which takes an instance of MAX 3SAT as input. If the instance-a collection of clauses each of length at most three-is satisfiable, then the expected weight of the assignment found is at least 7/8 of optimal. We provide strong evidence (but not a proof) that the algorithm performs equally well on arbitrary MAX 3SAT instances. Our algorithm uses semidefinite programming and may be seen as a sequel to the MAX CUT algorithm of Goemans and Williamson (1995) and the MAX 2SAT algorithm of Feige and Goemans (1995). Though the algorithm itself is fairly simple, its analysis is quite complicated as it involves the computation of volumes of spherical tetrahedra. Hastad has recently shown that, assuming P/spl ne/NP, no polynomial-time algorithm for MAX 3SAT can achieve a performance ratio exceeding 7/8, even when restricted to satisfiable instances of the problem. Our algorithm is therefore optimal in this sense. We also describe a method of obtaining direct semidefinite relaxations of any constraint satisfaction problem of the form MAX CSP(F), where F is a finite family of Boolean functions. Our relaxations are the strongest possible within a natural class of semidefinite relaxations.

The celebrated semidefinite programming algorithm for MAX CUT introduced by Goemans and Williamson was known to have a performance ratio of at least α = 2 π min0<θ≤π θ 1−cos θ (0.87856 < α < 0.87857); the exact performance ratio was unknown. We prove that the performance ratio of their algorithm is exactly α. Furthermore, we show that it is impossible to add valid linear constraints to improve the performance ratio.

IndependentRandom

In this paper, the authors prove lower bounds on the competitive ratio of randomized algorithms for two on-line problems: the k-server problem, suggested by Manasse, McGeoch, and Sleator [Competitive lgorithms for on-line problems, J. Algorithms, 11 (1990), pp. 208–230], and an on-line motion-planning problem due to Papadimitriou and Yannakakis [Shortest paths without a map, Lecture Notes in Comput. Sci. 372, Springer-Verlag, New York, 1989, pp. 610–620]. The authors prove, against an oblivious adversary, 1. an $\Omega \log k$ lower bound on the competitive ratio of any randomized on-line k-server algorithm in any sufficiently large metric space, 2. an $\Omega (\log \log k)$ lower bound on the competitive ratio of any randomized on-line k-server algorithm in any metric space with at least $k + 1$ points, and 3. an $\Omega (\log \log n)$ lower bound on the competitive ratio of any on-line motion-planning algorithm for a scene with n obstacles. Previously, no superconstant lower bound on the competitive ratio of randomized on-line algorithms was known for any of these problems.

Randomizedalgorithms are analyzed as if unlimited amounts of perfect randomness were available, while pseudorandom number generation is usually studied from the perspective of cryptographic security or for the statistical properties of the numbers generated.Bach proposed studying the interaction between pseudorandom number generators and randomized algorithms.This paper follows Bach's lead; the authors assume that a (small) random seed is available to start up a simple pseudorandom number generator that is then used for the randomized algorithm.Randomized algorithms are studied for (1) sorting, (2) selection.and (3) obhvious routing in networks.

The authors prove a lower bound of Omega ( square root logk/loglogk) for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (of at least k+1 points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of Omega (loglogk) for arbitrary metric spaces, more closely approaching the conjectured lower bound of Omega (logk). They also prove a lower bound of Omega (/sup logk///sub loglogk/) for the server problem on k+1 equally-spaced points on a line, which corresponds to some natural motion-planning problems.>

We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the make span, the completion time of the last job. In the on-line version, as soon as job j arrives, it must be assigned immediately to one of the m machines.

A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP = NEXP [4].

A layered graph is a connected, weighted graph whose vertices are partitioned into sets L/sub 0/=(s), L/sub 1/, L/sub 2/, . . ., and whose edges run between consecutive layers. Its width is max( mod L/sub i/ mod ). In the online layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. The authors give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. They give a deterministic online algorithm that is O(9w)-competitive on width-w graphs and prove that for no w can a deterministic online algorithm have a competitive ratio better than 2w/sup -2/ on width-w graphs. They prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized online layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, they give a randomized online algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor.>

No abstract available.

In the k-server problem, one must choose how k mobile servers will serve each of a sequence of requests, making decisions in an online manner. An optimal deterministic online strategy is exhibited when the requests fall on the real line. For the weighted-cache problem, in which the cost of moving to x from any other point is $w( x )$, the weight of x, an optimal deterministic algorithm is also provided. The nonexistence of competitive algorithms for the asymmetric two-server problem and of memoryless algorithms for the weighted-cache problem is proved. A fast algorithm for oflline computing of an optimal schedule is given, and it is shown that finding an optimal offline schedule is at least as hard as the assignment problem.

An algebraic technique for the construction of interactive proof systems is proposed. The technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. For the proof, a method is developed for reducing the problem of verifying the value of a low-degree polynomial at two points to verifying the value at one new point. The results have implications for program checking, verification, and self-correction.>

Given an undirected n-vertex graph G and a set of n points in Rd, we wish to embed the vertices of G onto the points so as to minimize the total embedded edge length. Important special cases of this geometric embedding problem are those in which G is a binary tree, a cycle, or a star. We give fast approximation algorithms for embedding these graphs on the line and in the plane in several metrics. Our principal techniques are: a notion of “approximate geometric sorting” that can be computed in linear time, and fast approximation schemes for the minimum spanning tree problem in the plane. We expect that these approximation techniques can be applied to many geometric problems besides the embedding problem. We give the example of approximating the convex hull of a set of points in the plane.

Where S is a set of N points in the unit square, let $t(S)$ be the Euclidean length of the shortest traveling salesman tour through S. Let $t_N = \max_st (S)$. We improve Few’s bound [Mathematika, 2 (1955), pp. 141–144] that $t_N \leqq \sqrt {2N} + 7/4$ to $t_N \leqq \alpha \sqrt N + 11$, where $\alpha /\sqrt 2 < 0.984$.

Randomized algorithms are analyzed as if unlimited amounts of perfect randomness were available, while pseudorandom number generation is usually studied from the perspective of cryptographic security. Bach recently proposed studying the interaction between pseudorandom number generators and randomized algorithms. We follow Bach's lead; we assume that a (small) random seed is available to start up a simple pseudorandom number generator which is then used for the randomized algorithm. We study randomized algorithms for (1) sorting; (2) selection; and (3) oblivious routing in networks.