Algorithm, local

An algorithm which specifies the attributes of elements of a structured set and uses, at each step, only information about neighbourhoods of the element. Problems of the existence or non-existence of effective algorithms for various discrete optimization problems are naturally formulated in terms of local algorithms.

Let there be given a family of sets, and let there be assigned to each pair , where , a set such that: 1) ; 2) ; and 3) if , and , then . The set will then be denoted as a neighbourhood of in . Examples of neighbourhoods are conjunction neighbourhoods in a contracted normal form (cf. Boolean functions, minimization of).

Let be a finite undirected graph, , where is the set of vertices of , and let be the set of edges of . A neighbourhood of an edge of the graph consists of all vertices of the edges incident with the edge , and also of all edges whose vertices are included in the neighbourhood . Let be a defined neighbourhood; the neighbourhood then consists of all vertices of the edges incident with the vertices of the neighbourhood and all edges, the vertices of which belong to the neighbourhood . The neighbourhoods of an arbitrary vertex of the graph are introduced in a similar manner.

Let a system of two-place predicates , which is subdivided into two non-intersecting subsets and , be defined on pairs , . The elements of the first subset are called the main predicates, while those of the second are called the auxiliary predicates. A vector is called an information vector if , . A vector is called permissible for in if for all the equality is satisfied. The set of all information vectors permissible for in is called the information set of in .

Let and , . The set is called permissible for . The class of all sets permissible for is called the information class of the set over the system of predicates . Clearly, a neighbourhood defines a neighbourhood .

Introduce a system of functions such that

The functions will be defined over all pairs such that , , and satisfies the following conditions: 1) if ; and 2) the set , which is obtained from by replacing the element by , is permissible for , i.e. . For the sake of brevity, the pairs are denoted by .

A partial order is introduced on some of the above sets: 1) on the set one takes , ; 2) on the set of information vectors of length one takes if , ; 3) on the set of elements with marks one takes if ; 4) on the set one takes if, first, and belong to the same information class and, secondly, if follows from and ; 5) on the set of neighbourhoods of the form one takes , where and if and only if and if it follows from and that .

Let and be elements of one of the sets 1)–5). If and , then the elements and are called equi-informative, which is denoted by . A function is called monotone if it follows from that, for ,

The determination of a local algorithm also necessitates the introduction of an ordering algorithm . Let be an arbitrary set of elements with information vectors, and let . Consider the set of all pairs such that , , . The algorithm orders the set . The local algortihm is completely defined by the system of predicates , by the subdivision of this system into main predicates and auxiliary predicates , by the system of monotone functions , , and by the algorithm .

Let , . The first step of the local algorithm may be described as follows. Algorithm is applied to the set , where ; for the first pair of the ordered sequence one computes and the element is then replaced by ; if , then one takes the second pair, etc.; if for all elements the equality is true, then the local algorithm is terminated after reviewing all the pairs from . Otherwise, after replacement of the vector by the new vector , algorithm is terminated if there are no more elements with at least one symbol in the first places of the information vectors; if there are such elements, the first step of the local algorithm terminates. Let the number of steps of the local algorithm which have been performed be . The -st step is carried out exactly as the first step, except that instead of the set one now considers the set into which the set has been converted after the first steps of the local algorithm . Owing to the monotone nature of the functions , , the local algorithm will be terminated after a finite number of steps.

The starting theorems for local algorithms are the uniqueness theorem and the theorem on the existence of a best algorithm. The first theorem states that the result of the calculation of the main predicates is independent of the algorithm (the order in which the elements of the set are taken). The second theorem stipulates the existence, under very general conditions, of a best local algorithm, i.e. of a local algorithm which uses a given system of neighbourhoods to compute given main predicates with fixed auxiliary predicates, whenever this is done by any other local algorithm with an identical system of neighbourhoods, and main and auxiliary predicates.

The problem of finding a best local algorithm in explicit form has been solved for algorithms of synthesis of minimal coverings. Let there be given a tuple , where is a set, is the complexity of , , , . The complexity of the tuple is . The problem is how to construct a covering of by sets from a number of with minimum complexity. A system of neighbourhoods for each is introduced in a manner similar to the introduction of a system of neighbourhoods for conjunctions. A best local algorithm is constructed for a system of neighbourhoods at fixed predicates: the set of auxiliary predicates is empty; the main predicates are considered to be the predicates ( is not included in any minimal covering of ) and ( is included in all the minimal coverings of ). Best local algorithms have also been constructed to calculate simple properties of edges of a graph. Various local algorithms have been proposed to solve problems of minimization of Boolean functions, of discrete linear programming, etc.

Computability of best local algorithms in a class of local algorithms is an important problem in the theory of local algorithms. If a system of imbedded neighbourhoods is given on the pairs , , , and if the local algorithm operates with respect to the system of neighbourhoods where , then one says that the local algorithm has index . It is natural to consider the number of predicates in the definition of a local algorithm as the quantity of memory of the local algorithm. Let there be given a set of predicates . It is considered that all the predicates participating in the definition of the local algorithm belong to . Let be the result of applying the local algorithm to , , . One says that the predicate is not -computable if for any local algorithm of index with memory quantity for the main predicate and for the auxiliary predicates from there exists a set such that in the predicate will not be computable for all elements.

Let be the set of all Boolean functions (cf. Boolean function) in the variables and let be the predicate ( "the conjunction A is included in at least one minimal disjunctive normal form" ). With natural limitations imposed on the class of predicates it was found that the predicate is not -computable if . It is interesting to note that the predicate ( "the conjunction A is included in at least one dead-end disjunctive normal form of f" ) (cf. Boolean functions, normal forms of) is -computable, but is not -computable. Similar results were obtained for predicates describing the entry of an edge into a shortest path between given vertices of a graph.

See also the references to Boolean functions, minimization of.

References

[1a]	Yu.I. Zhuravlev, "Local algorithms for the calculation of information Part I" Cybernetics , 1 : 1 (1965) pp. 10–16 Kibernetika (Kiev) , 1 : 1 (1965) pp. 12–19
[1b]	Yu.I. Zhuravlev, "Local algorithms for the calculation of information Part II" Cybernetics , 2 : 2 (1966) pp. 1–8 Kibernetika (Kiev) , 2 : 2 (1966) pp. 1–11
[2]	I.V. Khutoryanskaya, "Aspects of the theory of local algorithms on graphs" Cybernetics , 7 : 1 (1971) pp. 37–44 Kibernetika (Kiev) : 1 (1971) pp. 29–33
[3]	Yu.I. Zhuravlev, "Set-theoretical methods in the algebra of logic" Problemy Kibernet. , 8 (1962) pp. 5–44 (In Russian)

Comments

As a specific area (or in this form), the subject seems not to have been studied in the Western literature. It may be related to the study of Systolic Array algorithms [a1], Chapt. 8.

References

[a1]	C. Mead, L. Conway, "Introduction to VLSI systems" , Addison-Wesley (1980) pp. 263–330