共查询到20条相似文献,搜索用时 859 毫秒
1.
Maxim Sviridenko 《Operations Research Letters》2004,32(1):41-43
In this paper, we obtain an (1−e−1)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint. This algorithm requires O(n5) function value computations. 相似文献
2.
Computational Experience with a New Class of Convex Underestimators: Box-constrained NLP Problems 总被引:7,自引:3,他引:4
Ioannis G. Akrotirianakis Christodoulos A. Floudas 《Journal of Global Optimization》2004,29(3):249-264
In Akrotirianakis and Floudas (2004) we presented the theoretical foundations of a new class of convex underestimators for C
2 nonconvex functions. In this paper, we present computational experience with those underestimators incorporated within a Branch-and-Bound algorithm for box-conatrained problems. The algorithm can be used to solve global optimization problems that involve C
2 functions. We discuss several ways of incorporating the convex underestimators within a Branch-and-Bound framework. The resulting Branch-and-Bound algorithm is then used to solve a number of difficult box-constrained global optimization problems. A hybrid algorithm is also introduced, which incorporates a stochastic algorithm, the Random-Linkage method, for the solution of the nonconvex underestimating subproblems, arising within a Branch-and-Bound framework. The resulting algorithm also solves efficiently the same set of test problems. 相似文献
3.
The notion of a centerpoint of a finite set of points in two and higher dimensions is a generalization of the concept of the
median of a set of reals. In this paper we present a linear-time algorithm for computing a centerpoint of a set ofn points in the plane, which is optimal compared with theO(n log3
n) complexity of the previously best-known algorithm. We use suitable modifications of the hamsandwich cut algorithm in [Me2]
and the prune-and-search technique of Megiddo [Me1] to achieve this improvement. 相似文献
4.
Dvir Shabtay 《European Journal of Operational Research》2012,216(3):521-532
We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n3) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n3) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn2) time optimization algorithm. 相似文献
5.
Pankaj K. Agarwal Herbert Edelsbrunner Yusu Wang 《Discrete and Computational Geometry》2004,32(1):37-53
The writhing number measures the global geometry of
a closed space curve or knot.
We show that this measure is related to the average winding number
of its Gauss map.
Using this relationship, we give an algorithm for computing
the writhing number for a polygonal knot with n edges
in time roughly proportional to n1.6.
We also implement a different, simple algorithm and provide
experimental evidence for its practical efficiency. 相似文献
6.
Justo Puerto Antonio M. Rodríguez-Chía 《Mathematical Methods of Operations Research》2006,63(1):31-51
In this paper we analyze a new location problem which is a generalization of the well-known single facility location model.
This extension consists of introducing a general objective function and replacing fixed locations by trajectories. We prove
that the problem is well-stated and solvable. A Weiszfeld type algorithm is proposed to solve this generalized dynamic single
facility location problem on L
p
spaces of functions, with p ∈(1,2]. We prove global convergence of our algorithm once we have assumed that the set of demand functions and the initial
step function belong to a subspace of L
p
called Sobolev space. Finally, examples are included illustrating the application of the model to generalized regression
analysis and the convergence of the proposed algorithm. The examples also show that the pointwise extension of the algorithm
does not have to converge to an optimal solution of the considered problem while the proposed algorithm does. 相似文献
7.
We present an O(n2) algorithm for finding a specified oriented path of order at least n in a tournament of order n. Using this algorithm, we present an O(n2) algorithm that finds a specified oriented path from a given vertex if one exists. 相似文献
8.
This paper is concerned with a three-level alternating direction implicit (ADI) method for the numerical solution of a 3D hyperbolic equation. Stability criterion of this ADI method is given by using von Neumann method. Meanwhile, it is shown by a discrete energy method that it can achieve fourth-order accuracy in both time and space with respect to H 1- and L 2-norms only if stable condition is satisfied. It only needs solution of a tri-diagonal system at each time step, which can be solved by multiple applications of one-dimensional tri-diagonal algorithm. Numerical experiments confirming the high accuracy and efficiency of the new algorithm are provided. 相似文献
9.
T. M. Tovstik 《Vestnik St. Petersburg University: Mathematics》2007,40(3):250-252
An algorithm for calculating the discrepancy of finitely many points in the unit n-cube [0, 1]n is suggested. This algorithm is easy to program. For 2 ≤ n ≤ 4, the suggested algorithm is significantly faster than Bundschuh and Zhu’s algorithm. For larger n, whether this algorithm is faster depends on the number of points. 相似文献
10.
Optimally Cutting a Surface into a Disk 总被引:1,自引:0,他引:1
We consider the problem of cutting a subset of the edges of a polyhedral manifold
surface, possibly with boundary, to obtain a single topological disk, minimizing
either the total number of cut edges or their total length. We show that this
problem is NP-hard in general, even for manifolds without boundary and for punctured
spheres. We also describe an algorithm with running time n
O(g+k), where n is
the combinatorial complexity, g is the genus, and k is the number of boundary
components of the input surface. Finally, we describe a greedy algorithm that
outputs a O(log2
g)-approximation of the minimum cut graph in O(g
2
n log n)
time. 相似文献
11.
《Journal of Computational and Applied Mathematics》1997,83(2):147-163
In this paper, an iterative algorithm for solving singular nonlinear two-point boundary value problems is formulated. This method is basically a collocation method for nonlinear second-order two-point boundary value problems with singularities at either one or both of the boundary points. It is proved that the iterative algorithm converges to a smooth approximate solution of the BVP provided the boundary value problem is well posed and the algorithm is applied appropriately. Error estimates for uniform partitions are also investigated. It has been shown that, for sufficiently smooth solutions, the method produces order h4 approximations. Numerical examples are provided to show the effectiveness of the algorithm. 相似文献
12.
Yang Liu Nan Liu Hong Li Jinfeng Wang 《Numerical Methods for Partial Differential Equations》2020,36(6):1904-1921
In this article, a spatial two-grid finite element (TGFE) algorithm is used to solve a two-dimensional nonlinear space–time fractional diffusion model and improve the computational efficiency. First, the second-order backward difference scheme is used to formulate the time approximation, where the time-fractional derivative is approximated by the weighted and shifted Grünwald difference operator. In order to reduce the computation time of the standard FE method, a TGFE algorithm is developed. The specific algorithm is to iteratively solve a nonlinear system on the coarse grid and then to solve a linear system on the fine grid. We prove the scheme stability of the TGFE algorithm and derive a priori error estimate with the convergence result O(Δt2 + hr + 1 − η + H2r + 2 − 2η) . Finally, through a two-dimensional numerical calculation, we improve the computational efficiency and reduce the computation time by the TGFE algorithm. 相似文献
13.
Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn
1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n
3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n
3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn
1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn
1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688 相似文献
14.
15.
Automatic parallel generation of tetrahedral grids by using a domain decomposition approach 总被引:1,自引:0,他引:1
H. Andrä O. N. Gluchshenko E. G. Ivanov A. N. Kudryavtsev 《Computational Mathematics and Mathematical Physics》2008,48(8):1367-1375
An algorithm for the automatic parallel generation of three-dimensional unstructured grids based on geometric domain decomposition is proposed. A software package based on this algorithm is described. Examples of generating meshes for some application problems on a multiprocessor computer are presented. It is shown that the parallel algorithm can significantly (by a factor of several tens) reduce the mesh generation time. Moreover, it can easily generate meshes with as many as 5 × 107 elements, which can hardly be generated sequentially. Issues concerning the speedup and the improvement of the efficiency of the computations and of the quality of the resulting meshes are discussed. 相似文献
16.
Gautam M. Shroff 《Numerische Mathematik》1990,58(1):779-805
Summary A new parallel Jacobi-like algorithm is developed for computing the eigenvalues of a general complex matrix. Most parallel methods for this problem typically display only linear convergence, Sequential norm-reducing algorithms also exist and they display quadratic convergence in most cases. The new algorithm is a parallel form of the norm-reducing algorithm due to Eberlein. It is proven that the asymptotic convergence rate of this algorithm is quadratic. Numerical experiments are presented which demonstrate the quadratic convergence of the algorithm and certain situations where the convergence is slow are also identified. The algorithm promises to be very competitive on a variety of parallel architectures. In particular, the algorithm can be implemented usingn
2/4 processors, takingO(n log2
n) time for random matrices.This research was supported by the Office of Naval Research under Contract N00014-86-k-0610 and by the U.S. Army Research Office under Contract DAAL 03-86-K-0112. A portion of this research was carried out while the author was visiting RIACS, Nasa Ames Research Center 相似文献
17.
Numerical Experience with a Reduced Hessian Method for Large Scale Constrained Optimization 总被引:4,自引:0,他引:4
Lorenz T. Biegler Jorge Nocedal Claudia Schmid David Ternet 《Computational Optimization and Applications》2000,15(1):45-67
The reduced Hessian SQP algorithm presented in Biegler et al. [SIAM J. Optimization, Vol. 5, no. 2, pp. 314–347, 1995.] is developed in this paper into a practical method for large-scale optimization. The novelty of the algorithm lies in the incorporation of a correction vector that approximates the cross term ZTWYpY. This improves the stability and robustness of the algorithm without increasing its computational cost. The paper studies how to implement the algorithm efficiently, and presents a set of tests illustrating its numerical performance. An analytic example, showing the benefits of the correction term, is also presented. 相似文献
18.
The result that for quadratic functions the classical steepest descent algorithm in R
d
converges locally to a two-point attractor was proved by Akaike. In this paper this result is proved for bounded quadratic operators in Hilbert space. The asymptotic rate of convergence is shown to depend on the starting point while, as expected, confirming the Kantorovich bounds. The introduction of a relaxation coefficient in the steepest-descent algorithm completely changes its behaviour, which may become chaotic. Different attractors are presented. We show that relaxation allows a significantly improved rate of convergence. 相似文献
19.
In this paper we propose an O(n
3
L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n
3
L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n
3
L).Research supported in part by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research supported in part by NSF grants ECS-8602534 and DMS-8904406 and ONR contract N-00014-87-K0212. 相似文献
20.
We show that a fast algorithm for theQR factorization of a Toeplitz or Hankel matrixA is weakly stable in the sense thatR
T
R is close toA
T
A. Thus, when the algorithm is used to solve the semi-normal equationsR
TRx=AT
b, we obtain a weakly stable method for the solution of a nonsingular Toeplitz or Hankel linear systemAx=b. The algorithm also applies to the solution of the full-rank Toeplitz or Hankel least squares problem min ||Ax-b||2. 相似文献