We present approximation algorithms and heuristics for several variations of terrain guarding problems, where we need to guard a terrain in its entirety by a minimum number of guards. Terrain guarding has applications...
详细信息
We present approximation algorithms and heuristics for several variations of terrain guarding problems, where we need to guard a terrain in its entirety by a minimum number of guards. Terrain guarding has applications in telecommunications, namely in the setting up of antenna networks for wireless communication. Our approximation algorithms transform the terrain guarding instance into a MINIMUM SET COVER instance, which is then solved by the standard greedy approximation algorithm [J. Comput. System Sci. 9 (1974) 256-278]. The approximation algorithms achieve approximation ratios of 0(logn), where n is the number of vertices in the input terrain. We also briefly discuss some heuristic approaches for solving other variations of terrain guarding problems, for which no approximation algorithms are known. These heuristic approaches do not guarantee non-trivial approximation ratios but may still yield good solutions. (C) 2002 Published by Elsevier Science B.V.
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 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 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
Designing and analyzing algorithms with provable performance guarantees enables efficient optimization problem solving in different application domains, e.g. communication networks, transportation, economics, and manu...
详细信息
Designing and analyzing algorithms with provable performance guarantees enables efficient optimization problem solving in different application domains, e.g. communication networks, transportation, economics, and manufacturing. Despite the significant contributions of approximation algorithms in engineering, only limited and isolated works contribute from this perspective in process systems engineering. The current paper discusses three representative, NP-hard problems in process systems engineering: (i) pooling, (ii) process scheduling, and (iii) heat exchanger network synthesis. We survey relevant results and raise major open questions. Further, we present approximation algorithms applications which are relevant to process systems engineering: (i) better mathematical modeling, (ii) problem classification, (iii) designing solution methods, and (iv) dealing with uncertainty. This paper aims to motivate further research at the intersection of approximation algorithms and process systems engineering. (C) 2019 Elsevier Ltd. All rights reserved.
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.
暂无评论