In this work, we are interested in the problem of task scheduling on large-scale data-intensive computing systems. In order to achieve good performance, one must construct not only good task schedules but also good da...
详细信息
In this work, we are interested in the problem of task scheduling on large-scale data-intensive computing systems. In order to achieve good performance, one must construct not only good task schedules but also good data allocation across nodes on the system, since before a task can be executed, it must have access to data distributed on the system. In this article, we present a general formulation of a static problem that combines both scheduling and replication problems in data-intensive distributed systems. We show that this problem does not admit an approximation algorithm. However, considering a restricted version of the problem that considers some practical constraints, an approximation algorithm can be designed. From a practical perspective, we introduce a novel heuristic for the problem that is based on nodes clustering. We compare the heuristic with two adapted approaches from other works in the literature by computational simulations using an extensive set of instances based on real computer grids. We show that our heuristic often obtains the best solutions and also runs faster than other approaches.
In this paper we present a 1.52-approximation algorithm for the metric uncapacitated facility location problem, and a 2-approximation algorithm for the metric capacitated facility location problem with soft capacities...
详细信息
In this paper we present a 1.52-approximation algorithm for the metric uncapacitated facility location problem, and a 2-approximation algorithm for the metric capacitated facility location problem with soft capacities. Both these algorithms improve the best previously known approximation factor for the corresponding problem, and our soft-capacitated facility location algorithm achieves the integrality gap of the standard linear programming relaxation of the problem. Furthermore, we will show, using a result of Thorup, that our algorithms can be implemented in quasi-linear time.
Motivated by the Steiner tree problem with minimum number of Steiner points and bounded edge-length in [4], we consider the problem of constructing specific subgraph with minimum number of length-bounded stock pieces ...
详细信息
Motivated by the Steiner tree problem with minimum number of Steiner points and bounded edge-length in [4], we consider the problem of constructing specific subgraph with minimum number of length-bounded stock pieces (CSS-MSP, for short), which is defined as follows. In some constructing specific subgraph problem Q (CSS, for short), the objective is to choose a minimum-length subset of edges, such that these edges form a specific subgraph (such as a spanning tree or a Steiner tree). In the CSS-MSP problem Q', these edges are further required to be cut from some stock pieces of length L, and the new objective, however, is to minimize the number of stock pieces of length L to construct all edges in such a specific subgraph. We obtain two main results. (1) Whenever the CSS problem Q can be approximated by an alpha-approximation algorithm (alpha >= 1) (for the case alpha = 1, the CSS problem Q is solved optimally by a polynomial-time exact algorithm), we design two approximation algorithms with performance ratios 2 alpha and 7 alpha/4 to solve the CSS-MSP problem Q';(2) In addition, when the problem Q is to find a minimum spanning tree, we present a 3/2-approximation algorithm and an APTAS to solve the problem Q' of constructing spanning tree with minimum number of length-bounded stock pieces. (C) 2018 Elsevier B.V. All rights reserved.
In the minimum-cost k-(S, T) connected digraph (abbreviated as k-(S, T) connectivity) problem we are given a positive integer k, a directed graph G = (V, E) with nonnegative costs on the edges, and two subsets S, T of...
详细信息
In the minimum-cost k-(S, T) connected digraph (abbreviated as k-(S, T) connectivity) problem we are given a positive integer k, a directed graph G = (V, E) with nonnegative costs on the edges, and two subsets S, T of V;the goal is to find a subset of edges (E) over cap of minimum cost such that the subgraph (V, (E) over cap) has k edge-disjoint directed paths from each vertex in S to each vertex in T. Most of our results focus on a specialized version of the problem that we call the standard version, where every edge of positive cost has its tail in S and its head in T. This version of the problem captures NP-hard problems such as the minimum-cost k-vertex connected spanning subgraph problem. We give an approximation algorithm with a guarantee of O((log k)(log n)) for the standard version of the k-(S, T) connectivity problem, where n denotes the number of vertices. For k = 1, we give a simple 2-approximation algorithm that generalizes a well-known 2-approximation algorithm for the minimum-cost strongly connected spanning subgraph problem. For k = 2, we give a 3-approximation algorithm;this matches the best approximation guarantee known for the special case of the minimum-cost 2-vertex connected spanning subgraph problem. Besides the standard version, we study another version that is intermediate between the standard version and the problem in its full generality. In the relaxed version of the (S, T) connectivity problem, each edge of positive cost has its head in T but there is no restriction on the tail. We study the relaxed version with the connectivity parameter k fixed at one and observe that this version is at least as hard to approximate as the directed Steiner tree problem. We match this by giving an algorithm that achieves an approximation guarantee of alpha(n)+1 for the relaxed (S, T) connectivity problem, where alpha(n) denotes the best approximation guarantee available for the directed Steiner tree problem. The key to the analysis is a structural result
In this paper, we prove that the Max Morse Matching Problem is approximable, thus resolving an open problem posed by Joswig and Pfetsch [1]. For D-dimensional simplicial complexes, we obtain a (D+1)/(D-2+D+1)-factor a...
详细信息
In this paper, we prove that the Max Morse Matching Problem is approximable, thus resolving an open problem posed by Joswig and Pfetsch [1]. For D-dimensional simplicial complexes, we obtain a (D+1)/(D-2+D+1)-factor approximation ratio using a simple edge reorientation algorithm that removes cycles. For D >= 5, we describe a 2/D-factor approximation algorithm for simplicial manifolds by processing the simplices in increasing order of dimension. This algorithm leads to 1/2-factor approximation for 3-manifolds and 4/9-factor approximation for 4-manifolds. This algorithm may also be applied to non-manifolds resulting in a 1/(D+1)-factor approximation ratio. One application of these algorithms is towards efficient homology computation of simplicial complexes. Experiments using a prototype implementation on several datasets indicate that the algorithm computes near optimal results. (C) 2016 Elsevier B.V. All rights reserved.
We study the approximability of minimum total weighted tardiness with a modified objective which includes an additive constant. This ensures the existence of a positive lower bound for the minimum value. Moreover the ...
详细信息
We study the approximability of minimum total weighted tardiness with a modified objective which includes an additive constant. This ensures the existence of a positive lower bound for the minimum value. Moreover the new objective has a natural interpretation in just-in-time production systems. (C) 2007 Elsevier B.V. All rights reserved.
Sorting by Genome Rearrangements is a classic problem in Computational Biology. Several models have been considered so far, each of them defines how a genome is modeled (for example, permutations when assuming no dupl...
详细信息
Sorting by Genome Rearrangements is a classic problem in Computational Biology. Several models have been considered so far, each of them defines how a genome is modeled (for example, permutations when assuming no duplicated genes, strings if duplicated genes are allowed, and/or use of signs on each element when gene orientation is known), and which rearrangements are allowed. Recently, a new problem, called Sorting by Multi-Cut Rearrangements, was proposed. It uses the k-cut rearrangement which cuts a permutation (or a string) at k >= 2 places and rearranges the generated blocks to obtain a new permutation (or string) of same size. This new rearrangement may model chromoanagenesis, a phenomenon consisting of massive simultaneous rearrangements. Similarly as the Double-Cut-and-Join, this new rearrangement also generalizes several genome rearrangements such as reversals, transpositions, revrevs, transreversals, and block-interchanges. In this paper, we extend a previous work based on unsigned permutations and strings to signed permutations. We show the complexity of this problem for different values of k, and that the approximation algorithm proposed for unsigned permutations with any value of k can be adapted to signed permutations. We also show a 1.5-approximation algorithm for the specific case k = 4, as well as a generic approximation algorithm applicable for any k >= 5, that always reaches constant ratio. The latter makes use of the cycle graph, a well-known structure in genome rearrangements. We implemented and tested the proposed algorithms on simulated data.
The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in g...
详细信息
The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time. For any epsilon > 0, we provide a (2 + epsilon)-approximation algorithm for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant. No prior upper approximation bounds were known for this time-dependent problem. (C) 2001 Elsevier Science B.V. All rights reserved.
In this paper, we address the trip-constrained vehicle routing cover problem (theTcVRC problem). Specifically, given a metric complete graphG=(V,E;w)with a set D(subset of V)of depots, a setJ(=V\D)of customer location...
详细信息
In this paper, we address the trip-constrained vehicle routing cover problem (theTcVRC problem). Specifically, given a metric complete graphG=(V,E;w)with a set D(subset of V)of depots, a setJ(=V\D)of customer locations, each customerhaving unsplittable demand 1, andkvehicles with capacityQ, it is asked to find a setC={C-i|=1,2,...,k}ofktours forkvehicles to service all customers, each tourfor a vehicle starts and ends at one depot inDand permits to be replenished at someother depots inDbefore continuously servicing at mostQcustomers, i.e., the numberof customers continuously serviced in per trip of each tour is at mostQ(except thetwo end-vertices of that trip), where each trip is a path or cycle, starting at a depot andending at other depot (maybe the same depot) inD, such that there are no other depotsin the interior of that path or cycle, the objective is to minimize the maximum weightof suchktours inC, i.e., minCmax{w(C-i)|i=1,2,...,k}, wherew(Ci)is thetotal weight of edges in that tourCi. Consideringkvehicles whether to have commondepot or suppliers, we consider three variations of the TcVRC problem, i.e., (1) the trip-constrained vehicle routing cover problem with multiple suppliers (the TcVRC-MSproblem) is asked to find a setC={Ci|i=1,2,...,k}ofktours mentioned-above,the objective is to minimize the maximum weight of suchktours inC;(2) the trip-constrained vehicle routing cover problem with common depot and multiple suppliers(the TcVRC-CDMS problem) is asked to find a setC={Ci|i=1,2,...,k}ofk tours mentioned-above, where each tour starts and ends at same depotvinD, eachvehicle having its suppliers at some depots inD(possibly includingv), the objectiveis to minimize the maximum weight of suchktours inC;(3) the trip-constrainedk-traveling salesman problem with non-suppliers (the TckTS-NS problem, simply theTckTSP-NS) is asked to find a setC={C-i=1,2,...,k}of k tours mentioned-above, where each tour starts and ends at same depotvinD, each vehicle havingnon-suppli
We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple ...
详细信息
We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP-hard for any fixed number (>= 2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two-phase heuristics and dynamic two-phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. (C) 2006 Wiley Peribdicals, Inc.
暂无评论