For a given weighted digraph D =（V, A;s, t;w, c;B）, certain stock pieces of length L and an unit price c for each stock piece, where a length function w: A → Z, a construction cost function c: A → Z0 and a constan...
详细信息
For a given weighted digraph D =（V, A;s, t;w, c;B）, certain stock pieces of length L and an unit price c for each stock piece, where a length function w: A → Z, a construction cost function c: A → Z0 and a constant positive integer B, we are asked to construct a path P from s to t in D, having total length ∑w（ e）≤ B, such that the arcs in P are to be cut from some stock pieces of length L, the new objective is to minimize the total cost ∑c（ e） k（ P）c where k（ P） , denotes the number of necessary stock pieces to construct the arcs in P. Moreover, we consider a special version of this problem, where c（e） =0 holds for each arc e ∈A. We design two asymptotic approximation algorithms to solve them, respectively.
We study polynomial-time clearing algorithms for the barter exchange problem. We put forward a family of carefully designed approximation algorithms with desirable worst-case guarantees We further apply a series of no...
详细信息
ISBN:
(纸本)9781510855076
We study polynomial-time clearing algorithms for the barter exchange problem. We put forward a family of carefully designed approximation algorithms with desirable worst-case guarantees We further apply a series of novel heuristics to implement these algorithms. We demonstrate via kidney exchange data sets that these algorithms achieve near-optimal performances while outperforming the state-of-the-art ILP based algorithms in running time by orders of magnitude.
This monograph develops an algorithmic theory of nonlinear discrete optimization. It introduces a simple and useful setup which enables the polynomial time solution of broad fundamental classes of nonlinear combinator...
详细信息
ISBN:
(数字)9783037195932
ISBN:
(纸本)9783037190937
This monograph develops an algorithmic theory of nonlinear discrete optimization. It introduces a simple and useful setup which enables the polynomial time solution of broad fundamental classes of nonlinear combinatorial optimization and integer programming problems in variable dimension. An important part of this theory is enhanced by recent developments in the algebra of Graver bases. The power of the theory is demonstrated by deriving the first polynomial time algorithms in a variety of application areas within operations research and statistics, including vector partitioning, matroid optimization, experimental design, multicommodity flows, multi-index transportation and privacy in statistical databases. The monograph is intended for graduate students and researchers. It is accessible to anyone with standard undergraduate knowledge and mathematical maturity.
By applying Ant-Cycle model of Ant Colony algorithm, and modifying the state transition probability, an approximation algorithm is obtained for the minimum vertex cover problem. The time complex of the algorithm i...
详细信息
ISBN:
(纸本)9781622761227
By applying Ant-Cycle model of Ant Colony algorithm, and modifying the state transition probability, an approximation algorithm is obtained for the minimum vertex cover problem. The time complex of the algorithm is o{n2), where n is the number of vertices in a network. In the end, an example is given to illustrate the process of the algorithm.
A new mathematical problem, namely searching a connected dominating set(CDS) with the minimum total edge weight in an edge-weighted graph which can provide a better mathematical model for wireless networks, has been b...
详细信息
A new mathematical problem, namely searching a connected dominating set(CDS) with the minimum total edge weight in an edge-weighted graph which can provide a better mathematical model for wireless networks, has been brought forward from the design of wireless networksTo solve this problem, an approximation algorithm with polynomial-time complexity is proposed in this paperThe simulation results demonstrate the effectiveness of the proposed algorithm, and the results also show that the approximation ratio of the proposed algorithm is up to 0.7.
This paper investigates a new strategy to best deploy road side units so that their spatio-temporal coverage is maximized under a limited budget. For the first time in the literature, we consider three different RSU d...
详细信息
ISBN:
(纸本)9781467385800
This paper investigates a new strategy to best deploy road side units so that their spatio-temporal coverage is maximized under a limited budget. For the first time in the literature, we consider three different RSU deployment strategies in a single framework, on static locations, public mobile transportation, and fully controllable vehicles. We first introduce a new strategy to abstract a map of city area into a grid graph. Then, we formulate the problem as a new optimization problem and show its NP-hardness. To solve this problem, we transform this problem into another optimization problem and propose a new polynomial running time approximation algorithm and show its performance ratio is at least the half of the best possible ratio.
Based on the theories and methods of operations research,a mathematical model for the short est rescue route during gas leak emergencies in high-sulfur oil and gas fields is built in this pap er,which contains two wei...
详细信息
ISBN:
(纸本)9781479900305
Based on the theories and methods of operations research,a mathematical model for the short est rescue route during gas leak emergencies in high-sulfur oil and gas fields is built in this pap er,which contains two weights of rescue rout e optimization,and serves the bi-objective optimization *** approximate search algorithm with two optimization objectives is proposed for the model based on heuristic algorithm,which could find out the shortest escape route from the double-weight escape route network by construct ing anxiliary *** the study case of the gas leak emergency rescue system of the Puguang gas field in Sichnan,the algorithm procedures are introduced,the convergence rate of the algorithm are analyzed,and the time complexity and the strengths of the algorithm are *** this algorithm,decision makers can find out the optimum rescue route on the distribution sketch map of the Puguang gas field,thus realizing the two optimizing targets,and providing strong technical support for gas leak rescue in the gas field.
We consider the path cover problem which is to find a set of vertex-disjoint paths for a simple undirectedgraph with maximum number of edges to cover all vertices of this *** path cover problem isNP-hard because the w...
详细信息
We consider the path cover problem which is to find a set of vertex-disjoint paths for a simple undirectedgraph with maximum number of edges to cover all vertices of this *** path cover problem isNP-hard because the well known Hamilton path problem is NP complete and the Hamilton path problemis a special case of the path cover *** this paper we present a new upper bound for the size of asolution of the path cover problem We believe that the upper bound is useful for our future *** application,we devise a 7-10approximation algorithm whose time complexity is O(|V‖E|1.5log(|V|))where |V| is the number of vertices and |E| is the number of edges of a *** that the bestapproximation ratio is 6-7 which is achieved by Berman et al[20].However,their algorithm has timecomplexity O(|V|9) which is much slower than ours.
Transpositions are large-scale mutational events that occur when a block of genes moves from a region of a chromosome to another region within the same chromosome. The transposition distance problem is the minimum num...
详细信息
Transpositions are large-scale mutational events that occur when a block of genes moves from a region of a chromosome to another region within the same chromosome. The transposition distance problem is the minimum number of transpositions required to transform one genome into another. Recently, Bulteau et al. [Bulteau L, Fertin G, Rusu U, Automata, Languages and Programming, Vol. 6755 of Lecture Notes in Computer Science, pp. 654-665, Springer Berlin, Heidelberg, 2011] proved that finding the transposition distance is a NP-Hard problem. Some approximation algorithm for this problem have been presented to date [Bafna V, Pevzner PA, SIAM J Discr Math 11(2): 224-240, 1998;Elias I, Hartman T, IEEE/ACM Trans Comput Biol Bioinform 3(4): 369-379, 2006;Mira CVG, Dias Z, Santos HP, Pinto GA, Walter ME, Proc 3rd Brazilian Symp Bioinformatics (BSB'2008), pp. 115-126, Santo Andre, Brazil, 2008;Walter MEMT, Dias Z, Meidanis J, Proc String Processing and Information Retrieval (SPIRE'2000), pp. 199-208, Coruna, Spain, 2000]. Here we focus on developing heuristics to provide an improved approximated solution. Our approach outperforms other algorithms on small sized permutations. We also show that our algorithm keeps the good performance on longer permutations.
暂无评论