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.     

A decomposition algorithm for linear relaxation of the weightedr-covering problem

In this paper the linear relaxation of the weightedr-covering problem (r-LCP) is considered. The dual problem (c-LMP) is the linear relaxation of the well-knownc-matching problem and hence can be solved in polynomial time. However, we describe a simple, but nonpolynomial algorithm in which ther-LCP is decomposed into a sequence of 1-LCP’s and its optimal solution is obtained by adding the optimal solutions of these 1-LCP’s. An 1-LCP can be solved in polynomial time by solving its dual as a max-flow problem on a bipartite graph. An accelerated algorithm based on this decomposition scheme to solve ar-LCP is also developed and its average case behaviour is studied.     

An unfeasible matching problem

LetG be a bipartite graph with natural edge weights, and letW be a function from the set of vertices ofG into natural numbers. AW-matching ofG is a subset of the set of edges ofG such that for each vertexv the total weight of edges in the subset incident tov does not exceedW(v). Letm be a natural number. We show that the problem of deciding whether there is aW-matching inG whose total weight is not less thanm is NP-complete even ifG is bipartite and its edge weights as well as theW(v)-constraints are constantly bounded.     

Thep-facility ordered median problem on networks

In this paper we deal with the ordered median problem: a family of location problems that allows us to deal with a large number of real situations which does not fit into the standard models of location analysis. Moreover, this family includes as particular instances many of the classical location models. Here, we analyze thep-facility version of this problem on networks and our goal is to study the structure of the set of candidate points to be optimal solutions. The research of the authors is partially financed by Spanish research grants BFM2001-2378, BFM2001-4028, BFM2004-0909 and HA2003-0121.     

A clustering approach to the planar hub location problem

The problem tackled in this paper is as follows: consider a set ofn interacting points in a two-dimensional space. The levels of interactions between the observations are given exogenously. It is required to cluster then observations intop groups, so that the sum of squared deviations from the cluster means is as small as possible. Further, assume that the cluster means are adjusted to reflect the interaction between the entities. (It is this latter consideration which makes the problem interesting.) A useful property of the problem is that the use of a squared distance term yields a linear system of equations for the coordinates of the cluster centroids. These equations are derived and solved repeatedly for a given set of cluster allocations. A sequential reallocation of the observations between the clusters is then performed. One possible application of this problem is to the planar hub location problem, where the interacting observations are a system of cities and the interaction effects represent the levels of flow or movement between the entities. The planar hub location problem has been limited so far to problems with fewer than 100 nodes. The use of the squared distance formulation, and a powerful supercomputer (Cray Y-MP) has enabled quick solution of large systems with 250 points and four groups. The paper includes both small illustrative examples and computational results using systems with up to 500 observations and 9 clusters.     

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.     

A matching problem with side conditions

Given a graph G, a 2-matching is an assignment of nonnegative integers to the edges of G such that for each node i of G, the sum of the values on the edges incident with i is at most 2. A triangle-free 2-matching is a 2-matching such that no cycle of size 3 in G has the value 1 assigned to all of its edges. In this paper we describe explicity the convex hull of triangle-free 2-matchings by means of its extreme points and of its facets. We give a polynomially bounded algorithm which maximizes a linear function over the set of triangle-free 2-matchings. Finally we discuss some related problems.     

Extension of an abstract attainability problem with the use of the stone representation space

We consider an attainability problem in a complete metric space on values of an objective operator h. We assume that the latter admits a uniform approximation by mappings which are tier with respect to a given measurable space with an algebra of sets. Let asymptotic-type constraints be defined as a nonempty family of sets in this measurable space. We treat ultrafilters of the measurable space as generalized elements; we equip this space of ultrafilters with a topology of a zero-dimensional compact (the Stone representation space). On this base we construct a correct extension of the initial problem, realizing the set of attraction in the form of a continuous image of the compact of feasible generalized elements. Generalizing the objective operator, we use the limit with respect to ultrafilters of the measurable space. This provides the continuity of the generalized version of h understood as a mapping of the zero-dimensional compact into the topological space metrizable with a total metric.     

An improved approximation ratio for the minimum latency problem

Given a tour visitingn points in a metric space, thelatency of one of these pointsp is the distance traveled in the tour before reachingp. Theminimum latency problem (MLP) asks for a tour passing throughn given points for which the total latency of then points is minimum; in effect, we are seeking the tour with minimum average arrival time. This problem has been studied in the operations research literature, where it has also been termed the delivery-man problem and the traveling repairman problem. The approximability of the MLP was first considered by Sahni and Gonzalez in 1976; however, unlike the classical traveling salesman problem (TSP), it is not easy to give any constant-factor approximation algorithm for the MLP. Recently, Blum et al. (A. Blum, P. Chalasani, D. Coppersimith, W. Pulleyblank, P. Raghavan, M. Sudan, Proceedings of the 26th ACM Symposium on the Theory of Computing, 1994, pp. 163–171) gave the first such algorithm, obtaining an approximation ratio of 144. In this work, we develop an algorithm which improves this ratio to 21.55; moreover, combining our algorithm with a recent result of Garg (N. Garg, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 302–309) provides an approximation ratio of 10.78. The development of our algorithm involves a number of techniques that seem to be of interest from the perspective of the TSP and its variants more generally. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by NSF contract 9302476-CCR and an NEC research grant.Author supported by an ONR Graduate Fellowship.     

A new bound for the ratio between the 2-matching problem and its linear programming relaxation

Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation, the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem. Received August 26, 1996 / Revised version received July 6, 1999? Published online September 15, 1999     

Randomized k-server algorithms for growth-rate bounded graphs

The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total movement cost. While the deterministic competitive ratio is at least k, randomized k-server algorithms have the potential of reaching o(k)-competitive ratios. Prior to this work only few specific cases of this problem were solved. For arbitrary metric spaces, this goal may be approached by using probabilistic metric approximation techniques. This paper gives the first results in this direction, obtaining o(k)-competitive ratio for a natural class of metric spaces, including d-dimensional grids, and wide range of k.     

Inverse problem of finding the coefficient of a lower derivative in a parabolic equation on the plane

We study the existence and uniqueness of the solution of the inverse problem of finding an unknown coefficient b(x) multiplying the lower derivative in the nondivergence parabolic equation on the plane. The integral of the solution with respect to time with some given weight function is given as additional information. The coefficients of the equation depend on the time variable as well as the space variable.     

Heuristics for the fixed cost median problem

We describe in this paper polynomial heuristics for three important hard problems—the discrete fixed cost median problem (the plant location problem), the continuous fixed cost median problem in a Euclidean space, and the network fixed cost median problem with convex costs. The heuristics for all the three problems guarantee error ratios no worse than the logarithm of the number of customer points. The derivation of the heuristics is based on the presentation of all types of median problems discussed as a set covering problem.     

An efficient representation of Benes networks and its applications

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications.     

Sylvester–Gallai Theorem and Metric Betweenness

Sylvester conjectured in 1893 and Gallai proved some 40 years later that every finite set S of points in the plane includes two points such that the line passing through them includes either no other point of S or all other points of S. There are several ways of extending the notion of lines from Euclidean spaces to arbitrary metric spaces. We present one of them and conjecture that, with lines in metric spaces defined in this way, the Sylvester--Gallai theorem generalizes as follows: in every finite metric space there is a line consisting of either two points or all the points of the space. Then we present meagre evidence in support of this rash conjecture and finally we discuss the underlying ternary relation of metric betweenness.     

A simulated annealing approach to the nesting problem in the textile manufacturing industry

The nesting problem in the textile industry is the problem of placing a set of irregularly shaped pieces (calledstencils) on a rectangularsurface, such that no stencils overlap and that thetrim loss produced when cutting out the stencils is minimized. Certain constraints may put restrictions on the positions and orientation of some stencils in the layout but, in general, the problem is unconstrained. In this paper, an algorithmic approach using simulated annealing is presented covering a wide variety of constraints which may occur in the industrial manufacturing process. The algorithm has high performance, is quite simple to use, is extensible with respect to the set of constraints to be met, and is easy to implement.The work of this author was supported in part by grant Le 491/3-1 from the German Research Association (DFG).     

Locally uniform approximation by solutions of the classical Dirichlet problem

LetU be an open subset of aP-harmonic space. It is shown that the space of solutions of the Dirichlet problem onU is dense with respect to locally uniform convergence in the space of Perron-Wiener-Brelot solutions of the generalized Dirichlet problem if and only if the set of irregular boundary points forU is negligible.     

双会议服务器选址问题研究

中位选址问题一直是管理学科的研究热点,本文考虑平面点集选址问题中的双会议服务器选址问题,该问题可以看成是2中位问题的衍生问题。令P为平面上包含n个点的点集,双会议服务器选址问题即为寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并证明所给算法时间复杂性为O(n³logn)。     

一类一维在线单位聚类问题的随机近似算法

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。     

一类一维在线单位聚类问题的随机近似算法

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。