Location of best simultaneous approximations

Amir and Ziegler have proved that a real normed space E of dimension ≥ 3 is an inner product space if and only if, for any x,y ε E and any two dimensional subspace M of E, the expression max(‖x — w‖,‖y — w‖) attains its minimum in some point w of each segment [u,v], with u and v, respectively, best approximations to x and y from M. We extend this result to expressions π(‖x — w‖,‖y — w‖), where π denotes a monotonic norm in R²     

Analytic Center Cutting-Plane Method with Deep Cuts for Semidefinite Feasibility Problems

An analytic center cutting-plane method with deep cuts for semidefinite feasibility problems is presented. Our objective in these problems is to find a point in a nonempty bounded convex set in the cone of symmetric positive-semidefinite matrices. The cutting plane method achieves this by the following iterative scheme. At each iteration, a query point that is an approximate analytic center of the current working set is chosen. We assume that there exists an oracle which either confirms that or returns a cut A S ^m {YS ^m : AY AY - } , where 0. If , an approximate analytic center of the new working set, defined by adding the new cut to the preceding working set, is then computed via a primal Newton procedure. Assuming that contains a ball with radius > 0, the algorithm obtains eventually a point in , with a worst-case complexity of O ^*(m ³/²) on the total number of cuts generated.     

Indefinite Eigenvalue Problems with Several Singular Points and Turning Points

We consider a general class of eigenvalue problems with two-point boundary conditions on a finite interval generated by a differential equation with an indefinite weight function which has several zeros and/or poles. As a basic result we derive asymptotic estimates for a special fundamental system of solutions of the corresponding differential equation and determine the asymptotic distribution of the eigenvalues. Finally we prove the uniform convergence of eigenfunction expansions for some class of functions f.     

Approximation of solutions for location problems

This paper is devoted to a class of location problems with polyhedral norms. The objective function is shown to be a piecewise convex function which has to be maximized. We prove that the optimal locations belong to a finite set of intersection points, and we present an efficient method operating upon this finite set and providing a strict local maximum with few computational effort.     

An Improved IP Formulation for the Uncapacitated Facility Location Problem: Capitalizing on Objective Function Structure

In this paper we examine the Uncapacitated Facility Location Problem (UFLP) with a special structure of the objective function coefficients. For each customer the set of potential locations can be partitioned into subsets such that the objective function coefficients in each are identical. This structure exists in many applications, including the Maximum Cover Location Problem. For the problems possessing this structure, we develop a new integer programming formulation that has all the desirable properties of the standard formulation, but with substantially smaller dimensionality, leading to significant improvement in computational times. While our formulation applies to any instance of the UFLP, the reduction in dimensionality depends on the degree to which this special structure is present. This work was supported by grants from NSERC.     

选址问题研究的若干进展

中值问题、覆盖问题、中心问题是选址研究中的三个经典问题，它们的应用非常广泛，也是迄今为止大多数选址理论研究的坚实基础。本文综述了近年来它们的研究进展，包括模型、求解方法以及相关问题，最后，指出这一领域未来研究的一些问题与方向。     

A Network Improvement Problem Under Different Norms

In this paper, we first consider a network improvement problem, called vertex-to-vertices distance reduction problem. The problem is how to use a minimum cost to reduce lengths of the edges in a network so that the distances from a given vertex to all other vertices are within a given upper bound. We use l , l ₁ and l ₂ norms to measure the total modification cost respectively. Under l norm, we present a strongly polynomial algorithm to solve the problem, and under l ₁ or weighted l ₂ norm, we show that achieving an approximation ratio O(log(|V|)) is NP-hard. We also extend the results to the vertex-to-points distance reduction problem, which is to reduce the lengths of edges most economically so that the distances from a given vertex to all points on the edges of the network are within a given upper bound.     

Annealing Algorithms for Multisource Absolute Location Problems on Graph

A methodology is presented for applying annealing techniques tomultisource absolute location problems on graph. Two kinds ofobjective functions are considered: barycenters and centers. Aclass of new algorithms is described: its development startsfrom the iterative cluster-and-locate algorithm and reliesupon the relaxation of the integrality constraints onallocation variables. Experimental results are reported.     

Location Among Regions with Varying Norms

This paper investigates a new variation in the continuous single facility location problem. Specifically, we address the problem of locating a new facility on a plane with different distance norms on different sides of a boundary line. Special cases and extensions of the problem, where there are more than two regions are also discussed. Finally, by investigating the properties of the models, efficient solution procedures are proposed.     

A General Global Optimization Approach for Solving Location Problems in the Plane

We propose a general approach for constructing bounds required for the “Big Triangle Small Triangle” (BTST) method for the solution of planar location problems. Optimization problems, which constitute a sum of individual functions, each a function of the Euclidean distance to a demand point, are analyzed and solved. These bounds are based on expressing each of the individual functions in the sum as a difference between two convex functions of the distance, which is not the same as convex functions of the location. Computational experiments with nine different location problems demonstrated the effectiveness of the proposed procedure.     

平面上的点-线选址问题

本文研究两类平面选址问题：（1）求一直线到n个给定点的加权距离和为最小；（2）求一点到n条给定直线的加权距离和为最小，对这两个非线性最优化问题，欠给出迭代次数为多项式的算法。     

Subsets of Euclidean Space with Nearly Maximal Gowers Norms

A set E ⊂ ℝd whose indicator function 1E has maximal Gowers norm, among all sets of equal measure, is an ellipsoid up to Lebesgue null sets. If 1E has nearly maximal Gowers norm then E...     

Ratios of Norms for Polynomials and Connected n-width Problems

Let be a bounded simply connected domain with boundary Γ and let be a regular compact set with connected complement. In this paper we investigate asymptotics of the extremal constants:

The Covariance Adjusted Location Linear Discriminant Function for Classifying Data with Unequal Dispersion Matrices in Different Locations

Classification between two populations dealing with both continuous and binary variables is handled by splitting the problem into different locations. Given the location specified by the values of the binary variables, discrimination is performed using the continuous variables. The location probability model with homoscedastic across location conditional dispersion matrices is adopted for this problem. In this paper, we consider presence of continuous covariates with heterogeneous location conditional dispersion matrices. The continuous covariates have equal location specific mean in both populations. Conditional homoscedasticity fails when strong interaction between the continuous and binary variables is present. A plug-in covariance adjusted rule is constructed and its asymptotic distribution is derived. An asymptotic expansion for the overall error rate is given. The result is extended to include binary covariates.     

Solving Nonconvex Planar Location Problems by Finite Dominating Sets

It is well-known that some of the classical location problems with polyhedral gauges can be solved in polynomial time by finding a finite dominating set, i.e. a finite set of candidates guaranteed to contain at least one optimal location.In this paper it is first established that this result holds for a much larger class of problems than currently considered in the literature. The model for which this result can be proven includes, for instance, location problems with attraction and repulsion, and location-allocation problems.Next, it is shown that the approximation of general gauges by polyhedral ones in the objective function of our general model can be analyzed with regard to the subsequent error in the optimal objective value. For the approximation problem two different approaches are described, the sandwich procedure and the greedy algorithm. Both of these approaches lead - for fixed - to polynomial approximation algorithms with accuracy for solving the general model considered in this paper.     

Fixed Point Optimality Criteria for the Location Problem with Arbitrary Norms

The single-facility location problem in continuous space is considered, with distances given by arbitrary norms. When distances are Euclidean, for many practical problems the optimal location of the new facility coincides with one of the existing facilities. This property carries over to problems with generalized distances. In this paper a necessary and sufficient condition for the location of an existing facility to be the optimal location of the new facility is developed. Some computational examples using the condition are given.     

矩阵的酉不变范数不等式

利用凹函数和半正定矩阵的性质,讨论并且得到了一些矩阵Rotfel型范数不等式.另外,通过研究Hermitian矩阵和斜Hermitian矩阵和的特征值的模行列式的不等式,得到一些关于Hermitian矩阵和斜Hermitian矩阵和的范数不等式.推广了文献中的相关结果.     

Globally and Quadratically Convergent Algorithm for Minimizing the Sum of Euclidean Norms

For the problem of minimizing the sum of Euclidean norms (MSN), most existing quadratically convergent algorithms require a strict complementarity assumption. However, this assumption is not satisfied for a number of MSN problems. In this paper, we present a globally and quadratically convergent algorithm for the MSN problem. In particular, the quadratic convergence result is obtained without assuming strict complementarity. Examples without strictly complementary solutions are given to show that our algorithm can indeed achieve quadratic convergence. Preliminary numerical results are reported.     

干线网络的选址问题研究

考虑平面上和三维空间中同时确定多条干线的干线网络选址问题.对于平面上情形,通过最小化每个点到离它最近干线的加权距离之和,给出了一种有限步终止算法和基于k-means聚类分析、加权全最小一乘和重抽样方法的线性类算法;对于空间情形,给出了线性聚类算法.通过计算机仿真说明以上算法可以有效地确定平面和空间中干线网络位置.     

A Calculus of Boundary Value Problems in Domains with Non–Lipschitz Singula Points

The paper is devoted to pseudodifferential boundary value problems in domains with singular points on the boundary. The tangent cone at a singular point is allowed to degenerate. In particular, the boundary may rotate and oscillate in a neighbourhood of such a point. We show a criterion for the Fredholm property of a boundary value problem and derive estimates of solutions close to singular points.