In this paper, we consider the maximum traveling salesman problem with gamma-parameterized triangle inequality for gamma is an element of [1/2, 1), which means that the edge weights in the given complete graph G = (V,...
详细信息
In this paper, we consider the maximum traveling salesman problem with gamma-parameterized triangle inequality for gamma is an element of [1/2, 1), which means that the edge weights in the given complete graph G = (V, E, w) satisfy w(uv) <= gamma . (w(ux) + w(xv)) for all distinct nodes u, x, v is an element of V. For the maximum traveling salesman problem with gamma-parameterized triangle inequality, R. Hassin and S. Rubinstein gave a constant factor approximation algorithm with polynomial running time, they achieved a performance ratio gamma only for gamma is an element of [1/2, 5/7) in [8], which is the best known result. We design a k gamma+1-2 gamma/k gamma-approximation algorithm for the maximum traveling salesman problem with gamma-parameterized triangle inequality by using a similar idea but very different method to that in [11], where k = min{vertical bar C-i vertical bar vertical bar i = 1, 2, ..., m}, C-1, C-2, ..., C-m is an optimal solution of the minimum cycle cover in G, which is better than the gamma-approximation algorithm for almost all gamma is an element of [1/2, 1). (C) 2010 Elsevier B.V. All rights reserved.
Given a weighted undirected graph G = (V, E), where the vertex set V is partitioned into K clusters V1. . . . . V-K, the clustered traveling salesman problem is to compute a shortest tour so that all vertices are visi...
详细信息
Given a weighted undirected graph G = (V, E), where the vertex set V is partitioned into K clusters V1. . . . . V-K, the clustered traveling salesman problem is to compute a shortest tour so that all vertices are visited and the vertices of each cluster are visited consecutively. Supposing that no starting and ending vertices of any cluster are specified, we provide a 13/6 (approximate to 2.17)-approximation algorithm, and improve the previous approximation ratio of 2.75 due to Guttmann-Beck, Hassin, Khuller, and Raghavachari [algorithmica 28 (2000) 422-437]. (C) 2012 Elsevier B.V. All rights reserved.
In this letter, we study the optimum selection of ground stations (GSs) in RF/optical satellite networks (SatNets) in order to minimize the overall installation cost under an outage probability requirement, assuming i...
详细信息
In this letter, we study the optimum selection of ground stations (GSs) in RF/optical satellite networks (SatNets) in order to minimize the overall installation cost under an outage probability requirement, assuming independent weather conditions between sites. First, we show that the optimization problem can be formulated as a binary-linear-programming problem, and then we give a formal proof of its NP-hardness. Furthermore, we design a dynamic-programming algorithm of pseudo-polynomial complexity with global optimization guarantee as well as an efficient (polynomial-time) approximation algorithm with provable performance guarantee on the distance of the achieved objective value from the global optimum. Finally, the performance of the proposed algorithms is verified through numerical simulations.
We present a simple 3-approximation algorithm for the feedback vertex set problem in a bipartite tournament, improving on the approximation ratio of 3.5 achieved by the best previous algorithms. (c) 2008 Elsevier B.V....
详细信息
We present a simple 3-approximation algorithm for the feedback vertex set problem in a bipartite tournament, improving on the approximation ratio of 3.5 achieved by the best previous algorithms. (c) 2008 Elsevier B.V. All rights reserved.
This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose a new lower bound for the traveling tournament problem, and construct a randomiz...
详细信息
This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose a new lower bound for the traveling tournament problem, and construct a randomized approximation algorithm yielding a feasible solution whose approximation ratio is less than 2+(9/4)/(n-1), where n is the number of teams. Additionally, we propose a deterministic approximation algorithm with the same approximation ratio using a derandomization technique. For the traveling tournament problem, the proposed algorithms are the first approximation algorithms with a constant approximation ratio, which is less than 2+3/4.
The optimal path to be followed by an automatic cutter to cut a set of shapes arranged on a material is termed as the cutting path determination problem. The shapes are often considered as polygons. Each polygon can b...
详细信息
The optimal path to be followed by an automatic cutter to cut a set of shapes arranged on a material is termed as the cutting path determination problem. The shapes are often considered as polygons. Each polygon can be either cut entirely (complete cutting approach) or partially (partial cutting approach) before cutting the next polygon. This work solves the cutting path determination problem using the partial cutting approach. The proposed approximation algorithm uses the concepts of ma tching, s panning tree, and tri angulation, and is hence termed as MASTRI. The MASTRI algorithm has a time complexity of O(n logn) where n is the total number of vertices of all the polygons. The cutting path computed by the MASTRI algorithm is guaranteed to be within a factor of 3/2 of optimum travel distance of the cutter. No other algorithm has been developed for the partial cutting approach which runs in polynomial time. The MASTRI algorithm is evaluated on 285 input problems, of which 192 problems are randomly generated, and 93 problems are taken from literature. The experimental analysis shows that the MASTRI algorithm computes the cutting path in a very short amount of time. The comparison of MASTRI algorithm with existing works in the literature shows that the MASTRI algorithm gives a shorter cutting path in less time. The MASTRI algorithm can be used for computing cutting path in industries like sheet metal cutting.
We consider the vertex cover P-n (VCPn) problem, that is, the problem of finding a minimum weight set F subset of V such that the graph G[V - F] has no P-n, where P-n is a path with n vertices. The problem also has it...
详细信息
We consider the vertex cover P-n (VCPn) problem, that is, the problem of finding a minimum weight set F subset of V such that the graph G[V - F] has no P-n, where P-n is a path with n vertices. The problem also has its application background. In this paper, we restrict our attention to the VCP3 problem and give a 2-approximation algorithm using the technique of layering. (C) 2011 Elsevier B.V. All rights reserved.
For two sequences P and Q of n points in R-d, we compute an approximation to the discrete Frechet distance. Our f-approximation algorithm runs in time O(n logn + n(2)/f(2)), for any f is an element of[1, root n/log n]...
详细信息
For two sequences P and Q of n points in R-d, we compute an approximation to the discrete Frechet distance. Our f-approximation algorithm runs in time O(n logn + n(2)/f(2)), for any f is an element of[1, root n/log n] and d = O(1), which improves (and, at the same time, slightly simplifies) the previous O(n logn + n(2)/f)-time algorithm by Bringmann and Mulzer [SoCG'15]. (C) 2018 Elsevier B.V. All rights reserved.
In this paper a new approximation algorithm with worst case performance ratio 3/2 is presented for the problem of scheduling unit execution time jobs on two parallel machines with the objective of minimizing the makes...
详细信息
In this paper a new approximation algorithm with worst case performance ratio 3/2 is presented for the problem of scheduling unit execution time jobs on two parallel machines with the objective of minimizing the makespan where each job can be processed on only one machine and there are chain-type precedence constraints in the jobs. This result answers an open problem in Jansen et al. [Jansen, K., Woeginger, G. J. and Yu, Z., UET-Scheduling with chain-type precedence constraints. Report 277, Technische Universitat Graz, Institut fur Mathematik, Graz, Austria, 1993.]: "Does there exist a polynomial time heuristic with worst-case guarantee better than 5/3 for the problem U2Chain?". The new approximation algorithm is also applied to the problem J2\pmtn\C-max. (C) 1998 Elsevier Science Ltd. All rights reserved.
A partitionable multiprocessor system can form multiple partitions, each consisting of a controller and a varying number of processors. Given such a system and a set of tasks, each of which can be executed on partitio...
详细信息
A partitionable multiprocessor system can form multiple partitions, each consisting of a controller and a varying number of processors. Given such a system and a set of tasks, each of which can be executed on partitions of varying sizes, we study the problem of choosing the partition sizes and a minimum completion time schedule for the execution of these tasks. We assume that the number of tasks to be scheduled on the system is no more than the maximum number of partitions that can be formed simultaneously by the system, and that parallelization of the tasks can achieve at most perfect speedup. We show this scheduling problem to be NP-hard, and present a polynomial time approximation algorithm for this problem. We derive a parameter dependent, asymptotically tight worst-case performance bound for this approximation algorithm. We also evaluate its average performance through simulation.
暂无评论