Abstract The proximity π = π(G) of a connected graph G is the minimum, over all vertices, of the average distance from a vertex to all others. Similarly, the maximum is called the “remoteness” and denoted by ρ = ρ(G). In this article we first prove upper and lower bounds on π and ρ as a function of the order n of G. A comparison between these two invariants follows and then each one is compared to the diameter, radius, average eccentricity, average distance, independence number and matching number. Most bounds so obtained are proved, but a few of them remain conjectures. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

The variable neighborhood search metaheuristic is applied to the primal simple plant-location problem and to a reduced dual obtained by exploiting the complementary slackness conditions. This leads to (i) heuristic resolution of (metric) instances with uniform fixed costs, up to n=15,000 users, and m=n potential locations for facilities with an error not exceeding 0.04%; (ii) exact solution of such instances with up to m=n=7,000; and (iii) exact solutions of instances with variable fixed costs and up to m=n=15,000.

Abstract The p‐Center problem consists of locating p facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility to which he or she is allocated. In this paper, we present a basic Variable Neighborhood Search and two Tabu Search heuristics for the p‐Center problem without the triangle inequality. Both proposed methods use the 1‐interchange (or vertex substitution) neighborhood structure. We show how this neighborhood can be used even more efficiently than for solving the p‐Median problem. Multistart 1‐interchange, Variable Neighborhood Search, Tabu Search, and a few early heuristics are compared on small‐ and large‐scale test problems from the literature. © 2003 Wiley Periodicals, Inc.

We consider nonlinear programs in 0–1 variables with nonlinear constraints and survey the main approaches to their solution: (i) linearization; (ii) algebraic methods; (iii) enumerative methods and (iv) cutting-plane methods. We also present an extensive computational comparison of algorithms of all four categories. Enumerative methods appear to be the most promising. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract We consider graphs G = (V,E) with order ρ = |V|, size e = |E|, and stability number β0. We collect or determine upper and lower bounds on each of these parameters expressed as functions of the two others. We prove that all these bounds are sharp. © 1993 by John Wiley & Sons, Inc.

S.H. Bokhari (IEEE Trans. Comput., vol.37, p.48-57, 1988) has studied the assignment of the modules of a parallel program to the processors of a multiple-computer system. He proposed algorithms to solve optimally the following problems: (1) partition chain-structured parallel or pipelined programs over chain-connected systems; (2) partition multiple chain-structured parallel or pipelined programs over single-host multiple satellite systems; (3) partition multiple arbitrarily structured serial programs over single-host multiple-satellite systems; (4) partition single-tree structured parallel or pipelined programs over single-host multiple identical satellite systems. The authors solve here problem 1 by dynamic programming and problem 2 by sorting and using bisection search for the bottleneck value. They also note that Bokhari's algorithms for problems 3 and 4 can be improved by using recent results of G. Gallo et al. (1989), and by implementing E.W. Dijkstra's (1959) algorithm, which is used as a subroutine, with a heap structure. The time complexity of all algorithms is thus reduced.>

Nilsson recently introduced a rigorous semantic generalization of logic in which the truth values of sentences are probability values. This led to state precisely several basic problems of artificial intelligence, a paradigm of which is probabilistic satisfiability (PSAT): determine, given a set of clauses and probabilities that these clauses are true, whether these probabilities are consistent. We consider several extensions of this model involving intervals on probability values, conditional probabilities and minimal modifications of probability values to ensure satisfiability. Investigating further an approach of G. Georgakopoulos, D. Kavvadias and C. H. Papadimitriou, we propose a column generation algorithm which allows to solve exactly all these extensions. Computational experience shows that large problems, with up to 140 variables and 300 clauses, may be solved in reasonable time. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The authors study the complexity and propose an algorithm for the problem of determining, given p vectors of {-1,1}(n), all linear combinations of them which are also in {-1,1}(n). Computational results are reported. This problem corresponds to the detection of spurious states in neural networks.

Abstract The distance between an edge and a point of a network N is defined as the maximum distance from that point to any point on that edge. A continuous median of N is a point of N such that the sum of the distances between all edges and that point is minimum. A continuous p‐median is a set of p points of N such that the sum for all edges of the distance to the closest poit of that set is minimum. It is shown that the set of vertices and middle points of edges always contaisn a continuous p‐median. Therefore, powerful algorithms for the usual p‐median problem can be brought to bear. Moreover, algorithms requiring O(m2) operations in worst case for determining the set of all continuous and conditional continuous medians of N are obtained. A linear algorithm for the set of all continuous medians of a tree is also provided.

Abstract Properties of efficient points on a network are given. They are then used to devise (i) a linear algorithm for efficient points on a tree, (ii) on O(m log n) algorithm for the set of links common to all shortest paths between two points, and (iii) a polynomial algorithm for efficient points on a general network.

Cluster analysis is concerned with the problem of partitioning a given set of entities into homogeneous and well-separated subsets called clusters. The concepts of homogeneity and of separation can be made precise when a measure of dissimilarity between the entities is given. Let us define the diameter of a partition of the given set of entities into clusters as the maximum dissimilarity between any pair of entities in the same cluster and the split of a partition as the minimum dissimilarity between entities in different clusters. The problems of determining a partition into a given number of clusters with minimum diameter (i.e., a partition of maximum homogeneity) or with maximum split (i.e., a partition of maximum separation) are first considered. It is shown that the latter problem can be solved by the classical single-link clustering algorithm, while the former can be solved by a graph-theoretic algorithm involving the optimal coloration of a sequence of partial graphs, described in more detail in a previous paper. A partition into a given number of clusters will be called efficient if and only if there exists no partition into at most the same number of clusters with smaller diameter and not smaller split or with larger split and not larger diameter. Two efficient partitions are called equivalent if and only if they have the same values for the split and for the diameter.