A complex product can be described in terms of its product architecture. There are two product architectures: integral and modular. Advantages of modular products have been noted in the literature. Maximizing modulari...
详细信息
ISBN:
(纸本)9781728161396
A complex product can be described in terms of its product architecture. There are two product architectures: integral and modular. Advantages of modular products have been noted in the literature. Maximizing modularity is a critical issue in modular product design. In this study, a polynomial approximation algorithm with a 0.422 approximation ratio is proposed to find hidden modules. It is observed that better modularity can be achieved when the product is partitioned into 3 to 8 modules. Numerical experiments with applications in the products of bicycle, starter, and fruit chute system are conducted to illustrate the developed algorithm. Performance of the algorithm is demonstrated by comparisons with other well-known algorithms.
Single machine scheduling is a very fundamental scheduling problem with extensive applications in various areas ranging from computer science to manufacturing. Also, this problem is the building block of different dec...
详细信息
Single machine scheduling is a very fundamental scheduling problem with extensive applications in various areas ranging from computer science to manufacturing. Also, this problem is the building block of different decomposition-based algorithms for shop scheduling problems. Most variants of the single machine scheduling problem are known to be NP-hard, and therefore, many efforts have been devoted to the development of approximation algorithms for solving them. In this paper, we design a parallel randomized approximation algorithm for the non-preemptive single machine scheduling problem with release dates and delivery times (1 vertical bar r(j), q(j)vertical bar C-max), where the objective is to minimize the completion time of all jobs (i.e., makespan). To evaluate the performance of the proposed algorithm, we carry out a comprehensive experimental analysis on several instances of the problem. The results indicate that the proposed parallel algorithm can efficiently solve large instances achieving significant speedup on parallel systems with multiple cores. (C) 2021 Elsevier Ltd. All rights reserved.
Genome Rearrangements affect large stretches of genomes during evolution. One of the most studied genome rearrangement is the transposition, which occurs when a sequence of genes is moved to another position inside th...
详细信息
ISBN:
(纸本)9783030422660;9783030422653
Genome Rearrangements affect large stretches of genomes during evolution. One of the most studied genome rearrangement is the transposition, which occurs when a sequence of genes is moved to another position inside the genome. Mathematical models have been used to estimate the evolutionary distance between two different genomes based on genome rearrangements. However, many of these models have focused only on the (order of the) genes of a genome, disregarding other important elements in it. Recently, researchers have shown that considering existing regions between each pair of genes, called intergenic regions, can enhance the distance estimation in realistic data. In this work, we study the transposition distance between two genomes, but we also consider intergenic regions, a problem we name Sorting Permutations by Intergenic Transpositions (SbIT). We show that this problem is NP-hard and propose a 3.5-approximation algorithm for it.
Proposed algorithms for calculating the shortest paths such as Dijikstra and Flowd-Warshall's algorithms are limited to small networks due to computational complexity and cost. We propose an efficient and a more a...
详细信息
Proposed algorithms for calculating the shortest paths such as Dijikstra and Flowd-Warshall's algorithms are limited to small networks due to computational complexity and cost. We propose an efficient and a more accurate approximation algorithm that is applicable to large scale networks. Our algorithm iteratively constructs levels of hierarchical networks by a node condensing procedure to construct hierarchical graphs until threshold. The shortest paths between nodes in the original network are approximated by considering their corresponding shortest paths in the highest hierarchy. Experiments on real life data show that our algorithm records high efficiency and accuracy compared with other algorithms.
This paper considers the correlation clustering problem with non-uniform hard constrained cluster sizes, which is a generalization of correlation clustering problem. In this problem, we are given a positive integer U-...
详细信息
ISBN:
(数字)9783030271954
ISBN:
(纸本)9783030271954;9783030271947
This paper considers the correlation clustering problem with non-uniform hard constrained cluster sizes, which is a generalization of correlation clustering problem. In this problem, we are given a positive integer U-upsilon for each vertex upsilon, and require vertical bar C vertical bar = min(upsilon is an element of C) U-upsilon for any cluster C. We provide a (2, 4)-bicriteria approximation algorithm for this problem. Namely, the solution returned by the algorithm has the cost that is at most 4 times the optimum, and for each cluster C in the solution, we have vertical bar C vertical bar <= 2min(upsilon is an element of C) U-upsilon.
We consider the squared metric soft capacitated facility location problem (SMSCFLP), which includes both the squared metric facility location problem (SMFLP) and the soft capacitated facility location problem (SCFLP) ...
详细信息
ISBN:
(数字)9783030349806
ISBN:
(纸本)9783030349806;9783030349790
We consider the squared metric soft capacitated facility location problem (SMSCFLP), which includes both the squared metric facility location problem (SMFLP) and the soft capacitated facility location problem (SCFLP) as special cases. As our main contribution, we propose a primal-dual based 10-approximation algorithm for the SMSCFLP. Our work also extends the applicability of the primal-dual technique.
In this article, we investigate the dynamic (multi-period) facility location problem with potentially unserved clients or outliers. We propose a 3-approximation primal-dual algorithm based on an integer linear program...
详细信息
In this article, we investigate the dynamic (multi-period) facility location problem with potentially unserved clients or outliers. We propose a 3-approximation primal-dual algorithm based on an integer linear program formulation of the problem. We further improve the approximation ratio to 2 by combining the cost scaling and greedy improvement techniques.
Given a graph G=(V,E), we seek for a collection of vertex disjoint paths each of order at most 3 that together cover all the vertices of V. The problem is called 3-path partition, and it has close relationships to the...
详细信息
Given a graph G=(V,E), we seek for a collection of vertex disjoint paths each of order at most 3 that together cover all the vertices of V. The problem is called 3-path partition, and it has close relationships to the well-known path cover problem and the set cover problem. The general k-path partition problem for a constant k3 is NP-hard, and it admits a trivial k-approximation. When k=3, the previous best approximation ratio is 1.5 due to Monnot and Toulouse (Oper Res Lett 35:677-684, 2007), based on two maximum matchings. In this paper we first show how to compute in polynomial time a 3-path partition with the least 1-paths, and then apply a greedy approach to merge three 2-paths into two 3-paths whenever possible. Through an amortized analysis, we prove that the proposed algorithm is a 13/9-approximation. We also show that the performance ratio 13/9 is tight for our algorithm.
This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algo...
详细信息
This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algorithm employs two 2-approximation algorithms for k-minimum spanning tree problems and prize collecting Steiner tree problems. Also our algorithm framework can be applied to a special case of k-prize collecting traveling salesman problems.
We give an algorithm that for an input planar graph G of n vertices and an integer k, in min{O(n log(3) n), O(nk(2))} time either constructs a branch-decomposition of G of width at most (2 + delta)k, where delta > ...
详细信息
We give an algorithm that for an input planar graph G of n vertices and an integer k, in min{O(n log(3) n), O(nk(2))} time either constructs a branch-decomposition of G of width at most (2 + delta)k, where delta > 0 is a constant, or a (k+1) x inverted right perpendicular K+1/2 inverted right perpendicular cylinder minor of G implying bw(G) > k, where bw(G) is the branchwidth of G. This is the first (O) over tilde (n) time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous min{O(n(1 + epsilon) ), O(nk(2))} (where epsilon > 0 is a constant) time constant-factor approximations. For a planar graph G and k = bw(G), a branch-decomposition of width at most (2 + delta)k and a g x g/2 cylinder/grid minor with g = k/beta where beta > 2 is a constant, can be computed by our algorithm in min{O(n log(3) nlog k), O(nk(2) log k)} time. (C) 2018 Elsevier B.V. All rights reserved.
暂无评论