Journal of the ACM

The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of context on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics, through the discovery of “authorative” information sources on such topics. We propose and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure. Our formulation has connections to the eigenvectors of certain matrices associated with the link graph; these connections in turn motivate additional heuristrics for link-based analysis.

This article is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program called Principal Component Pursuit ; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the ℓ ₁ norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces.

Consider a set of S of n data points in real d -dimensional space, R ^d , where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q ∈ R ^d , is the closest point of S to q can be reported quickly. Given any positive real ϵ, data point p is a (1 +ϵ)- approximate nearest neighbor of q if its distance from q is within a factor of (1 + ϵ) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in R ^d in O(dn log n ) time and O(dn) space, so that given a query point q ∈ R ^d , and ϵ > 0, a (1 + ϵ)-approximate nearest neighbor of q can be computed in O ( c _{d , ϵ} log n ) time, where c _d,ϵ ≤ d ⌈1 + 6d/ϵ⌉ ^d is a factor depending only on dimension and ϵ. In general, we show that given an integer k ≥ 1, (1 + ϵ)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n ) time.

Subgraph isomorphism can be determined by means of a brute-force tree-search enumeration procedure. In this paper a new algorithm is introduced that attains efficiency by inferentially eliminating successor nodes in the tree search. To assess the time actually taken by the new algorithm, subgraph isomorphism, clique detection, graph isomorphism, and directed graph isomorphism experiments have been carried out with random and with various nonrandom graphs.

A parallel asynchronous logic-in-memory implementation of a vital part of the algorithm is also described, although this hardware has not actually been built. The hardware implementation would allow very rapid determination of isomorphism.

A new mathematical method is developed for interpolation from a given set of data points in a plane and for fitting a smooth curve to the points. This method is devised in such a way that the resultant curve will pass through the given points and will appear smooth and natural. It is based on a piecewise function composed of a set of polynomials, each of degree three, at most, and applicable to successive intervals of the given points. In this method, the slope of the curve is determined at each given point locally, and each polynomial representing a portion of the curve between a pair of given points is determined by the coordinates of and the slopes at the points. Comparison indicates that the curve obtained by this new method is closer to a manually drawn curve than those drawn by other mathematical methods.

It has been observed by many people that a striking number of quite diverse mathematical problems can be formulated as problems in integer programming, that is, linear programming problems in which some or all of the variables are required to assume integral values. This fact is rendered quite interesting by recent research on such problems, notably by R. E. Gomory [2, 3], which gives promise of yielding efficient computational techniques for their solution. The present paper provides yet another example of the versatility of integer programming as a mathematical modeling device by representing a generalization of the well-known “Travelling Salesman Problem” in integer programming terms. The authors have developed several such models, of which the one presented here is the most efficient in terms of generality, number of variables, and number of constraints. This model is due to the second author [4] and was presented briefly at the Symposium on Combinatorial Problems held at Princeton University, April 1960, sponsored by SIAM and IBM. The problem treated is: (1) A salesman is required to visit each of n cities, indexed by 1, … , n . He leaves from a “base city” indexed by 0, visits each of the n other cities exactly once, and returns to city 0. During his travels he must return to 0 exactly t times, including his final return (here t may be allowed to vary), and he must visit no more than p cities in one tour. (By a tour we mean a succession of visits to cities without stopping at city 0.) It is required to find such an itinerary which minimizes the total distance traveled by the salesman.

Note that if t is fixed, then for the problem to have a solution we must have tp ≧ n . For t = 1, p ≧ n , we have the standard traveling salesman problem.

Let d _ij ( i ≠ j = 0, 1, … , n ) be the distance covered in traveling from city i to city j . The following integer programming problem will be shown to be equivalent to (1): (2) Minimize the linear form ∑ _{0≦ i ≠ j ≦ n} ∑ d _ij x _ij over the set determined by the relations ∑ ⁿ _{i =0 i ≠ j} x _ij = 1 ( j = 1, … , n ) ∑ ⁿ _{j =0 j ≠ i} x _ij = 1 ( i = 1, … , n ) u _i - u _j + px _ij ≦ p - 1 (1 ≦ i ≠ j ≦ n ) where the x _ij are non-negative integers and the u _i ( i = 1, …, n ) are arbitrary real numbers. (We shall see that it is permissible to restrict the u _i to be non-negative integers as well.)

If t is fixed it is necessary to add the additional relation: ∑ ⁿ _{u =1} x _{i 0} = t Note that the constraints require that x _ij = 0 or 1, so that a natural correspondence between these two problems exists if the x _ij are interpreted as follows: The salesman proceeds from city i to city j if and only if x _ij = 1. Under this correspondence the form to be minimized in (2) is the total distance to be traveled by the salesman in (1), so the burden of proof is to show that the two feasible sets correspond; i.e., a feasible solution to (2) has x _ij which do define a legitimate itinerary in (1), and, conversely a legitimate itinerary in (1) defines x _ij , which, together with appropriate u _i , satisfy the constraints of (2).

Consider a feasible solution to (2).

The number of returns to city 0 is given by ∑ ⁿ _{i =1} x _{i 0} . The constraints of the form ∑ x _ij = 1, all x _ij non-negative integers, represent the conditions that each city (other than zero) is visited exactly once. The u _i play a role similar to node potentials in a network and the inequalities involving them serve to eliminate tours that do not begin and end at city 0 and tours that visit more than p cities. Consider any x _{r 0 r 1} = 1 ( r ₁ ≠ 0). There exists a unique r ₂ such that x _{r 1 r 2} = 1. Unless r ₂ = 0, there is a unique r ₃ with x _{r 2 r 3} = 1. We proceed in this fashion until some r _j = 0. This must happen since the alternative is that at some point we reach an r _k = r _j , j + 1 < k .

Since none of the r 's are zero we have u _{r i} - u _{r i + 1} + px _{r i r i + 1} ≦ p - 1 or u _{r i} - u _{r i + 1} ≦ - 1. Summing from i = j to k - 1, we have u _{r j} - u _{r k} = 0 ≦ j + 1 - k , which is a contradiction. Thus all tours include city 0. It remains to observe that no tours is of length greater than p . Suppose such a tour exists, x _{0 r 1} , x _{r 1 r 2} , … , x _{r p r p +1} = 1 with all r _i ≠ 0. Then, as before, u _{r 1} - u _{r p +1} ≦ - p or u _{r p +1} - u _{r 1} ≧ p .

But we have u _{r p +1} - u _{r 1} + px _{r p +1 r 1} ≦ p - 1 or u _{r p +1} - u _{r 1} ≦ p (1 - x _{r p +1 r 1} ) - 1 ≦ p - 1, which is a contradiction.

Conversely, if the x _ij correspond to a legitimate itinerary, it is clear that the u _i can be adjusted so that u _i = j if city i is the j th city visited in the tour which includes city i , for we then have u _i - u _j = - 1 if x _ij = 1, and always u _i - u _j ≦ p - 1.

The above integer program involves n ² + n constraints (if t is not fixed) in n ² + 2 n variables. Since the inequality form of constraint is fundamental for integer programming calculations, one may eliminate 2 n variables, say the x _{i 0} and x _{0 j} , by means of the equation constraints and produce an equivalent problem with n ² + n inequalities and n ² variables.

The currently known integer programming procedures are sufficiently regular in their behavior to cast doubt on the heuristic value of machine experiments with our model. However, it seems appropriate to report the results of the five machine experiments we have conducted so far. The solution procedure used was the all-integer algorithm of R. E. Gomory [3] without the ranking procedure he describes.

The first three experiments were simple model verification tests on a four-city standard traveling salesman problem with distance matrix [ 20 23 4 30 7 27 25 5 25 3 21 26 ]

The first experiment was with a model, now obsolete, using roughly twice as many constraints and variables as the current model (for this problem, 28 constraints in 21 variables). The machine was halted after 4000 pivot steps had failed to produce a solution.

The second experiment used the earlier model with the x _{i 0} and x _{0 j} eliminated, resulting in a 28-constraint, 15-variable problem. Here the machine produced the optimal solution in 41 pivot steps.

The third experiment used the current formulation with the x _{i 0} and x _{0 j} eliminated, yielding 13 constraints and 9 variables. The optimal solution was reached in 7 pivot steps.

The fourth and fifth experiments were used on a standard ten-city problem, due to Barachet, solved by Dantzig, Johnson and Fulkerson [1]. The current formulation was used, yielding 91 constraints in 81 variables. The fifth problem differed from the fourth only in that the ordering of the rows was altered to attempt to introduce more favorable pivot choices. In each case the machine was stopped after over 250 pivot steps had failed to produce the solution. In each case the last 100 pivot steps had failed to change the value of the objective function.

It seems hopeful that more efficient integer programming procedures now under development will yield a satisfactory algorithmic solution to the traveling salesman problem, when applied to this model. In any case, the model serves to illustrate how problems of this sort may be succinctly formulated in integer programming terms.