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).
The bounded k-median problem is to select in an undirected graph G = (V,E) a set S of k vertices such that the distance from any vertex v is an element of V to S is at most a given bound d and the average distance fro...
详细信息
The bounded k-median problem is to select in an undirected graph G = (V,E) a set S of k vertices such that the distance from any vertex v is an element of V to S is at most a given bound d and the average distance from vertices V\S to S is minimized. We present randomized algorithms for several versions of this problem and we prove some inapproximability results. We also study the bounded version of the uncapacitated facility location problem and present extensions of known deterministic algorithms for the unbounded version.
We introduce a novel coverage problem that arises in aerial surveying applications. The goal is to compute a shortest path that visits a given set of cones. The apex of each cone is restricted to lie on the ground pla...
详细信息
We introduce a novel coverage problem that arises in aerial surveying applications. The goal is to compute a shortest path that visits a given set of cones. The apex of each cone is restricted to lie on the ground plane. The common angle alpha of the cones represent the field of view of the onboard camera. The cone heights, which can be varying, correspond with the desired observation quality (e.g. resolution). This problem is a novel variant of the traveling salesman problem with neighborhoods (TSPN). We name it Cone-TSPN. Our main contribution is a polynomial time approximation algorithm for Cone-TPSN. We analyze its theoretical performance and show that it returns a solution whose length is at most O(1+log(hmax/hmin)) times the length of the optimal solution where hmax and hmin are the heights of the tallest and shortest input cones, *** demonstrate the use of our algorithm in a representative precision agriculture application. Wefurther study its performance in simulation using randomly generated cone sets. Our results indicate that the performance of our algorithm is superior to standard solutions.
We consider a problem of locating communication centers. In this problem, it is required to partition the set of n customers into subsets minimizing the length of nets required to connect all the customers to the comm...
详细信息
We consider a problem of locating communication centers. In this problem, it is required to partition the set of n customers into subsets minimizing the length of nets required to connect all the customers to the communication centers. Suppose that communication centers are to be placed in p of the customers locations. The number of customers each center supports is also given. The problem remains to divide a graph into sets of the given sizes, keeping the sum of the spanning trees minimal. The problem is NP-complete, and no polynomial algorithm with bounded error ratio can be given, unless P=NP. We present an approximation algorithm for the problem assuming that the edge lengths satisfy the triangle inequality. It runs in O(p(2)4(p) + n(2)) time (n = \V\) and comes within a factor of 2p - 1 of optimal. When the sets' sizes are all equal this algorithm runs in O(n2) time. Next, an improved algorithm is presented which obtains as an input a positive integer x (x less than or equal to n - p) and runs in O(f(p,x)n(2)) time, where f is an exponential function of p and x, and comes within a factor of 2 + (2p - 3)/x of optimal. When the sets' sizes are all equal it runs in O(2((p+x))n(2)) time. A special algorithm is presented for the case p = 2. (C) 1998 Elsevier Science B.V. All rights reserved.
The emerging wireless relay networks (WRNs) are expected to provide significant improvement on throughput and extension of coverage area for next-generation wireless systems. We study an optimization problem for multi...
详细信息
The emerging wireless relay networks (WRNs) are expected to provide significant improvement on throughput and extension of coverage area for next-generation wireless systems. We study an optimization problem for multihop link scheduling with bandwidth and delay guarantees over WRNs. Our optimization problem is investigated under a more general interference model with a generic objective. The objective can be based on various kinds of performance indexes (e.g., throughput, fairness, and capacity), which can be determined by service providers. Through our theoretical analysis, the intractability and inapproximability of the optimization problem are shown. Due to the intractable computational complexity, we present efficient algorithms to provide a reasonable small approximation factor against any optimal solution even for a worst-case input. Furthermore, some experimental results indicate that our algorithms yield near-optimal performance in the average case.
The DEGREE-Delta CLOSEST PHYLOGENETIC kTH ROOT PROBLEM (Delta CPRk) is the problem of finding a (phylogenetic) tree T from a given graph G = ( V, E) such that ( 1) the degree of each internal node in T is at least 3 a...
详细信息
The DEGREE-Delta CLOSEST PHYLOGENETIC kTH ROOT PROBLEM (Delta CPRk) is the problem of finding a (phylogenetic) tree T from a given graph G = ( V, E) such that ( 1) the degree of each internal node in T is at least 3 and at most., ( 2) the external nodes (i.e. leaves) of T are exactly the elements of V, and ( 3) the number of disagreements, i.e., | E circle plus{{u, v} : u, v are leaves of T and d(T) ( u, v) <= k}|, is minimized, where d(T) ( u, v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Delta, k such that either both Delta >= 3 and k >= 3, or Delta > 3 and k = 2. This paper presents a polynomial-time 8-approximation algorithm for Delta CPR2 for any fixed Delta > 3, a quadratic-time 12-approximation algorithm for 3CPR(3), and a polynomial-time approximation scheme for the maximization version of Delta CPRk for any fixed. and k.
Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623-644, 1977;Jaitly et al. in J. Comput. Syst. Sci. 65:494-507, 2002;Tang et al. in...
详细信息
Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623-644, 1977;Jaitly et al. in J. Comput. Syst. Sci. 65:494-507, 2002;Tang et al. in J. Comput. Biol. 9:429-446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494-507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n (5)) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494-507, 2002) takes O(n (11)) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case.
We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimnm-load klacility location (MLkF...
详细信息
We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimnm-load klacility location (MLkFL) problem, Which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k >= 0. Assigning client j to a facility f incurs a connection cost d(f, j). The goal is to open a set F subset of F of k facilities and assign each client j to a-facility f (j) is an element of F so as to minimize max(f is an element of F) Sigma(j is an element of C:f(j)=f) d(f, j);we call Sigma(j is an element of C:f(j)=f) d(f, j) the load of facility f. This problem was studied under the name of min-max star cover in References [3, 7], who (among other results) gave bicriteria approximation algorithms for MLkFL for when F = C. MLkFL is rather poorly understood, a rid only an O(k)-approximation is currently known for MLkFL, even for line metrics. Our main result is the first polytime approximation scheme (PTAS) for MLkFL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that MLkFL is strongly NP-hard on line metrics. We also devise a quasi-PTAS for MLkFL on tree metrics. MLkFL turns out to be surprisingly challenging even on line metrics and resilient to attack by a variety of techniques that have been successfully applied to facility-location problems. For instance, we show that (a) even a configuration-style LP-relaxation has a bad integrality gap and (b) a multi-swap k-median style local search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack MLkFL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near optimal solution possessing sonic nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding of the problem and
We study the minimum connected sensor cover problem (MIN-CSC) and the budgeted connected sensor cover (Budgeted-CSC) problem, both motivated by important applications (e.g., reduce the communication cost among sensors...
详细信息
We study the minimum connected sensor cover problem (MIN-CSC) and the budgeted connected sensor cover (Budgeted-CSC) problem, both motivated by important applications (e.g., reduce the communication cost among sensors) in wireless sensor networks. In both problems, we are given a set of sensors and a set of target points in the Euclidean plane. In MIN-CSC, our goal is to find a set of sensors of minimum cardinality, such that all target points are covered, and all sensors can communicate with each other (i.e., the communication graph is connected). We obtain a constant factor approximation algorithm, assuming that the ratio between the sensor radius and communication radius is bounded. In Budgeted-CSC problem, our goal is to choose a set of B sensors, such that the number of targets covered by the chosen sensors is maximized and the communication graph is connected. We also obtain a constant approximation under the same assumption. (C) 2020 Published by Elsevier B.V.
In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), an...
详细信息
In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X (1),aEuro broken vertical bar,X (g) aS dagger V, with each group X (i) having a requirement r (i) between 0 and |X (i) |. The goal is to find a minimum cost set of edges whose removal separates each group X (i) into at least r (i) disconnected components. We give an O(log na <...log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log na <...log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Omega(log g) hardness of approximation for the requirement cut problem, even on trees.
暂无评论