Pareto optimality,anonymity, and strategy-proofness in location problems

Generalized location problems withn agents are considered, who each report a point inm-dimensional Euclidean space. A solution assigns a compromise point to thesen points, and the individual utilities for this compromise point are equal to the negatives of the Euclidean distances to the individual positions. Form = 2 andn odd, it is shown that a solution is Pareto optimal, anonymous, and strategy-proof if, and only if, it is obtained by taking the coordinatewise median with respect to a pair of orthogonal axes. Further, for all other situations withm2, such a solution does not exist. A few results concerning other solution properties, as well as different utility functions, are discussed.Supported by a grant from the Cooperation Centre Tilburg and Eindhoven University.     

k-Plane Clustering

A finite new algorithm is proposed for clustering m given points in n-dimensional real space into k clusters by generating k planes that constitute a local solution to the nonconvex problem of minimizing the sum of squares of the 2-norm distances between each point and a nearest plane. The key to the algorithm lies in a formulation that generates a plane in n-dimensional space that minimizes the sum of the squares of the 2-norm distances to each of m₁ given points in the space. The plane is generated by an eigenvector corresponding to a smallest eigenvalue of an n × n simple matrix derived from the m₁ points. The algorithm was tested on the publicly available Wisconsin Breast Prognosis Cancer database to generate well separated patient survival curves. In contrast, the k-mean algorithm did not generate such well-separated survival curves.     

Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem

The Fermat—Weber location problem is to find a point in ⁿ that minimizes the sum of the weighted Euclidean distances fromm given points in ⁿ . A popular iterative solution method for this problem was first introduced by Weiszfeld in 1937. In 1973 Kuhn claimed that if them given points are not collinear then for all but a denumerable number of starting points the sequence of iterates generated by Weiszfeld's scheme converges to the unique optimal solution. We demonstrate that Kuhn's convergence theorem is not always correct. We then conjecture that if this algorithm is initiated at the affine subspace spanned by them given points, the convergence is ensured for all but a denumerable number of starting points.     

Type constants and (q, 2)-summing norms defined byn vectors

Forq≧2, the (q, 2)-summing norm of an operator of rankn can be computed, up to a constantc _q, by an appropriate choice of at mostn vectors. A corresponding statement is true for the Gaussian type and cotype constants ofn-dimensional spaces.     

Inverse median location problems with variable coordinates

Given n points in \mathbbR^d{\mathbb{R}^d} with nonnegative weights, the inverse 1-median problem with variable coordinates consists in changing the coordinates of the given points at minimum cost such that a prespecified point in \mathbbR^d{\mathbb{R}^d} becomes the 1-median. The cost is proportional to the increase or decrease of the corresponding point coordinate. If the distances between points are measured by the rectilinear norm, the inverse 1-median problem is NP{\mathcal{NP}}-hard, but it can be solved in pseudo-polynomial time. Moreover, a fully polynomial time approximation scheme exists in this case. If the point weights are assumed to be equal, the corresponding inverse problem can be reduced to d continuous knapsack problems and is therefore solvable in O(nd) time. In case that the squared Euclidean norm is used, we derive another efficient combinatorial algorithm which solves the problem in O(nd) time. It is also shown that the inverse 1-median problem endowed with the Chebyshev norm in the plane is NP{\mathcal{NP}}-hard. Another pseudo-polynomial algorithm is developed for this case, but it is shown that no fully polynomial time approximation scheme does exist.     

Existence and asymptotic behavior for an incompressible Newtonian flow with intrinsic degree of freedom

We consider the Cauchy problem of a mathematical model for an incompressible, homogeneous, Newtonian fluid taking into account internal degrees of freedom. We first show that there exists a unique global strong solution when the given initial data are small in some sense. Then, we deduce the optimal decay rates for velocity vector in L² ? norm and L^p ? norm for p > n. These decay estimates depend only on the spatial dimension and the decay properties of the heat solution with the same data. Copyright © 2013 John Wiley & Sons, Ltd.     

Duality theorem for a generalized Fermat-Weber problem

The classical Fermat-Weber problem is to minimize the sum of the distances from a point in a plane tok given points in the plane. This problem was generalized by Witzgall ton-dimensional space and to allow for a general norm, not necessarily symmetric; he found a dual for this problem. The authors generalize this result further by proving a duality theorem which includes as special cases a great variety of choices of norms in the terms of the Fermat-Weber sum. The theorem is proved by applying a general duality theorem of Rockafellar. As applications, a dual is found for the multi-facility location problem and a nonlinear dual is obtained for a linear programming problem with a priori bounds for the variables. When the norms concerned are continuously differentiable, formulas are obtained for retrieving the solution for each primal problem from the solution of its dual.     

Anchored Hyperplane Location Problems

   Abstract. The anchored hyperplane location problem is to locate a hyperplane passing through some given points P

An improvement and an extension of the Elzinga & Hearn's algorithm to the 1-center problem in ℝn withl 2b-normswithl 2b-norms

Summary In this paper we deal with the 1-center problem in ℝⁿ when the distance is measured by anyl _2b-norm. This type of norm generalizes the Euclidean norm (l ₂-norm) and can be used to estimate road distances or travel times in Locational Analysis, and to measure dissimilarities between data in Cluster Analysis. The problem is to find the smallestb-ellipsoid containing a given finite setA of points in ℝⁿ, which generalizes the one of finding the smallest sphere containingA (1-center problem with thel ₂-norm). We show that this problem has a unique optimal solution. For thel ₂-norm, we use the Elzinga-Hearn algorithm. New starting rules are proposed to initialize and to improve the algorithm. On the other hand, the Elzinga-Hearn algorithm is extended to solve the problem withl _2b-norms. Computational results are given for six differentl _2b-norms, when these new starting rules are used in order to show which is the best starting rule. Problems of up to 5.000 points in ℝⁿ,n=2,4,6,8 and 10, are solved in a few seconds.     

A class of dimension-skipping graphs

Forn≧6 there exists a graphG with dimG=n, dimG*≧n+2, whereG* isG with a certain edge added.     

Explicit generalized zolotarev polynomials with complex coefficients

We give explicitly a class of polynomials with complex coefficients of degreen which deviate least from zero on [−1, 1] with respect to the max-norm among all polynomials which have the same,m + 1, 2m ≤n, first leading coefficients. Form=1, we obtain the polynomials discovered by Freund and Ruschewyh. Furthermore, corresponding results are obtained with respect to weight functions of the type 1/√ρl, whereρl is a polynomial positive on [−1, 1].     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

Sphere-and-point incidence relations in high dimensions with applications to unit distances and furthest-neighbor pairs

Forn points in three-dimensional Euclidean space, the number of unit distances is shown to be no more thancn ^8/5. Also, we prove that the number of furthest-neighbor pairs forn points in 3-space is no more thancn ^8/5, provided no three points are collinear. Both these results follow from the following incidence relation of spheres and points in 3-space. Namely, the number of incidences betweenn points andt spheres is at mostcn ^4/5 t ^4/5 if no three points are collinear andn ^3/2>t>n ^1/4. The proof is based on a point-and-line incidence relation established by Szemerédi and Trotter. Analogous versions for higher dimensions are also given.     

On the wiener type regularity of a boundary point for the polyharmonic operator

It is shown that the Wiener regularity of a boundary point with respect to the m-harmonic operator is a local property for the space dimensions n=2m,2m+1,2m+2 with m > 2 and n = 4,5,6,7 with m = 2. An estimate for the continuity modulus of the solution formulated in terms of the Wiener type m-capacitary integral is obtained for the same n and m.     

On polynomial approximation in the uniform norm by the discrete least squares method

The discrete least squares method is convenient for computing polynomial approximations to functions. We investigate the possibility of using this method to obtain polynomial approximants good in the uniform norm, and find that for a given set ofm nodes, the degreen of the approximating polynomial should be selected so that there is a subset ofn+1 nodes which are close ton+1 Fejér points for the curve. Numerical examples are presented.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041.     

Decomposition of finite pseudometric spaces

Here we define decomposable pseudometrics. A pseudometric is decomposable if it can be represented as the sum of two pseudometrics that are obtained in a way other than the multiplication all distances by a positive factor. We consider spaces consisting ofn points. We prove that there exist a finite number of indecomposable pseudometrics (that is, a basis) such that any pseudometric is a linear combination of basic pseudometrics with nonnegative coefficients. Forn ≤ 7, the basic pseudometrics are listed. A decomposability test is derived for finite pseudometric spaces. We also establish some other conditions of decomposability and indecomposability. Translated fromMatematicheskie Zametki, Vol. 63, No. 2, pp. 225–234, February, 1998.     

The number of unit distances is almost linear for most norms

We prove that there exists a norm in the plane under which no n-point set determines more than unit distances. Actually, most norms have this property, in the sense that their complement is a meager set in the metric space of all norms (with the metric given by the Hausdorff distance of the unit balls).     

Compromise 4<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> plans with clear two-factor interactions

This paper gets some necessary conditions for the existence of some kinds of clear 4^m2^n compromise plans which allow estimation of all main effects and some specified two-factor interactions without assuming the remaining two-factor interactions being negligible. Some methods for constructing clear 4^m2^n compromise plans are introduced.     

All-norm approximation algorithms

A major drawback in optimization problems and in particular in scheduling problems is that for every measure there may be a different optimal solution. In many cases the various measures are different ℓ_p norms. We address this problem by introducing the concept of an all-norm ρ-approximation algorithm, which supplies one solution that guarantees ρ-approximation to all ℓ_p norms simultaneously. Specifically, we consider the problem of scheduling in the restricted assignment model, where there are m machines and n jobs, each job is associated with a subset of the machines and should be assigned to one of them. Previous work considered approximation algorithms for each norm separately. Lenstra et al. [Math. Program. 46 (1990) 259–271] showed a 2-approximation algorithm for the problem with respect to the ℓ_∞ norm. For any fixed ℓ_p norm the previously known approximation algorithm has a performance of θ(p). We provide an all-norm 2-approximation polynomial algorithm for the restricted assignment problem. On the other hand, we show that for any given ℓ_p norm (p>1) there is no PTAS unless P=NP by showing an APX-hardness result. We also show for any given ℓ_p norm a FPTAS for any fixed number of machines.     

NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations

Three series of number-theoretic problems with explicitly defined parameters concerning systems of Diophantine dis-equations with solutions from a given domain are considered. Constraints on these parameters under which any problem of each series is NP-complete are proved. It is proved that for any m and m′ (m < m′) the consistency problem on the segment [m, m′] for a system of linear Diophantine dis-equations, each of which contains exactly three variables (even if the coefficients at these variables belong to {–1, 1}), is NP-complete. This problem admits a simple geometric interpretation of NP-completeness for the determination of whether there exists an integer-valued point inside a multidimensional cube that is not covered by given hyperplanes that cut off equal segments on three arbitrary axes and are parallel to all other axes. If in a system of linear Diophantine dis-equations each dis-equation contains exactly two variables, the problem remains NP-complete under the condition that the following inequality holds: m′–m > 2. It is also proved that if the solution to a system of linear Diophantine dis-equations, each containing exactly three variables, is sought in the domain given by a system of polynomial inequalities that contain an n-dimensional cube and are contained in an n-dimensional parallelepiped symmetric with respect to the point of origin, its consistency problem is NP-complete.