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.
In this paper, we study the link scheduling problem in wireless cooperative communication networks, in which receivers are allowed to combine copies of a message from different senders to combat fading. We formulate a...
详细信息
ISBN:
(纸本)9781467391023
In this paper, we study the link scheduling problem in wireless cooperative communication networks, in which receivers are allowed to combine copies of a message from different senders to combat fading. We formulate a problem called cooperative link scheduling problem (CLS), which aims to find a schedule of links that uses the minimum number of time slots to inform all the receivers. As a solution, we propose an algorithm for CLS with g(Κ) approximation ratio, where g(Κ) is so called diversity of key links. Simulation results indicate that our cooperative link scheduling approaches outperform non-cooperative ones.
We consider AC electrical systems where each electrical device has a power demand expressed as a complex number, and there is a limit on the magnitude of total power supply. Motivated by this scenario, we introduce th...
详细信息
ISBN:
(纸本)9781450319935
We consider AC electrical systems where each electrical device has a power demand expressed as a complex number, and there is a limit on the magnitude of total power supply. Motivated by this scenario, we introduce the complex-demand knapsack problem (C-KP), a new variation of the traditional knapsack problem, where each item is associated with a demand as a complex number, rather than a real number often interpreted as weight or size of the item. While keeping the same goal as to maximize the sum of values of the selected items, we put the capacity limit on the magnitude of the sum of satisfied demands. For C-KP, we prove its inapproximability by FPTAS (unless P = NP), as well as presenting a (1/2 - ε)-approximation algorithm. Furthermore, we investigate the selfish multi-agent setting where each agent is in charge of one item, and an agent may misreport the demand and value of his item for his own interest. We show a simple way to adapt our approximation algorithm to be monotone, which is sufficient for the existence of incentive compatible payments such that no agent has an incentive to misreport. Our results shed insight on the design of multi-agent systems for smart grid.
We consider the problem of sorting signed permutations by reversals, transpositions, transreversals, and block-interchanges. The problem arises in the study of species evolution via large-scale genome rearrangement op...
详细信息
We consider the problem of sorting signed permutations by reversals, transpositions, transreversals, and block-interchanges. The problem arises in the study of species evolution via large-scale genome rearrangement operations. Recently, Hao et al. gave a 2-approximation scheme called genome sorting by bridges (GSB) for solving this problem. Their result extended and unified the results of (i) He and Chen - a 2-approximation algorithm allowing reversals, transpositions, and block-interchanges (by also allowing transversals) and (ii) Hartman and Sharan - a 1.5-approximation algorithm allowing reversals, transpositions, and transversals (by also allowing block-interchanges). The GSB result is based on introduction of three bridge structures in the breakpoint graph, the L-bridge, T-bridge, and X-bridge that models good-reversal, transposition/transreversal, and block-interchange, respectively. However, the paper by Hao et al. focused on proving the 2-approximation GSB scheme and only mention a straightforward O(n(6)) algorithm. In this paper, we give an O(n(3)) algorithm for implementing the GSB scheme. The key idea behind our faster GSB algorithm is to represent cycles in the breakpoint graph by their canonical sequences, which greatly simplifies the search for these bridge structures. We also give some comparison results (running time and computed distances) against the original GSB implementation.
We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite set P of size n, our goal is to find a set C of size k such that the sum of errors D(P, C) = Sigma...
详细信息
We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite set P of size n, our goal is to find a set C of size k such that the sum of errors D(P, C) = Sigma(p is an element of P) min(c is an element of C) {D(p, c)} is minimized. The main result in this article can be stated as follows: There exists a (1 + epsilon)-approximation algorithm for the k-median problem with respect to D, if the I-median problem can be approximated within a factor of (1 + epsilon) by taking a random sample of constant size and solving the I-median problem on the sample exactly. This algorithm requires time n2(O(mklog(mk/epsilon))), where m is a constant that depends only on epsilon and D. Using this characterization, we obtain the first linear time (1 + epsilon)-approximation algorithms for the k-median problem in an arbitrary metric space with bounded doubling dimension, for the Kullback-Leibler divergence (relative entropy), for the Itakura-Saito divergence, for Mahalanobis distances, and for some special cases of Bregman divergences. Moreover, we obtain previously known results for the Euclidean k-median problem and the Euclidean k-means problem in a simplified manner. Our results are based on a new analysis of an algorithm of Kumar et al. [2004].
暂无评论