共查询到20条相似文献,搜索用时 15 毫秒
1.
Horst Hamacher 《Operations Research Letters》1982,1(5):186-189
An algorithm for finding the K best cuts in a network is presented. Using a branch technique introduced by Lawler [4] we reduce the problem to K computations of 2nd best cuts. The latter problem can be solved by an O(n4) algorithm yielding an overall complexity of O(K·n4) for the presented algorithm. 相似文献
2.
Kenjiro Takazawa 《Mathematical Programming》2012,132(1-2):261-276
An even factor in a digraph is a vertex-disjoint collection of directed cycles of even length and directed paths. An even factor is called independent if it satisfies a certain matroid constraint. The problem of finding an independent even factor of maximum size is a common generalization of the nonbipartite matching and matroid intersection problems. In this paper, we present a primal-dual algorithm for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs. Cunningham and Geelen have shown that this problem is solvable via valuated matroid intersection. Their method yields a combinatorial algorithm running in O(n 3 γ +? n 6 m) time, where n and m are the number of vertices and edges, respectively, and γ is the time for an independence test. In contrast, combining the weighted even factor and independent even factor algorithms, our algorithm works more directly and runs in O(n 4 γ?+?n 5) time. The algorithm is fully combinatorial, and thus provides a new dual integrality theorem which commonly extends the total dual integrality theorems for matching and matroid intersection. 相似文献
3.
We consider a deterministic lot-sizing problem with demand time windows, where speculative motive is allowed. Utilizing an untraditional decomposition principle, we provide an optimal algorithm that runs in O(nT3) time, where n is the number of demands and T is the length of the planning horizon. 相似文献
4.
Given a rectangle A and a set S of n points in A, we consider the problem, called the maximum empty rectangle problem, of finding a maximum area rectangle that is fully contained in A and does not contain any point of S in its interior. An O(n2) time algorithm is presented. Furthermore, it is shown that if the points of S are drawn randomly and independently from A, the problem can be solved in O(n(log n)2) expected time. 相似文献
5.
In this paper, we first present an O(n+m)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G, respectively. This algorithm is faster than the previous best known algorithm for the problem which takes O(n2) time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(logn) time using O((n+m)/logn) processors on an EREW PRAM. 相似文献
6.
Mahmut Parlar 《European Journal of Operational Research》1985,20(2):255-260
This paper deals with the optimal production planning for a single product over a finite horizon. The holding and production costs are assumed quadratic as in Holt, Modigliani, Muth and Simon (HMMS) [7] model. The cumulative demand is compound Poisson and a chance constraint is included to guarantee that the inventory level is positive with a probability of at least α at each time point. The resulting stochastic optimization problem is transformed into a deterministic optimal control problem with control variable and of the optimal solution is presented. The form of state variable inequality constraints. A discussion the optimal control (production rate) is obtained as follows: if there exists a time t1 such that t1?[O, T]where T is the end of the planning period, then (i) produce nothing until t1 and (ii) produce at a rate equal to the expected demand plus a ‘correction factor’ between t1 and T. If t1 is found to be greater than T, then the optimal decision is to produce nothing and always meet the demand from the inventory. 相似文献
7.
Peter Brucker 《Operations Research Letters》1984,3(3):163-166
An algorithm is presented which solves bounded quadratic optimization problems with n variables and one linear constraint in at most O(n) steps. The algorithm is based on a parametric approach combined with well-known ideas for constructing efficient algorithms. It improves an O(n log n) algorithm which has been developed for a more restricted case of the problem. 相似文献
8.
The connectivity problem is a fundamental problem in graph theory. The best known algorithm to solve the connectivity problem on general graphs withn vertices andm edges takesO(K(G)mn 1.5) time, whereK(G) is the vertex connectivity ofG. In this paper, an efficient algorithm is designed to solve vertex connectivity problem, which takesO(n 2) time andO(n) space for a trapezoid graph. 相似文献
9.
Finite tight frames are widely used for many applications. An important problem is to construct finite frames with prescribed norm for each vector in the tight frame. In this paper we provide a fast and simple algorithm for such a purpose. Our algorithm employs the Householder transformations. For a finite tight frame consisting of m vectors in ?n or ?n only O(nm) operations are needed. In addition, we also study the following question: Given a set of vectors in ?n or ?n, how many additional vectors, possibly with constraints, does one need to add in order to obtain a tight frame? 相似文献
10.
《European Journal of Operational Research》2005,165(3):649-656
An O(n2) algorithm is presented for the n jobs m parallel machines problem with identical processing times. Due dates for each job are given and the objective is the minimization of the number of late jobs. Preemption is permitted. The problem can be formulated as a maximum flow network model. The optimality proof as well as other properties and a complete example are given. 相似文献
11.
An algorithm for solving m×n systems of (max,+)-linear equations is presented. The systems have variables on both sides of the equations. After O(m4n4) iterations the algorithm either finds a solution of the system or finds out that no solution exists. Each iteration needs O(mn) operations so that the complexity of the presented algorithm is O(m5n5). 相似文献
12.
《Operations Research Letters》1988,7(3):155-158
We present a sequential dual-simplex algorithm for the linear problem which has the same complexity as the algorithms of Balinski [3,4] and Goldfarb [8]: O(n2) pivots, O(n2 log n + nm) time. Our algorithm works with the (dual) strongly feasible trees and can handle rectangular systems quite naturally. 相似文献
13.
Russell R. Barton 《European Journal of Operational Research》1984,15(2):203-211
Algorithms for clustering n objects typically require O(n2) operations. This report presents a special approach for a certain class of data that requires O(n) operations and O(n) storage. Such data commonly occur when a microscopic signal structure is imposed on a medium with potential for macroscopic defects, and the signal elements are then checked sequentially for error. The algorithm can be used to cluster other classes of data in O(n log n) operations. An application to videodisc defect consolidation is presented. 相似文献
14.
15.
Robert Endre Tarjan 《Operations Research Letters》1984,2(6):265-268
Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n ? 1 so-called ‘blocking flow’ problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n2). Karzanov devised the first O(n2)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n2)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method. 相似文献
16.
In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ*/logΔ*) of the optimum in O(mnlogn)-time, where Δ* is the minimum k such that there is a spanning tree of the graph with maximum degree k. 相似文献
17.
Uzi Vishkin 《Discrete Applied Mathematics》1984,9(2):197-207
A synchronized parallel algorithm of depth O(n2/p) for p (≤n2/log2n) processors is given for the problem of computing connected components of an undirected graph. The speed-up of this algorithm is optimal in the sense that the depth of the algorithm is of the order of the running time of the fastest known sequential algorithm over the number of processors used. 相似文献
18.
Blanka Seman?íková 《Linear algebra and its applications》2006,414(1):38-63
Properties of orbits in max-min algebra are described, mainly the properties of periodic orbits. An O(n3) algorithm computing the period of a periodic orbit is presented. As a consequence, an O(n3 log n) algorithm computing the period of arbitrary orbit is obtained, as the pre-periodic part of the orbit has length at most (n − 1)2 + 1. 相似文献
19.
Antoon Kolen 《European Journal of Operational Research》1983,12(3):266-278
Given a tree network on n vertices, a neighborhood subtree is defined as the set of all points on the tree within a certain radius of a given point, called the center. It is shown that for any two neighborhood subtrees containing the same endpoint of a longest path in the tree one is contained in the other. This result is then used to obtain O(n2) algorithms for the minimum cost covering problem and the minimum cost operating problem as well as an O(n3) algorithm for the uncapacitated plant location problem on the tree. 相似文献
20.
《Discrete Applied Mathematics》1988,21(3):177-183
We give a linear time reduction of the problem of finding a minimum independent dominating set in a permutation graph, into that of finding a shortest maximal increasing subsequence. We then give an O(n log2n)-time algorithm for solving the second (and hence the first) problem. This improves on the O(n3)-time algorithm given in [4] for solving the problem of finding a minimum independent dominating set in a permutation graph. 相似文献