A note on the m-center problem with rectilinear distances

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.     

The <Emphasis Type="Italic">p</Emphasis>-Centre Problem—Heuristic and Optimal Algorithms

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a given p in time polynomial in n. Computational results are presented.     

Asymptotic formulas for the number of oriented graphs

Wille found an asymptotic approximation to r(n, q), the number of unlabeled oriented graphs on n points and q directed lines, for a wide interval of q and conjectured that, for given n, the maximum of r(n, q) occurs at $\text{q = [}\text{2(N + 1)}\text{3}\text{]}$. We find the (different) asymptotic approximation to r(n, q) valid for the remaining interval of q and prove Wille's conjecture for all large n.     

r-tuple colorings of uniquely colorable graphs

An r-tuple coloring of a graph is one in which r colors are assigned to each point of the graph so that the sets of colors assigned to adjacent points are always disjoint. We investigate the question of whether a uniquely n-colorable graph can receive an r-tuple coloring with fewer than nr colors. We show that this cannot happen for n=3 and r=2 and that for a given n and r to establish the conjecture that no uniquely n-colorable graph can receive an r-tuple coloring from fewer than nr colors it suffices to prove it for on a finite set of uniquely n-colorable graphs.     

Symmetric Gobos in a finite projective plane

A gobo G in any incidence structure K is a (perhaps degenerate) tactical configuration having the property that no three points in G are collinear and no three lines in G are concurrent. General results are obtained where K is a finite projective plane of order n and G has k points and k lines such that each point (line) lies on r lines (points) of G. Particular attention is called to the contrast between the case r = 1 and the case r ≠ 1 when k = n.     

An inequality for pseudo-subplanes of sets of orthogonal latin squares

Let L₁, L₂,…, L_t be a given set of t mutually orthogonal order-n latin squares defined on a symbol set S, |S| = n. The squares are equivalent to a (t + 2)-netN of order n which has n² points corresponding to the n² cells of the squares. A line of the net N defined by the latin square L_i comprises the n points of the net which are specified by a set of n cells of L_i all of which contain the same symbol x of S. If we pick out a particular r × r block B of cells, a line which contains points corresponding to r of the cells of B will be called an r-cell line. If there exist r(r ? 1) such lines among the tn lines of N, we shall say that they form a pseudo-subplane of order r-the “pseudo” means that these lines need not belong to only r ? 1 of the latin squares. The purpose of the present note is to prove that the hypothesis that such a pseudo-plane exists in N implies that $\text{r}{}^3\text{? (t + 2)r}{}^2\text{+ r + nt ?}{}^1\text{0}$.     

On approximation by polynomials increasing to the right of the interval

We obtain sufficient conditions on a real valued function ?, continuous on [0, + ∞), to insure that, for some nonnegative integer n, there is a nonnegative number r(n) so that for any r ? r(n), the polynomial of best approximation to ? on [0, r] from π_n is increasing and nonnegative on [r, + ∞). Here, π_n denotes the set of all real polynomials of degree n or less. The proofs of Theorems 1 and 2 use only properties of Lagrange interpolation while that of Theorem 3 employs results on the location of interpolation points in Chebyshev approximation.     

The directional p-median problem: Definition,complexity, and algorithms

An instance of a p-median problem gives n demand points. The objective is to locate p supply points in order to minimize the total distance of the demand points to their nearest supply point. p-Median is polynomially solvable in one dimension but NP-hard in two or more dimensions, when either the Euclidean or the rectilinear distance measure is used. In this paper, we treat the p-median problem under a new distance measure, the directional rectilinear distance, which requires the assigned supply point for a given demand point to lie above and to the right of it. In a previous work, we showed that the directional p-median problem is polynomially solvable in one dimension; we give here an improved solution through reformulating the problem as a special case of the constrained shortest path problem. We have previously proven that the problem is NP-complete in two or more dimensions; we present here an efficient heuristic to solve it. Compared to the robust Teitz and Bart heuristic, our heuristic enjoys substantial speedup while sacrificing little in terms of solution quality, making it an ideal choice for real-world applications with thousands of demand points.     

On the exact values of the best approximations of classes of differentiable periodic functions by splines

We obtain the exact values of the best L ₁-approximations of classes W ^r F, r ∈ ?, of periodic functions whose rth derivative belongs to a given rearrangement-invariant set F, as well as of classes W ^r H ^ω of periodic functions whose rth derivative has a given convex (upward) majorant ω(t) of the modulus of continuity, by subspaces of polynomial splines of order m ≥ r + 1 and of deficiency 1 with nodes at the points 2kπ/n and 2kπ/n + h, n ∈ ?, k ∈ ?, h ∈ (0, 2π/n). It is shown that these subspaces are extremal for the Kolmogorov widths of the corresponding functional classes.     

The complexity of assigning genotypes to people in a pedigree consistently

We discuss the complexity of a combinatorial problem in the field of genetics, which we call Genotype ASsignability problem and abbreviate as GAS. A pair of genes at a position on a pair of chromosomes is called a genotype. GAS is defined as follows: “A pedigree is given and, for one of positions where genotypes are located in a set of pairs of chromosomes of a person, the genotypes at the position of some people in the pedigree are given. Is it possible to assign all other people (i.e., all of the people of which the genotypes are not given) genotypes for the position so as not to cause inconsistency in the heredity of genotypes at the position in the whole of the pedigree?” GAS can be used to compute, from the genotypes at the same position of some people in a pedigree, the genotypes that each person in the pedigree can possess at the position. Although many combinatorial problems have been studied so far, GAS seems not to have been done yet. Let m be the number of different genes in a pedigree and n that of people in the pedigree. We prove that GAS is NP-complete when m?3 and that it can be solved in linear time O(n) when m=2.     

Exploiting partial knowledge of satisfying assignments

Recently Schöning has shown that a simple local-search algorithm for 3SAT achieves the currently best upper bound, i.e., an expected time of 1.334ⁿ. In this paper, we show that this algorithm can be modified to run much faster if there is some kind of imbalance in satisfying assignments and we have a (partial) knowledge about that. Especially if a satisfying assignment has imbalanced 0's and 1's, i.e., p₁n 1's and (1-p₁)n 0's, then we can find a solution in time 1.260ⁿ when and 1.072ⁿ when p₁=0.1. Such an imbalance often exists in SAT instances reduced from other problems. As a concrete example, we investigate a reduction from 3DM and show our new approach is nontrivially faster than its direct algorithms. Preliminary experimental results are also given.     

An algorithm for generalized constrained multi-source Weber problem with demand substations

In this paper, we consider a multi-source Weber problem of m new facilities with respect to n demand regions in order to minimize the sum of the transportation costs between these facilities and the demand regions. We find a point on the border of each demand region from which the facilities serve the demand regions at these points. We present an algorithm including a location phase and an allocation phase in each iteration for solving this problem. An algorithm is also proposed for carrying out the location phase. Moreover, global convergence of the new algorithm is proved under mild assumptions, and some numerical results are presented.     

Comparative error bound theory for three location models: continuous demand versus discrete demand

We develop a unified error bound theory to compare a given p-median, p-center or covering location model with continuously distributed demand points in R ⁿ to a corresponding given original model of the same type having a finite collection of demand points in R ⁿ . We give ways to construct either a continuous or finite demand point model from the other model and also control the error bound. Our work uses Voronoi tilings extensively, and is related to earlier error bound theory for aggregating finitely many demand points.     

An asymptotically exact polynomial algorithm for equipartition problems

We describe an approximate algorithm for a special ‘quadratic semi-assignment problem’ arising from ‘equipartition’ applications, where one wants to cluster n objects with given weights w_i into p classes, so as to minimize the variance of the class-weights. The algorithm can be viewed both as a list scheduling method and as a special case of a heuristic procedure, due to Nemhauser and Carlson, for quadratic semi-assignment problems. Our main result is that the relative approximation error is O(1/n) when p and r = (maxw_i)/(min w_i) are bounded.     

Minmax regret location–allocation problem on a network under uncertainty

We consider a robust location–allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the “minimax regret” location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location–allocation problem can be solved in O(min{p, n − p}n³m) time, where n is the number of demand points, p (p < n) is the fixed number of demand points that must be served by the new service and m is the number of edges of the network.     

Hamiltonian decompositions of complete graphs

It is well known that K_{2n + 1} can be decomposed into n edge-disjoint Hamilton cycles. A novel method for constructing Hamiltonian decompositions of K_{2n + 1} is given and a procedure for obtaining all Hamiltonian decompositions of of K_{2n + 1} is outlined. This method is applied to find a necessary and sufficient condition for a decomposition of the edge set of K_r (r ≤ 2n) into n classes, each class consisting of disjoint paths to be extendible to a Hamiltonian decomposition of K_{2n + 1} so that each of the classes forms part of a Hamilton cycle.     

On the maximum of Stirling numbers of the second kind

A technique is illustrated for finding an estimate of the Stirling numbers of the second kind, S_{n, r}(1 ? r ? n), as n → ∞, for a certain range of values of r. It is shown how the estimation can be found to any given degree of approximation. Finally, the location of the maximum of S_{n, r} (1 ? r ? n) and the value of the maximum are computed.     

Orchards in elliptic curves over finite fields

Consider a set of n points on a plane. A line containing exactly 3 out of the n points is called a 3-rich line. The classical orchard problem asks for a configuration of the n points on the plane that maximizes the number of 3-rich lines. In this note, using the group law in elliptic curves over finite fields, we exhibit several (infinitely many) group models for orchards wherein the number of 3-rich lines agrees with the expected number given by Green-Tao (or, Burr, Grünbaum and Sloane) formula for the maximum number of lines. We also show, using elliptic curves over finite fields, that there exist infinitely many point-line configurations with the number of 3-rich lines exceeding the expected number given by Green-Tao formula by two, and this is the only other optimal possibility besides the case when the number of 3-rich lines agrees with the Green-Tao formula.     

Minimizing the density of terminal assignments in layout design

We present a linear-time solution to the problem of assigning each of n given entry terminals positioned at the upper row of a channel to one of m given exit terminals positioned at the lower row, so as to minimize the density of the resulting channel routine problem.