In Genetic algorithm (GA), the prevalent approach to population initialization are heuristics and randomization. Unlike approximation algorithms (AA), these methods do not provide a guarantee to the generated individu...
详细信息
ISBN:
(纸本)9781538621264
In Genetic algorithm (GA), the prevalent approach to population initialization are heuristics and randomization. Unlike approximation algorithms (AA), these methods do not provide a guarantee to the generated individual's quality in terms of optimality. Surprisingly, no literature to this date has attempted using AA as a population initialization method. Hence, we seek to improve upon the state of the art for NP-complete problem by presenting an implementation of AA at a GA's initial population. We tested this approach by sampling the populations for some Set Covering Problems from OR Library using the randomized rounding method (AAR) and compared them with that sampled using a randomized heuristics (R) in terms of redundancy rate, diversity and closeness to the optimal solution (OPT). Then, we tested three types of GA;R-GA with R-sampled initial population, AAR-GA with AAR-sampled initial population and S-GA with a combined R-AAR initial population and their performances are compared in terms of the best solution found(BFS) and the average number of iterations required to reach BFS. Results suggested that AAR has the potential of generating better starting populations compared to the traditional random heuristics.
In this paper, we consider the balanced Max-3-Uncut problem which has several applications in the design of VLSI circuits. We propose a complex discrete linear program for the balanced Max-3-Uncut problem. Applying th...
详细信息
ISBN:
(纸本)9783319087832;9783319087825
In this paper, we consider the balanced Max-3-Uncut problem which has several applications in the design of VLSI circuits. We propose a complex discrete linear program for the balanced Max-3-Uncut problem. Applying the complex semidefinite programming rounding technique, we present a 0.3456-approximation algorithm by further integrating a greedy swapping process after the rounding step. One ingredient in our analysis different from previous work for the traditional Max-3-Cut is the introduction and analysis of a bivariate function rather than a univariate function.
Correlation clustering problem is a classical clustering problem and has many applications in protein interaction networks, cross-lingual link detection, communication networks, etc. In this paper, we discuss the capa...
详细信息
ISBN:
(数字)9783030926816
ISBN:
(纸本)9783030926816;9783030926809
Correlation clustering problem is a classical clustering problem and has many applications in protein interaction networks, cross-lingual link detection, communication networks, etc. In this paper, we discuss the capacitated correlation clustering problem on labeled complete graphs, in which each edge is labeled + or - to indicate two endpoints are "similar" or "dissimilar", respectively. Our objective is to partition the vertex set into several clusters, subject to an upper bound on cluster size, so as to minimize the number of disagreements. Here the number of disagreements is defined as the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. The main contribution of this work is providing a 5.37-approximation algorithm for the capacitated correlation clustering problem, improving the current best approximation ratio of 6 [21]. In addition, we have conducted a series of numerical experiments, which effectively demonstrate the effectiveness of our algorithm.
A network of many sensors and a base station that are deployed over a region is considered. Each sensor has a transmission range, a interference range, and a carrier sensing range, which is tau, alpha tau, and beta r,...
详细信息
ISBN:
(纸本)9783642034169
A network of many sensors and a base station that are deployed over a region is considered. Each sensor has a transmission range, a interference range, and a carrier sensing range, which is tau, alpha tau, and beta r, respectively. In this paper, we study the minimum latency conflict-aware many-to-one data aggregation scheduling problem: Given locations of sensors along with a base station, a subset of sensors, and parameters tau, alpha, and beta, find a schedule in which the data of each sensor in the subset can be transmitted to the base station with no conflicts, such that the latency is minimized. We designed an nearly a constant ratio approximation algorithm and a heuristic algorithm for the problem. Extensive simulations have been done to show the performances of the two algorithms.
The minimum vertex cover problem is a basic combinatorial optimization problem. Given an undirected graph the objective is to determine a subset of the vertices which covers all edges such that the number of the verti...
详细信息
The minimum vertex cover problem is a basic combinatorial optimization problem. Given an undirected graph the objective is to determine a subset of the vertices which covers all edges such that the number of the vertices in the subset is minimized. In the paper, based on Dijkstra algorithm, an approximation algorithm is obtained for the minimum vertex cover problem. In the process of getting a vertex cover, the maximum value of shortest paths is considered as a standard, and some criteria are defined. The time complex of the algorithm is O(n(3)), where n is the number of vertices in a graph. In the end, an example is given to illustrate the process and the validity of the algorithm. (C) 2016 Published by Elsevier Ltd.
作者：
Dai, HanYunnan Univ
Sch Math & Stat Kunming 650504 Yunnan Peoples R China
Given a set U of n users and a set S of m sensors on the plane, each sensor s has the same integer capacity C, and each user u has an integer demand d(u). Each sensor s regulates its power p(s) to form a circular cove...
详细信息
ISBN:
(纸本)9789811981517;9789811981524
Given a set U of n users and a set S of m sensors on the plane, each sensor s has the same integer capacity C, and each user u has an integer demand d(u). Each sensor s regulates its power p(s) to form a circular coverage area disk(s, r(s)) (i.e. a disk with s as the center and r(s) as the radius), the relationship between the power p(s) and its coverage radius r(s) is: p(s) = c center dot r(s)(alpha), where c > 0, alpha >= 1 are constants. The minimum soft capacitated disk multi-coverage problem is to find a set of disks supported by the power {p(s)}(s is an element of S) such that the number of users assigned to one copy of each disk disk(s, r(s)) is at most C, each user u is allocated at least d(u) times, and minimize the number of selected disks. We obtain a 4-approximation of this problem based on an LP rounding algorithm.
Given a graph, an L(2, 1)-labeling of the graph is an assignment l from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), vertical bar l(u) - l(v)vertical bar >= 2 if u an...
详细信息
ISBN:
(纸本)9783030108014;9783030108007
Given a graph, an L(2, 1)-labeling of the graph is an assignment l from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), vertical bar l(u) - l(v)vertical bar >= 2 if u and v are adjacent, and l(u) not equal l(nu) if u and v are at distance 2. The L(2, 1)-labeling problem is to minimize the span of l (i.e., max(u is an element of V) (l(u)) - min(u is an element of V) (l(u)) + 1). In this paper, we propose a new polynomial-time 116/13-approximation algorithm for L(2, 1)-labeling of unit disk graphs. This improves the previously best known ratio 12.
Cost-aware Targeted Viral Marketing (CTVM), a generalization of Influence Maximization (IM), has received a lot of attentions recently due to its commercial values. Previous approximation algorithms for this problem r...
详细信息
ISBN:
(纸本)9783030349806;9783030349790
Cost-aware Targeted Viral Marketing (CTVM), a generalization of Influence Maximization (IM), has received a lot of attentions recently due to its commercial values. Previous approximation algorithms for this problem required a large number of samples to ensure approximate guarantee. In this paper, we propose an efficient approximation algorithm which uses fewer samples but provides the same theoretical guarantees based on generating and using important samples in its operation. Experiments on real social networks show that our proposed method outperforms the state-of-the-art algorithm which provides the same approximation ratio in terms of the number of required samples and running time.
Based on MFE principle and the relative stability of the n-stems in RNA molecules, Minimum free energy method is adopted widely to predict RNA secondary structure, an improved approximation algorithm is presented to p...
详细信息
ISBN:
(纸本)9781467322379
Based on MFE principle and the relative stability of the n-stems in RNA molecules, Minimum free energy method is adopted widely to predict RNA secondary structure, an improved approximation algorithm is presented to predict RNA pseudoknotted structure, the algorithm can solve arbitrary nested or parallel pseudoknots the algorithm takes O(n(3)) time and O(n(2)) space. This algorithm not only reduces the time complexity to O(n(3)), but also widens the maximum length of the sequence. The preliminary experimental test on the RNA sub-sequences in PseudoBase confirm that the algorithm outperforms other known algorithms in predicting accuracy, sensitivity and specificity.
Clustering large data is a fundamental task with widespread applications. The distributed computation methods have received greatly attention in recent years due to the increasing size of data. In this paper, we consi...
详细信息
ISBN:
(纸本)9789819723393;9789819723409
Clustering large data is a fundamental task with widespread applications. The distributed computation methods have received greatly attention in recent years due to the increasing size of data. In this paper, we consider a variant of the widely used k-center problem, i.e., the lower-bounded k-center problem, and study the lower-bounded k-center problem in the Massively Parallel Computation (MPC) model. The lower-bounded k-center problem takes as input a set C of points in a metric space, the desired number k of centers, and a lower bound L. The goal is to partition the set C into at most k clusters such that the number of points in each cluster is at least L, and the k-center clustering objective is minimized. The current best result for the above problem in the MPC model is 16-approximation algorithm with 4 rounds. In this paper, we obtain a 2-round (7+ epsilon)-approximation algorithm for this problem in the MPC model.
暂无评论