共查询到20条相似文献,搜索用时 15 毫秒
1.
The 1-center problem in the plane with random weights has only been studied for a few specific probability distributions and distance measures. In this paper we deal with this problem in a general framework, where weights are supposed to be independent random variables with arbitrary probability distributions and distances are measured by any norm function. Two objective functions are considered to evaluate the performance of any location. The first is defined as the probability of covering all demand points within a given threshold, the second is the threshold for which the probability of covering is bounded from below by a given value. We first present some properties related to the corresponding optimization problems, assuming random weights with both discrete and absolutely continuous probability distributions. For weights with discrete distributions, enumeration techniques can be used to solve the problems. For weights continuously distributed, interval branch and bound algorithms are proposed to solve the problems whatever the probability distributions are. Computational experience using the uniform and the gamma probability distributions is reported. 相似文献
2.
This article discusses modification of the shape of a plane elastic body whose uncontrolled geometric configuration is an annulus, fixed along its interior boundary and free on its outer boundary. The paper discusses the use of radial and circumferential actuators, each of so-called monotropic type, to produce strictly radial deformations of the elastic structure so as to achieve target configurations, or shapes, in a specific class. 相似文献
3.
LetU andV be two sets of points in the plane, where ¦U¦=k,¦V¦=, andn=k+. These two sets of points induce a directed complete bipartite graph in which the points represent nodes and an edge is directed from each node inU to each node in K Each edge is given a cost equal to the distance between the corresponding nodes measured by some metricd on the plane. We consider thetransportation problem on such a graph. We present an 0(n2,5 logn logN) algorithm, whereN is the magnitude of the largest supply or demand. The algorithm uses some fundamental results of computational geometry and scaling of supplies and demands. The algorithm is valid for the 1 metric, the 2 metric, and the metric. The running time for the 1 and metrics can be improved to 0(n2(logn)3 logN).D. S. Atkinson was supported by the National Science Foundation under Grant CCR90-57481PYI. P. M. Vaidya was supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195. 相似文献
4.
O. G. Mancino 《Calcolo》1976,13(3):299-311
A problem of plane elastic-plastic stress is connected with a varitional problem in an appropriate Hilbert space. Next, the
numerical solution of the latter is considered. Finally, the exact and the approximate solutions of a model problem are compared. 相似文献
5.
This paper presents a new local search for solving the continuous p-median problem in the plane. The basic idea is to first find a good starting solution by overlaying the area containing the set of demand points with a grid and solving heuristically the location problem on this grid. The solution is then used as an initial point for running an improved version of Cooper's well-known alternating local search. 相似文献
6.
7.
《Parallel Computing》1988,7(2):249-251
We describe an O(log(n)) time with O(n) processors optimal algorithm for finding the maximal elements of a set. The model of parallel computation we consider is the CREW-PRAM, i.e. it is the synchronous shared memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). 相似文献
8.
This paper describes an optimal solution for the following geometric search problem defined for a set P of n points in three dimensions: Given a plane h with all points of P on one side and a line ? in h, determine a point of P that is hit first when h is rotated around ?. The solution takes O(n) space and O(log n) time for a query. By use of geometric transforms, the post-office problem for a finite set of points in two dimensions and certain two-dimensional point location problems are reduced to the former problem and thus also optimally solved. 相似文献
9.
10.
P. K. Bhattacharyya 《Computers & Mathematics with Applications》1980,6(4):443-448
The displacement problem of elastostatics in two dimensions is formulated in terms of integral equations via the Airy stress function. The integral equations are solved numerically using piecewise constant approximations to the unknown functions. The validity of the formulation is demonstrated by its application to a simple problem with a known solution. 相似文献
11.
《Journal of Symbolic Computation》2006,41(9):943-958
In this paper we give a very easy to compute necessary condition in the monodromy problem for all singular point of analytic differential systems in the real plane. Our main tool is considering the analytic function, angular speed, and studying its limit through straight lines to the singular point. 相似文献
12.
We consider the optimal placement problem in a bounded region on a plane with fixed objects. We specify minimal admissible distances between placed and fixed objects. The optimization criterion is to maximize the minimal weighted distances from placed objects to fixed ones. We propose a quasipolynomial combinatorial algorithm to solve this problem with a given accuracy. We show the results of a computational experiment with the integer programming model and the IBM ILOG CPLEX suite. 相似文献
13.
14.
The purpose of this article is to discuss some properties of optimal microstructure that are used in the homogenization approach for structural optimization problems involving compliance as the design criterion. The key ingredient for the homogenization method is to allow for microperforated composite materials as admissible designs. Some authors use periodic holes while others rely on optimal microstructures such as the so-called rank-2 layered materials which achieve optimality in the 2-D Hashin-Shtrikman bound. We prove that, in two space dimension, when the eigenvalues of the average stress have opposite signs, there is no optimal periodic microstructure. We also prove in this case that any optimal microstructure is degenerate, like the rank-2 layered material, i.e. it cannot sustain a nonaligned shear stress. When the eigenvalues of the average stress have the same sign, we exhibit higher order layered material that is optimal and not degenerate. 相似文献
15.
16.
Nir Halman 《Information Processing Letters》2003,86(3):121-128
We present an optimal O(n) time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane and prove that calculating the optimal value of the objective function requires Θ(nlogn) time. 相似文献
17.
18.
G. G. Zabudskii 《Automation and Remote Control》2006,67(12):1986-1990
Problems of optimal object location in a plane outside rectangular forbidden gaps are considered. Objects under location are connected with one another and with the objects, located in the same plane. The criteria are the minimization of maximal weighted distance or total cost of the links between objects. A model building procedure of integer linear programming of the problems above for rectangular metric is given. Solution algorithms are briefly described. The outcomes of a numerical experiment are given. 相似文献
19.
We study a bottleneck Steiner tree problem: given a set P={p1,p2,…,pn} of n terminals in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. The problem has applications in the design of wireless communication networks. We give a ratio-1.866 approximation algorithm for the problem. 相似文献
20.
Givenn points in the Euclidean plane, we consider the problem of finding the minimum tree spanning anyk points. The problem isNP-hard and we give anO(logk)-approximation algorithm. 相似文献