The memory and storage hierarchy in database systems is currently undergoing a radical evolution in the context of Big Data systems. SQL-on-Hadoop systems share data with other applications in the Big Data ecosystem by storing their data in HDFS, using open file formats. However, they do not provide automatic caching mechanisms for storing data in memory. In this paper, we describe the architecture of IBM Big SQL and its use of the HDFS cache as an alternative to the traditional buffer pool, allowing in-memory data to be shared with other Big Data applications. We design novel adaptive caching algorithms for Big SQL tailored to the challenges of such an external cache scenario. Our experimental evaluation shows that only our adaptive algorithms perform well for diverse workload characteristics, and are able to adapt to evolving data access patterns. Finally, we discuss our experiences in addressing the new challenges imposed by external caching and summarize our insights about how to direct ongoing architectural evolution of external caching mechanisms.

Machine learning relies on the assumption that unseen test instances of a classification problem follow the same distribution as observed training data. However, this principle can break down when machine learning is used to make important decisions about the welfare (employment, education, health) of strategic individuals. Knowing information about the classifier, such individuals may manipulate their attributes in order to obtain a better classification outcome. As a result of this behavior -- often referred to as gaming -- the performance of the classifier may deteriorate sharply. Indeed, gaming is a well-known obstacle for using machine learning methods in practice; in financial policy-making, the problem is widely known as Goodhart's law. In this paper, we formalize the problem, and pursue algorithms for learning classifiers that are robust to gaming.

We present an intelligent, crowd-powered information collection system that automatically identifies and asks targeted strangers on Twitter for desired information (e.g., current wait time at a nightclub). Our work includes three parts. First, we identify a set of features that characterize one's willingness and readiness to respond based on their exhibited social behavior, including the content of their tweets and social interaction patterns. Second, we use the identified features to build a statistical model that predicts one's likelihood to respond to information solicitations. Third, we develop a recommendation algorithm that selects a set of targeted strangers using the probabilities computed by our statistical model with the goal to maximize the over-all response rate. Our experiments, including several in the real world, demonstrate the effectiveness of our work.

We propose a dynamic faceted search system for discovery-driven analysis on data with both textual content and structured attributes. From a keyword query, we want to dynamically select a small set of "interesting" attributes and present aggregates on them to a user. Similar to work in OLAP exploration, we define "interestingness" as how surprising an aggregated value is, based on a given expectation. We make two new contributions by proposing a novel "navigational" expectation that's particularly useful in the context of faceted search, and a novel interestingness measure through judicious application of p-values. Through a user survey, we find the new expectation and interestingness metric quite effective. We develop an efficient dynamic faceted search system by improving a popular open source engine, Solr. Our system exploits compressed bitmaps for caching the posting lists in an inverted index, and a novel directory structure called a bitset tree for fast bitset intersection. We conduct a comprehensive experimental study on large real data sets and show that our engine performs 2 to 3 times faster than Solr.

In this paper we focus on traitor tracing technologies for the anonymous re-broadcasting attack where the attackers re-distribute the per-content encrypting key or the decrypted plain content. To defend against an anonymous attack, content is usually built with different variations. For example, content is divided into multiple segments, each segment comes with multiple variations, and each variation is differently encrypted. Each user/player can only play back one variation per segment through the content.

When comparing alternative query execution plans (QEPs), a cost-based query optimizer in a relational database management system needs to estimate the selectivity of conjunctive predicates. To avoid inaccurate independence assumptions, modern optimizers try to exploit multivariate statistics (MVS) that provide knowledge about joint frequencies in a table of a relation. Because the complete joint distribution is almost always too large to store, optimizers are given only partial knowledge about this distribution. As a result, there exist multiple, non-equivalent ways to estimate the selectivity of a conjunctive predicate. To consistently combine the partial knowledge during the estimation process, existing optimizers employ cumbersome ad hoc heuristics. These methods unjustifiably ignore valuable information, and the optimizer tends to favor QEPs for which the least information is available. This bias problem yields poor QEP quality and performance. We demonstrate MAXENT, a novel approach based on the maximum entropy principle, prototyped in IBM DB2 LUW. We illustrate MAXENT's ability to consistently estimate the selectivity of conjunctive predicates on a per-table basis. In contrast to the DB2 optimizer's current ad hoc methods, we show how MAXENT exploits all available information about the joint column distribution and thus avoids the bias problem. For some complex queries against a real-world database, we show that MAXENT improves selectivity estimates by orders of magnitude relative to the current DB2 optimizer, and also show how these improved estimate influence plan choices as well as query execution times.

“Experts algorithms” constitute a methodology for choosing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the environment. An experts algorithm has access to a set of strategies (“experts”), each of which may recommend which action to choose. The algorithm learns how to combine the recommendations of individual experts so that, in the long run, for any fixed sequence of states of the environment, it does as well as the best expert would have done relative to the same sequence. This methodology may not be suitable for situations where the evolution of states of the environment depends on past chosen actions, as is usually the case, for example, in a repeated non-zero-sum game.A general exploration-exploitation experts method is presented along with a proper definition of value. The definition is shown to be adequate in that it both captures the impact of an expert's actions on the environment and is learnable. The new experts method is quite different from previously proposed experts algorithms. It represents a shift from the paradigms of regret minimization and myopic optimization to consideration of the long-term effect of a player's actions on the environment. The importance of this shift is demonstrated by the fact that this algorithm is capable of inducing cooperation in the repeated Prisoner's Dilemma game, whereas previous experts algorithms converge to the suboptimal non-cooperative play. The method is shown to asymptotically perform as well as the best available expert. Several variants are analyzed from the viewpoint of the exploration-exploitation tradeoff, including explore-then-exploit, polynomially vanishing exploration, constant-frequency exploration, and constant-size exploration phases. Complexity and performance bounds are proven.

A reactive environment is one that responds to the actions of an agent rather than evolving obliviously. In reactive environments, experts algorithms must balance exploration and exploitation of experts more carefully than in oblivious ones. In addition, a more subtle definition of a learnable value of an expert is required. A general exploration-exploitation experts method is presented along with a proper definition of value. The method is shown to asymptotically perform as well as the best available expert. Several variants are analyzed from the viewpoint of the exploration-exploitation tradeoff, including explore-then-exploit, polynomially vanishing exploration, constant-frequency exploration, and constant-size explo- ration phases. Complexity and performance bounds are proven.

The so-called “experts algorithms” constitute a methodology for choos- ing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the environment. An experts algorithm has access to a set of strategies (“experts”), each of which may recommend which action to choose. The algorithm learns how to com- bine the recommendations of individual experts so that, in the long run, for any fixed sequence of states of the environment, it does as well as the best expert would have done relative to the same sequence. This method- ology may not be suitable for situations where the evolution of states of the environment depends on past chosen actions, as is usually the case, for example, in a repeated non-zero-sum game. A new experts algorithm is presented and analyzed in the context of re- peated games. It is shown that asymptotically, under certain conditions, it performs as well as the best available expert. This algorithm is quite different from previously proposed experts algorithms. It represents a shift from the paradigms of regret minimization and myopic optimiza- tion to consideration of the long-term effect of a player’s actions on the opponent’s actions or the environment. The importance of this shift is demonstrated by the fact that this algorithm is capable of inducing co- operation in the repeated Prisoner’s Dilemma game, whereas previous experts algorithms converge to the suboptimal non-cooperative play.

The basis of many systems that integrate data from multiple sources is a set of correspondences between source schemata and a target schema. Correspondences express a relationship between sets of source attributes, possibly from multiple sources, and a set of target attributes. Clio is an integration tool that assists users in defining value correspondences between attributes. In real life scenarios there may be many sources and the source relations may have many attributes. Users can get lost and might miss or be unable to find some correspondences. Also, in many real life schemata the attribute names reveal little or nothing about the semantics of the data values. Only the data values in the attribute columns can convey the semantic meaning of the attribute. Our work relieves users of the problems of too many attributes and meaningless attribute names, by automatically suggesting correspondences between source and target attributes. For each attribute, we analyze the data values and derive a set of features.

Physical database design is important for query performance in a shared-nothing parallel database system, in which data is horizontally partitioned among multiple independent nodes. We seek to automate the process of data partitioning. Given a workload of SQL statements, we seek to determine automatically how to partition the base data across multiple nodes to achieve overall optimal (or close to optimal) performance for that workload. Previous attempts use heuristic rules to make those decisions. These approaches fail to consider all of the interdependent aspects of query performance typically modeled by today's sophisticated query optimizers.We present a comprehensive solution to the problem that has been tightly integrated with the optimizer of a commercial shared-nothing parallel database system. Our approach uses the query optimizer itself both to recommend candidate partitions for each table that will benefit each query in the workload, and to evaluate various combinations of these candidates. We compare a rank-based enumeration method with a random-based one. Our experimental results show that the former is more effective.

In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the final decision about each object is made only on the basis of its rank relative to the ones already seen. Variants of the problem depend on the goal: either maximize the probability of accepting the best k objects, or minimize the expectation of the sum of the ranks (or powers of ranks) of the accepted objects. The problem and its generalizations are at the core of tasks with a large data set, in which it may be impractical to backtrack and select previous choices. Optimal algorithms for the special case of k = 1 are well known. Partial solutions for the first variant with general k are also known. In contrast, an explicit solution for the second variant with general k has not been known. It seems that the fact that the expected sum of powers of the ranks of selected items is bounded as n tends to infinity has been known to follow from standard results. We derive our results by obtaining explicit algorithms. For each $z \geq 1$, the resulting expected sum of the zth powers of the ranks of the selected objects is at most $k^{z + 1}/(z + 1) + C(z) \cdot k^{z + 0.5}\log k$, where log k \equiv \max\{1, \log_2 k\}$, whereas the best possible value at all is k z + 1/(z + 1) + O(k z ). Our methods are very intuitive and apply to some generalizations. We also derive a lower bound on the trade-off between the probability of selecting the best object and the expected rank of the selected object.

The authors address the problem of estimating the performance of loop tiling, an important program transformation for improved memory hierarchy utilization. We introduce an analytical model for estimating the memory cost of a loop nest as a rational polynomial in tile size variables. We also present a constant-time algorithm for finding an optimal solution to the model (i.e., for selecting optimal tile sizes) for the case of doubly nested loops. This solution can be applied to tiling of three loops by performing an iterative search on the value of the first tile size variable, and using the constant-time algorithm at each point in the search to obtain optimal tile size values for the remaining two loops. Our solution is efficient enough to be used in production-quality optimizing compilers, and has been implemented in the IBM XL Fortran product compilers. This solution can also be used by processor designers to efficiently predict the performance of a set of tiled loops for a range of memory hierarchy parameters.

A range query applies an aggregation operation over all selected cells of an OLAP data cube where the selection is specified by providing ranges of values for numeric dimensions. We present fast algorithms for range queries for two types of aggregation operations: SUM and MAX. These two operations cover techniques required for most popular aggregation operations, such as those supported by SQL.

Much of the computation involved in parallel programs occurs within loops, either nested loops as in parallel scientific applications or collections of loops as in stream-based applications. Loop fusion is a well-known program transformation that has shown to be effective in improving data locality in parallel programs by reducing inter-processor communication and improving register and cache locality. Weighted loop fusion is the problem of finding a legal partition of loop nests into fusible clusters so as to minimize the total inter-cluster weights. The loop nests may contain parallel or sequential loops; care is taken to ensure that a parallel loop does not get serialized after fusion. It has been shown in past work that the weighted loop fusion problem is NP-hard. Despite the NP-hardness property, we show how optimal solutions can be found efficiently (i.e., within the compile-time constraints of a product-quality optimizing compiler) for weighted loop fusion problem sizes that occ...

This paper addresses the issues of (1) automatically segmenting color images into foreground and background regions and (2) efficiently encoding segmented background for the purpose of storage, indexing, and query in large image databases. The work was motivated by the need of automatically "populating" large image databases. The following issues are discussed in this paper: (1) the model used to approximate relatively smooth color image background, (2) the approach developed for robust extraction of model parameters, (3) color background reconstruction and segmentation. Some experimental results are given to illustrate the effectiveness of the approach. The benefits of the method in efficient content-based encoding, indexing, and query in an image database environment are presented.

This research addresses the issue of automatically segmenting color images into foreground (F) and background (B) regions with the assumption that background regions are relatively smooth but may have gradually varying colors or be slightly textured. A multi-level segmentation scheme is used that involves color clustering, unsupervised segmentation using MDL (minimum description length) principle, edge-based F/B separation, integrated initial F/B segmentation, background modeling, and final F/B separation. The approach has been tested on more than 100 images. Some of the experimental results are presented in this paper.

It is shown that for any fixed number of variables, linear-programming problems with n linear inequalities can be solved deterministically by n parallel processors in sublogarithmic time. The parallel time bound (counting only the arithmetic operations) is $O((\log \log n)^d )$, where d is the number of variables. In the one-dimensional case, this bound is optimal. If we take into account the operations needed for processor allocation, the time bound is $O((\log \log n)^{d + c} )$, where c is an absolute constant.

In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the final decision about each object is made only on the basis of its rank relative to the ones already seen. Variants of the problem depend on the goal: either maximize the probability of accepting the best k objects, or minimize the expectation of the sum of the ranks (or powers of ranks) of the accepted objects. The problem and its generalizations are at the core of tasks with a large data set, in which it may be impractical to backtrack and select previous choices. Optimal algorithms for the special case of k=1 are well known. Partial solutions for the first variant with general k are also known. In contrast, an explicit solution for the second variant with general k has not been known; even the question of whether or not the expected sum of powers of the ranks of selected items tends to infinity with n has been unresolved. We answer these open questions by obtaining explicit algorithms. For each z/spl ges/1, the resulting expected sum of the zth powers of the ranks of the selected objects is at most k/sup z+1//(z+1)+C(z)/spl middot/k/sup z+0.5/log k, whereas the best possible value at all is k/sup z+1//(z+1)+O(k/sup z/). Our methods are very intuitive and apply to some generalizations. We also derive a lower bound on the trade-off between the probability of selecting the best object and its expected rank.

Interactions among agents can be conveniently described by game trees. In order to analyze a game, it is important to derive optimal (or equilibrium) strategies for the different players. The standard approach to finding such strategies in games with imperfect information is, in general, computationally intractable. The approach is to generate the normal form of the game (the matrix containing the payoff for each strategy combination), and then solve a linear program (LP) or a linear complementarity problem (LCP). The size of the normal form, however, is typically exponential in the size of the game tree, thus making this method impractical in all but the simplest cases. This paper describes a new representation of strategies which results in a practical linear formulation of the problem of two-player games with perfect recall (i.e., games where players never forget anything, which is a standard assumption). Standard LP or LCP solvers can then be applied to find optimal randomized strategies. The resulting algorithms are, in general, exponentially better than the standard ones, both in terms of time and in terms of space.

For any fixed dimension d , the linear programming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM with O ( n ) processors almost surely in constant time. The algorithm always finds the correct solution. With nd /log 2 d processors, the probability that the algorithm will not finish within O ( d 2 log 2 d ) time tends to zero exponentially with n . — Authors' Abstract

The authors show that a system of m linear inequalities with n variables, where each inequality involves at most two variables, can be solved in $\tilde O(mn^2 )$ time (we denote $\tilde O(f) = O(f{\operatorname{polylog}} n{\operatorname{polylog}} m))$ deterministically, and in $\tilde O(n^3 + mn)$ expected time using randomization. Parallel implementations of these algorithms run in $\tilde O(n)$ time, where the deterministic algorithm uses $\tilde O(mn)$ processors and the randomized algorithm uses $\tilde O(n^2 + m)$ processors. The bounds significantly improve over previous algorithms. The randomized algorithm is based on novel insights into the structure of the problem.

The subject of this paper is finding small sample spaces for joint distributions of n discrete random variables. Such distributions are often only required to obey a certain limited set of constraints of the form ${\text{Pr}}( {{\text{Event}}} ) = \pi$. It is shown that the problem of deciding whether there exists any distribution satisfying a given set of constraints is NP-hard. However, if the constraints are consistent, then there exists a distribution satisfying them, which is supported by a “small” sample space (one whose cardinality is equal to the number of constraints). For the important case of independence constraints, where the constraints have a certain form and are consistent with a joint distribution of independent random variables, a small sample space can be constructed in polynomial time. This last result can be used to derandomize algorithms; this is demonstrated by an application to the problem of finding large independent sets in sparse hypergraphs.

The subject of this paper is finding small sample spaces for joint distributions of n discrete random variables.Such distributions are often only required to obey a certain limited set of constraints of the form Pr(Euent) = zr.We show that the problem of deciding whether there exists any distribution satisfying a given set of constraints is NP-hard.However, if the constraints are consistent, then there exists a distribution satisfying them which is supported by a "small" sample space (one whose cardinality is equal to the number of constraints).For the important case of independence constraints, where the constraints have a certain form and are consistent with a joint distribution of independent random variables, a small sample space can be constructed in polynomial time.This last result can be used to derandomize algorithms; we delnonstrate this by an application to the problem of finding large independent sets in sparse hypergraphs.

This paper is concerned with the problem of recognizing, m a graph with rational vector-weights associates with the edges, the existence of a cycle whose total weight is the zero vector.This problem is known to be equivalent to the problem of recognizing the existence of cycles in periodic (dynamic) graphs and to the validity of systems of recursive formulas.It was previously conjectured that combinatorial algorithms exist for the casesof two-and three-dimensional vector-weights.It is shown that strongly polynomial algorithms exist for any fixed dimension d.Moreover, these algorithms also estabhsh membership in the class.1Y.On the other hand, ]t is shown that when the dimension of the weights IS not fixed, the problem IS equivalent to the general linear programming problem under strongly polynomial and Iogspace reductions, The algorithms presented here solve the cycle detection problem by reducing it to instances of the parametric mmimum cycle problem.In the latter, graphs with edge-weights that are linear functions of d parameters are considered.The goal, roughly. is to find an assignment of the parameters such that the value of the minimum weight cycle is maximized.The technique we used in order to obtain strongly polynomial algorithms for the parametric minimum cycle problem N a general tool applicable to parametric extensions of a variety of other problems.

It is shown that for any fixed number of variables, the linear programming problems with n linear inequalities can be solved deterministically by n parallel processors in sub-logarithmic time. The parallel time bound is O((log log n)d) where d is the number of variables. In the one-dimensional case this bound is optimal.

We show that a system of m linear inequalities wit h n variables, where each inequality involves at most two variables, can be solved det erministically in O(mn log m + mnz log2 n) time. A randomized O(n3 log n + mn log3 n log m + mn log5 n) time algorithm is given for the case where in every inequality the two nonzero coefficients have opposite signs (monotone systems). This algorithm improves the known time bounds for the incapacitated generalized transshipment problem, with many sources and no sinks. We also present a new algorithm that solves the capacitated generalized flow problem by iteratively solving monotone systems. Combined with the improved bound, it yields the fastest known algorithm for the problem which does not rely on the theoretically fast matrix multiplication algorithms. This approach also yields the first strongly polynomial time bound for approximating the maximum generalized flow within any constant factor.

We show that if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for the general linear programming problem. On the other hand, we give a strongly polynomial time algorithm that finds such a basis, given any pair of optimal solutions (not necessarily basic) for the primal and the dual problems. Such an algorithm is needed when one is using an interior point method and is interested in finding a basis which is both primal- and dual-optimal. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

It is shown that, for any fixed dimension d, the linear programming problem with n inequality constraints can be solvent on a probabilistic CRCW PRAM (concurrent-read-concurrent-write parallel random-access machine) with O(n) processors almost surely in constant time. The algorithm always finds the correct solution. With nd/log/sup 2/d processors, the probability that the algorithm will not finish within O(d/sup 2/log/sup 2/d) time tends to zero exponentially with n.>

The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed. Let n and m denote the number of variables and the number of inequalities, respectively, in a linear programming problem. It is assumed that all inequalities are weak. Under the concurrent-read-exclusive-write PRAM model, an $O((\log m + \log^2 n) \log^2 n)$-time parallel algorithm for deciding feasibility is described. It requires $mn^{O(\log n)}$ processors in the worst case, though it is not known whether this bound is tight. When the problem is feasible, a solution can be computed within the same complexity. Moreover, linear programming problems with at most two nonzero coefficients in the objective function can be solved in poly-log time on a similar number of processors. Consequently, all these problems can be solved sequentially with only $O((\log m + \log ^2 n)^2 \log ^2 n)$ space. (These bounds assume that numbers take $O(1)$ space, and arithmetic on them takes $O(1)$ time; the problem can still be solved in poly-log space as a function of the input size even if a Turing machine model with rational input is used instead.) It is also shown that if the underlying graph has bounded tree-width and an underlying tree is given, then the feasibility problem is in the class NC.

This paper is concerned with the problem of recognizing, in a graph with rational vector-weights associated with the edges, the existence of a cycle whose total weight is the zero vector. This problem is known to be equivalent to the problem of recognizing the existence of cycles in dynamic graphs and to the validity of some systems of recursive formulas. It was previously conjectured that combinatorial algorithms exist for the cases of two- and three-dimensional vector-weights. The present paper gives strongly polynomial algorithms for any fixed dimension. Moreover, these algorithms also establish membership in the class NC. On the other hand, it is shown that when the dimension of the weights is not fixed, the problem is equivalent to the general linear programming problem under strongly polynomial and logspace reductions.

A language for reasoning about probability is considered that allows statements such as 'the probability of E/sub 1/ is less than 1/3' and 'the probability of E/sub 1/ is at least twice the probability of E/sub 2/', where E/sub 1/ and E/sub 2/ are arbitrary events. The case is treated in which all events are measurable (i.e. represent measurable sets), as well as the more general case, which is also of interest in practice, where they may not be measurable. The measurable case is essentially a formalization of (the propositional fragment of) N. Nilson's (1986) probabilistic logic, while the general (nonmeasurable) case corresponds precisely to replacing probability functions by Dempster-Shafer belief functions. In both cases, an elegant complete axiomization is provided, and it is shown that the problem of deciding satisfiability is NP-complete.>

T. Parsons originally proposed and studied the following pursuit-evasion problem on graphs: Members of a team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number s ( G ) of searchers that will suffice for guaranteeing capture of the fugitive? It is shown that determining whether s ( G ) ≤ K , for a given integer K , is NP-complete for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs G with s ( G ) ≤ K for K = 1, 2, 3.

The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed.Let n and m denote the number of variables and the number of inequalities, respectively, in a linear programming problem.We describe an 2 2 O((logm + log n)log n) time parallel algorithm under the concurrent-read-exclusive-write PRAM model for deciding feasibility.It requires mn O(l°gn) processors in the worst case, though we do not know whether this bound is tight.If the coefficients are rational or the set of solutions is bounded then, given the output of the feasibility checking algorithm, a solution can be computed in constant time.Moreover, linear programming problems with two nonzero coefficients in the objective function can be solved in poly-log time on a similar number of processors.Consequently, all these problems can be solved 2 by sequentially with only 2 2 O((logm + log n) log n) space.It is also shown that if the underlying graph has bounded treewidth and an underlying tree is given then the problem is in the class NC.

We consider the problem of achieving coordinated actions in a real-time distributed system. In particular, we consider how tightly processors can be guaranteed to perform a particular action, in a system where message transmission is guaranteed, but there is some uncertainty in message transmission time. We present an algorithm to achieve optimal precision in arbitrary networks.

It has been a challenge for mathematicians to confirm theoretically the extremely good performance of simplex-type algorithms for linear programming. In this paper the average number of steps performed by a simplex algorithm, the so-called self-dual method , is analyzed. The algorithm is not started at the traditional point (1, … , l) T , but points of the form (1, ϵ, ϵ 2 , …) T , with ϵ sufficiently small, are used. The result is better, in two respects, than those of the previous analyses. First, it is shown that the expected number of steps is bounded between two quadratic functions c 1 (min( m , n )) 2 and c 2(min( m , n )) 2 of the smaller dimension of the problem. This should be compared with the previous two major results in the field. Borgwardt proves an upper bound of O ( n 4 m 1/( n -1) ) under a model that implies that the zero vector satisfies all the constraints, and also the algorithm under his consideration solves only problems from that particular subclass. Smale analyzes the self-dual algorithm starting at (1, … , 1) T . He shows that for any fixed m there is a constant c ( m ) such the expected number of steps is less than c ( m )(ln n ) m ( m +1) ; Megiddo has shown that, under Smale's model, an upper bound C ( m ) exists. Thus, for the first time, a polynomial upper bound with no restrictions (except for nondegeneracy) on the problem is proved, and, for the first time, a nontrivial lower bound of precisely the same order of magnitude is established. Both Borgwardt and Smale require the input vectors to be drawn from spherically symmetric distributions. In the model in this paper, invariance is required only under certain

It has been a challenge for mathematicians to theoretically confirm the extremely good performance of simplex-type algorithms for linear programming. In this paper we analyze the average number of steps performed by a simplex algorithm so-called the self-dual method. Instead of starting the algorithm at the traditional point (1, ..., 1)T, we use points of the form (1, ε, ε2, ...) T, with ε sufficiently small. The result that we get is much better, in two respects, than those of the previous analyses. First, we show that the expected number of steps is bounded between two quadratic functions c1(min(m, n))2 and c2(min(m, n))2 of the smaller dimension of the problem. This should be compared with the previous two major results in the field. Borgwardt proves an upper bound of O(n4m1/(n-1)) under a restrictive model which implies that the zero-vector satisfies all the constraints, and also the algorithm under his consideration solves only problems from the particular subclass. Smale analyzes a less restrictive algorithm. He shows that for any fixed m there is a constant c(m) such the expected number of steps is less than c(m)(ln n)m(m+1); Megiddo has shown that, under Smale's model, an upper-bound C(m) exists. Thus, we prove for the first time a polynomial upper bound with no restrictions (except for non-degeneracy) on the problem, and establish for the first time a nontrivial lower bound of precisely the same order of magnitude. Secondly, our probabilistic model is much less restrictive than the previous ones. Both Borgwardt and Smale require the input vectors to be drawn from spherically

It is demonstrated that the linear programming problem in d variables and n constraints can be solved in O(n) time when d is fixed.This bound follows from a multidimensional search technique which is applicable for quadratic programming as well.There is also developed an algorithm that is polynomial in both n and d provided d is bounded by a certain slowly growing function of n.

Given n demand points in the plane, the p-center problem is to find p supply points (anywhere in the plane) so as to minimize the maximum distance from a demand point to its respective nearest supply point. The p-median problem is to minimize the sum of distances from demand points to their respective nearest supply points. We prove that the p-center and the p-median problems relative to both the Euclidean and the rectilinear metrics are NP-hard. In fact, we prove that it is NP-hard even to approximate the p-center problems sufficiently closely. The reductions are from 3-satisfiability.

The goal of this paper is to point out that analyses of parallelism m computational problems have practical implications even when mult~processor machines are not available.This is true because, in many cases, a good parallel algorithm for one problem may turn out to be useful for designing an efficsent serial algorithm for another problem A unified framework for cases like this is presented.Particular cases, which axe discussed in this paper, provide motivation for examining parallelism in sorting, selecuon, minimum-spanning-tree, shortest route, max-flow, and matrix multiplication problems, as well as in scheduling and locational problems.

A linear programming algorithm is called genuinely polynomial if it requires no more than $p(m,n)$ arithmetic operations to solve problems of order $m \times n$, where p is a polynomial. It is not known whether such an algorithm exists. We present a genuinely polynomial algorithm for the simpler problem of solving linear inequalities with at most two variables per inequality. The number of operations required is $O(mn^3 \log {\text{m}})$. The technique used was developed in a previous paper where a novel binary search idea was introduced.

Linear-time algorithms for linear programming in $R^2 $ and $R^3 $ are presented. The methods used are applicable for other graphic and geometric problems as well as quadratic programming. For example, a linear-time algorithm is given for the classical problem of finding the smallest circle enclosing n given points in the plane; this disproves a conjecture by Shamos and Hoey [Proc.16th IEEE Symposium on Foundations of Computer Science, 1975] that this problem requires $\Omega (n\log n)$ time. An immediate consequence of the main result is that the problem of linear separability is solvable in linear time. This corrects an error in Shamos and Hoey’s paper, namely, that their $ O (n\log n)$ algorithm for this problem in the plane was optimal. Also, a linear-time algorithm is given for the problem of finding the weighted center of a tree, and algorithms for other common location-theoretic problems are indicated. The results apply also to the problem of convex quadratic programming in three dimensions. The results have already been extended to higher dimensions, and we know that linear programming can be solved in linear time when the dimension is fixed. This will be reported elsewhere; a preliminary version is available from the author.

An $O(n\log ^3 n)$ algorithm for the continuous p-center problem on a tree is presented. Following a sequence of previous algorithms, ours is the first one whose time bound in uniform in p and less than quadratic in n. We also present an $O(n\log ^2 n\log \log n)$ algorithm for a weighted discrete p-center problem.

Linear-time algorithms for linear programming in $R^2 $ and $R^3 $ are presented. The methods used are applicable for other graphic and geometric problems as well as quadratic programming. For exam...

The goal of this paper is to point out that analyses of parallelism in computational problems have practical implications even when multi-processor machines are not available. This is true because, in many cases, a good parallel algorithm for one problem may turn out to be useful for designing an efficient serial algorithm for another problem. A unified framework for cases like this is presented. Particular cases, which are discussed in this paper, provide motivation for examining parallelism in problems like sorting, selection, minimum-spanning-tree, shortest route, maxflow, matrix multiplication, as well as scheduling and locational problems.

T. Parsons proposed and partially analyzed the following pursuit-evasion problem on graphs: A team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number s(G) of searchers that will suffice for guaranteeing capture of the fugitive? We show that determining whether s(G) ≤ K, for a given integer K, is NP-hard for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs with s(G) ≤ K for K = 1,2,3.

Many known algorithms are based on selection in a set whose cardinality is superlinear in terms of the input length. It is desirable in these cases to have selection algorithms that run in sublinear time in terms of the cardinality of the set. This paper presents a successful development in this direction. The methods developed here are applied to improve the previously known upper bounds for the time complexity of various location problems.

An algonthm ,s developed which finds the nth largest element of a linearly ordered set S, given m the form of m patrwise disjoint subsets Each of the m subsets satisfies the property that its kth largest element can be computed m a constant amount of time The algorithm terminates m time O(m.log2([Sj/m))The selection algorithm applies to the problem of optimum distribution of effort, namely, the maxun~zation of the total utility of allocating n persons to m activities, where the utlhty of k persons assigned to actwity j ~s a concave funcuon uAk) Consequently, this problem can be solved m time O(m.logZn)

Let A be the problem of minimizing c1x1+...+cnxn subject to certain constraints on x=(x1,...,xn), and let B be the problem of minimizing (a0+a1x1+...+anxn)/(b0+b1x1+...+bnxn) subject to the same constraints, assuming the denominator is always positive. It is shown that if A is solvable within O[p(n)] comparisons and O[q(n)] additions, then B is solvable in time O[p(n)(q(n)+p(n))]. This applies to most of the “network” algorithms. Consequently, minimum ratio cycles, minimum ratio spanning trees, minimum ratio (simple) paths, maximum ratio weighted matchings, etc., can be computed within polynomial-time in the number of variables. This improves a result of E. L. Lawler, namely, that a minimum ratio cycle can be computed within a time bound which is polynomial in the number of bits required to specify an instance of the problem. A recent result on minimum ratio spanning trees by R. Chandrasekaran is also improved by the general arguments presented in this paper. Algorithms of time-complexity O(¦E¦ • ¦V¦2•log¦V¦) for a minimum ratio cycle and O(¦E¦ • log2¦V¦ • log log ¦V¦) for a minimum ratio spanning tree are developed.

Abstract A set of points, called consumers, and another point called central supplier, are located in a Euclidean plane. The cost of constructing a connection between two points is proportional to the distance between them. The minimum cost required for connecting all the consumers to the supplier is given by a minimal Steiner tree. An example is given in which for every allocation of the total cost of the tree to the consumers, a coalition of consumers exists, which is charged more than the cost required for connecting its members to the central supplier.

The following class of matching problems is considered. The vertices of a complete undirected graph are indexed $1, \cdots ,n$, where $n = 2m$. Every vertex i is assigned two numbers $a_i $, $b_i $. The length of every edge $(i,j)$, where $i < j$, is $d(i,j) = a_i + b_j $. This class of weighted graphs is applicable to scheduling and optimal assignment problems. A maximum weighted (perfect) matching is found in $O(n \cdot \log n)$ operations.