In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R^(2)using stock pieces of materials with fixed length,which is modelled as *** a set X={r_(1),r_(2)…,r_(n)}of n terminals in...
详细信息
In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R^(2)using stock pieces of materials with fixed length,which is modelled as *** a set X={r_(1),r_(2)…,r_(n)}of n terminals in R^(2)and some stock pieces of materials with fixed length L,we are asked to construct a Steiner tree T interconnecting all terminals in X,and each edge in T must be constructed by a part of that stock piece of *** objective is to minimize the cost of constructing such a Steiner tree T,where the cost includes three components,(1)The cost of Steiner points needed in T;(2)The construction cost of constructing all edges in T and(3)The cost of stock pieces of such materials used to construct all edges in *** can obtain two main results.(1)Using techniques of constructing a Euclidean minimum spanning tree on the set X and a strategy of solving the bin-packing problem,we present a simple 4-approximation algorithm in time O(n log n)to solve this new problem;(2)Using techniques of computational geometry to solve two nonlinear mathematical programming to obtain a key Lemma 8 and using other strategy of solving the bin-packing problem,we design a 3-approximation algorithm in time O(n^(3))to resolve this new problem.
Motivated by the soaking process under separate heating mode in iron and steel enterprises, we study the parallel batch machine scheduling problem with incompatible deteriorating jobs. The objective is to minimize mak...
详细信息
Motivated by the soaking process under separate heating mode in iron and steel enterprises, we study the parallel batch machine scheduling problem with incompatible deteriorating jobs. The objective is to minimize makespan. A soaking furnace can be seen as a parallel batch processing machine. In order to avoid the thermal stress caused by excessive temperature difference, initial temperature is needed for the ingot before processing. With the increasing of waiting time, the ingot temperature decreases and the soaking time increases. This property is called deterioration. Setup time is needed between incompatible jobs. We show that if jobs have the same sizes, an optimal solution can be found within O(nlogn) time. If jobs have identical processing times, the problem is proved to be NP-hard in the strong sense. We propose an approximate algorithm whose absolute and asymptotic worst-case ratios are less than 2 and 11/9, respectively. When the jobs have arbitrary sizes and arbitrary processing times, the model is also NP-hard in the strong sense. An approximate algorithm with an absolute and asymptotic worst-case ratio less than 2 is proposed. The time complexity is O(nlogn).
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.
In this paper, we consider the heterogeneous Chinese postman problem (the HCPP), which generalizes the k-Chinese postman problem. Specifically, given a weighted graph G = (V, E;w;r) with length function w : E -> R+...
详细信息
In this paper, we consider the heterogeneous Chinese postman problem (the HCPP), which generalizes the k-Chinese postman problem. Specifically, given a weighted graph G = (V, E;w;r) with length function w : E -> R+ satisfying the triangle inequality, a fixed depot r is an element of V, and k vehicles having k nonuniform speeds lambda(1), lambda(2), ..., lambda(k), respectively, it is asked to find k tours in G for these k vehicles, each starting at the same depot r, and collectively traversing each edge in E at least once. The objective is to minimize the maximum completion time of vehicles, where the completion time of a vehicle is its total travel length divided by its speed. The main contribution of our paper is to show the following two results. (1) Given any small constant delta > 0, we design a 20.8765(1 + delta)-approximation algorithm to solve the HCPP, where the running time required is bounded by a polynomial in the input size and 1/delta. (2) We present a (1 + Delta - 1/k)-approximation algorithm to solve the HCPP in cubic time, where Delta is the ratio of the largest vehicle speed to the smallest one.
In this paper,we consider the k-correlation clustering *** an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nodes into at...
详细信息
In this paper,we consider the k-correlation clustering *** an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nodes into at most k-clusters to maximize agreements—the total weights of“+”edges within clusters and“−”edges between *** problem is *** design an approximation algorithm with the approximation ratio{a,(2-k)a+k-1/k},where a is the weighted proportion of“+”edges in all *** a varies from 0 to 1,the approximation ratio varies from k-1/k to 1 and the minimum value is 1/2.
We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of n items, each associated with a non-negative ...
详细信息
We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of n items, each associated with a non-negative weight, and T time periods with non-decreasing capacities W-1 <= ... <= W-T. When item i is inserted at time t, we gain a profit of p(it );however, this item remains in the knapsack for all subsequent periods. The goal is to decide if and when to insert each item, subject to the time-dependent capacity constraints, with the objective of maximizing our total profit. Interestingly, this setting subsumes as special cases a number of recently-studied incremental knapsack problems, all known to be strongly NP-hard. Our first contribution comes in the form of a polynomial-time (1/2 - epsilon)-approximation for the generalized incremental knapsack problem. This result is based on a reformulation as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys-Tardos algorithm for the generalized assignment problem. Combined with further enumeration-based self-reinforcing ideas and new structural properties of nearly-optimal solutions, we turn our algorithm into a quasi-polynomial time approximation scheme (QPTAS). Hence, under widely believed complexity assumptions, this finding rules out the possibility that generalized incremental knapsack is APX-hard.
We consider a class of stochastic online matching problems, where a set of sequentially arriving jobs are to be matched to a group of workers. The objective is to maximize the total expected reward, defined as the sum...
详细信息
We consider a class of stochastic online matching problems, where a set of sequentially arriving jobs are to be matched to a group of workers. The objective is to maximize the total expected reward, defined as the sum of the rewards of each matched worker-job pair. Each worker can be matched to multiple jobs subject to the constraint that previously matched jobs are completed. We provide constant approximation algorithms for different variations of this problem with equal-length jobs.
In this paper, we have a set of weighted linear equalities and inequalities of the form A(1)x equivalent to 0(mod p), A2x not equivalent to 0(mod p) where all entries of A(1) and A(2) are in {- 1, 0, 1}. The objective...
详细信息
ISBN:
(纸本)9789819614899;9789819614905
In this paper, we have a set of weighted linear equalities and inequalities of the form A(1)x equivalent to 0(mod p), A2x not equivalent to 0(mod p) where all entries of A(1) and A(2) are in {- 1, 0, 1}. The objective is to assign each x(i) to Z(p) = {0,..., p-1} to maximize the total weight of the satisfied equalities and inequalities. This problem is a generalization of k-Correlation Clustering problem. We design an approximation algorithm with the approximation ratio max{a, (2-p)a+p-1/p}, where a is the weighted proportion of equalities in all equalities and inequalities. As a varies from 0 to 1, the approximation ratio varies from p-1/p to 1 and the minimum value is 1/2 when a is 1/2.
In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation...
详细信息
In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be NP-hard, while also proving NP-hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task setting.
In this paper, we address the k-Chinese postman problem under interdiction budget constraints (the k-CPIBC problem, for short), which is a further generalization of the k-Chinese postman problem and has many practical...
详细信息
In this paper, we address the k-Chinese postman problem under interdiction budget constraints (the k-CPIBC problem, for short), which is a further generalization of the k-Chinese postman problem and has many practical applications in real life. Specifically, given a weighted graph G = (V, E;w, c;v(1)) equipped with a weight function w : E -> R+ that satisfies the triangle inequality, an interdiction cost function c : E -> Z(+), a fixed depot v(1) is an element of V, an integer k is an element of Z(+) and a budget B is an element of N, we are asked to find a subset S-k subset of E such that c(S-k) = Sigma(e is an element of Sk) c(e) <= B and that the subgraph G\S-k is connected, the objective is to minimize the value minC(E\Sk) max{w(C-i) vertical bar C-i is an element of C-E\Sk} among such all aforementioned subsets S-k, where C-E\S-k is a set of k-tours (of G\S-k) starting and ending at the depot v1, jointly traversing each edge in G\S-k at least once, and w(C-i) = Sigma(e is an element of Ci) w(e) for each tour C-i is an element of C-E\Sk. We obtain the following main results: (1) Given an alpha-approximation algorithm to solve theminimization knapsack problem, we design an (alpha + beta)-approximation algorithm to solve the k-CPIBC problem, where beta = 7/2 - 1/k - left perpendicular1/kRIGHT perpendicular. (2) We present a beta-approximation algorithm to solve the special version of the k-CPIBC problem, where c(e) = 1 for each edge e in G and beta is defined in (1).
暂无评论