Search

This paper is concerned with designing algorithms for and analyzing the computational complexity of the partial vertex cover problem in trees. Graphs (and trees) are frequently used to model risk management in various systems. In particular, Caskurlu et al. in [4] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Cover problem on bipartite graphs. In this paper, we focus on a special case of the partial vertex cover problem, when the input graph is a tree. We consider four possible versions of this setting, depending on whether or not, the vertices and edges are weighted. Two of these versions, where edges are assumed to be unweighted, are known to be polynomial-time solvable. However, the computational complexity of this problem with weighted edges, and possibly with weighted vertices, remained open. The main contribution of this paper is to resolve these questions by fully characterizing which variants of partial vertex cover remain NP-hard in trees, and which can be solved in polynomial time. In the paper, we propose two pseudo-polynomial DP-based algorithms for the most general case in which weights are present on both the edges and the vertices of the tree. One of these algorithms leads to a polynomial-time procedure, when weights are confined to the edges of the tree. The insights used in this algorithm are combined with additional scaling ideas to derive an FPTAS for the general case. A secondary contribution of this work is to propose a novel way of using centroid decompositions in trees, which could be useful in other settings as well. [ABSTRACT FROM AUTHOR]

In this paper, we study a discrete momentum consensus-based optimization (Momentum-CBO) algorithm which corresponds to a second-order generalization of the discrete first-order CBO [S.-Y. Ha, S. Jin and D. Kim, Convergence of a first-order consensus-based global optimization algorithm, Math. Models Methods Appl. Sci. 30 (2020) 2417–2444]. The proposed algorithm can be understood as the modification of ADAM-CBO, replacing the normalization term by unity. For the proposed Momentum-CBO, we provide a sufficient framework which guarantees the convergence of algorithm toward a global minimum of the objective function. Moreover, we present several experimental results showing that Momentum-CBO has an improved success rate of finding the global minimum compared to vanilla-CBO and show the stability of Momentum-CBO under different initialization schemes. We also show that Momentum-CBO can be used as the alternative of ADAM-CBO which does not have a proper convergence analysis. Finally, we give an application of Momentum-CBO for Lyapunov function approximation using symbolic regression techniques. [ABSTRACT FROM AUTHOR]

A dominator coloring of a graph G is a proper vertex coloring with a domination property that each vertex dominates a color class. The minimum number of colors used in a dominator coloring of G is called dominator chromatic number of G and is denoted as χ d (G). Graphs with χ d (G) ≤ 3 have characterizations and such graphs can be recognized in polynomial time. However, for k ≥ 4 , deciding whether χ d (G) ≤ k is NP-hard. In this paper, we investigate the computational complexity of minimum q -dominator partization problem (Min- q -D-Partz). In Min- q -D-Partz, given a graph G , the objective is to find a vertex set S of minimum size such that χ d (G [ V ∖ S ]) ≤ q. We prove that Min- 2 -D-Partz is APX-complete and has a two-factor approximation algorithm. We also prove that Min- 3 -D-Partz cannot be approximated within any constant factor and can be approximated within a factor of O (log n). [ABSTRACT FROM AUTHOR]

For an m -edge connected simple graph G , finding a spanning tree of G with the maximum number of leaves is MAXSNP-complete. The problem remains NP-complete even if G is planar and the maximal degree of G is at most four. Lu and Ravi gave the first known polynomial-time approximation algorithms with approximation factors 5 and 3. Later, they obtained a 3 -approximation algorithm that runs in near-linear time. The best known result is Solis-Oba, Bonsma, and Lowski's O (m) -time 2 -approximation algorithm. We show an alternative simple O (m) -time 2 -approximation algorithm whose analysis is simpler. This paper is dedicated to the cherished memory of our dear friend, Professor Takao Nishizeki. [ABSTRACT FROM AUTHOR]

The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The first two problems minimize linear and submodular functions, respectively, subject to the same non-submodular cover constraint. The third problem minimizes a submodular function subject to non-submodular cover and precedence constraints. Based on the concepts of submodular ratio and gap, and Lovász extension, we devise greedy and primal–dual approximation algorithms for these problems. [ABSTRACT FROM AUTHOR]

This paper investigates the three-stage assembly flow shop scheduling problem, provided that there is a fixed maintenance period (MP) imposed on one of the machines in the first stage, the objective is to minimize the makespan. The starting time and duration of MP are known in advance, during MP no job can be processed on the corresponding machine. Only the non-resumable scenario is considered, i.e., if a job fails to finish before MP, it must restart from the beginning after the machine becomes available again, rather than continuing its processing. The problem generalizes the three-stage assembly flow shop scheduling problem without MPs and is therefore strongly NP-hard. To the best of our knowledge, the problem has not been explored so far. We propose three approximation algorithms for the problem. [ABSTRACT FROM AUTHOR]

We study the Maximum Bipartite Subgraph (M B S) problem, which is defined as follows. Given a set S of n geometric objects in the plane, we want to compute a maximum-size subset S ′ ⊆ S such that the intersection graph of the objects in S ′ is bipartite. We first give an O (n 2) -time algorithm that computes an almost optimal solution for the problem on circular-arc graphs. We show that the M B S problem is N P -hard on geometric graphs for which the maximum independent set is N P -hard (hence, it is N P -hard even on unit squares and unit disks). On the other hand, we give a P T A S for the problem on unit squares and unit disks. Moreover, we show fast approximation algorithms with small-constant factors for the problem on unit squares, unit disks, and unit-height axis parallel rectangles. Additionally, we prove that the Maximum Triangle-free Subgraph (M T F S) problem is NP-hard for axis-parallel rectangles. Here the objective is the same as that of the M B S except the intersection graph induced by the set S ′ needs to be triangle-free only (instead of being bipartite). [ABSTRACT FROM AUTHOR]

The Network Construction problem, studied by Angluin et al., Hosoda et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set V of vertices, construction costs for all possible edges between pairs of vertices from V , and a sequence S 1 , S 2 , ... , S r ⊆ V of connectivity constraints, the objective is to find a set E of edges such that each S i induces a connected subgraph of the graph (V , E) and the total cost of E is minimized. First, we study the online version where every constraint must be satisfied immediately after its arrival and edges that have already been added can never be removed. We give an O (B 2 log n) -competitive and O ((B + log r) log n) -competitive polynomial-time algorithms, where B is an upper bound on the size of constraints, while r , n denote the number of constraints and the number of vertices, respectively. On the other hand, we observe that an Ω (B) -competitive lower bound as well as an Ω (B) -competitive lower bound in the cost-uniform case are implied by the known lower bounds for unbounded constraints. For the cost-uniform case with unbounded constraints, we provide an O (n (log n + log r)) -competitive upper bound with high probability. The latter bound is against an oblivious adversary while our other randomized competitive bounds are against an adaptive adversary. Next, we discuss a hybrid approximation method for the (offline) Network Construction problem combining an approximation algorithm of Hosoda et al. with one of Angluin et al. and an application of the hybrid method to bioinformatics. Finally, we consider a natural strengthening of the connectivity requirements in the Network Construction problem, where each constraint has to induce a subgraph (of the constructed graph) of diameter at most d. Among other things, we provide a polynomial-time ( B 2 − B + 2) B 2 -approximation algorithm for the Network Construction problem with the d -diameter requirements, when each constraint has at most B vertices, and show the APX-completeness of this variant. [ABSTRACT FROM AUTHOR]

Given an undirected complete graph G = (V , E) on k n vertices with a non-negative weight function on E , the maximum-weight k -cycle (k -path) packing problem aims to compute a set of n vertex-disjoint cycles (paths) in G containing k vertices so that the total weight of the edges in these n cycles (paths) is maximized. For the maximum-weight k -cycle packing problem, we develop an algorithm achieving an approximation ratio of α ⋅ (k − 1 k) 2 , where α is the approximation ratio for the maximum traveling salesman problem. For the case k = 4 , we design a better 2 3 -approximation algorithm. When the weights of edges obey the triangle inequality, we propose a 3 4 -approximation algorithm and a 3 5 -approximation algorithm for the maximum-weight k -cycle packing problem with k = 4 and k = 5 , respectively. For the maximum-weight k -path packing problem with k = 3 (or k = 5) with the triangle inequality, we devise an algorithm with approximation ratio 3 4 and give a tight example. [ABSTRACT FROM AUTHOR]

Correlation clustering problem (CorCP) is a classical clustering problem, which clusters data based on the similarity of data set, and has many applications in interaction networks, cross-lingual link detection, and communication networks, etc. In this paper, we study a practical generalization of the CorCP, called the capacitated correlation clustering problem (the capacitated CorCP), by constructing a labeled complete graph. On this labeled complete graph, each vertex represents a piece of data. If two pieces of data are similar, then the edge between the corresponding vertices is marked by a positive label +. Otherwise, this edge is marked by a negative label −. The objective of the capacitated CorCP is to group some similar data sets into one cluster as far as possible, while satisfying the cluster capacity constraint. To achieve this objective, we shall partition the vertex set of the labeled complete graph into several clusters, each cluster’s size subjecting to an upper bound, so as to minimize the number of disagreements. Here the number of disagreements is defined as the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. Different with the previous algorithm in [18], which subjects to the constraint on the cluster size by a penalty measure, we design an algorithm for the capacitated CorCP to directly output a feasible solution by iteratively constructing clusters based on a preset threshold. Through carefully setting the threshold and sophisticatedly analyzing, our algorithm is proved to have an improved approximation ratio of 5.37. In addition, we also conduct a series of numerical experiments to demonstrate the effectiveness of our algorithm. [ABSTRACT FROM AUTHOR]

Given a set 풫 of h pairwise disjoint convex polygonal obstacles in the plane, defined with n vertices, we preprocess 풫 and compute one routing table at each vertex in a subset of vertices of 풫. For routing a packet from any vertex s ∈풫 to any vertex t ∈풫, our scheme computes a routing path with a multiplicative stretch 1 + 휖 and an additive stretch 2kℓ, by consulting routing tables at only a subset of vertices along that path. Here, k is the number of obstacles of 풫 the routing path intersects, and ℓ depends on the geometry of obstacles in 풫. During the preprocessing phase, we construct routing tables of size O(n + h3 휖2 polylog(h 휖 )) in O(n + h3 휖2 polylog(h 휖 )) time, where 휖 < 1 is an input parameter. [ABSTRACT FROM AUTHOR]

Genome rearrangement events are widely used to estimate a minimum-size sequence of mutations capable of transforming a genome into another. The length of this sequence is called distance, and determining it is the main goal in genome rearrangement distance problems. Problems in the genome rearrangement field differ regarding the set of rearrangement events allowed and the genome representation. In this work, we consider the scenario where the genomes share the same set of genes, gene orientation is known or unknown, and intergenic regions (structures between a pair of genes and at the extremities of the genome) are taken into account. We use two models, the first model allows only conservative events (reversals and moves), and the second model includes non-conservative events (insertions and deletions) in the intergenic regions. We show that both models result in NP-hard problems no matter if gene orientation is known or unknown. When the information regarding the orientation of genes is available, we present for both models an approximation algorithm with a factor of 2. For the scenario where this information is unavailable, we propose a 4-approximation algorithm for both models. [ABSTRACT FROM AUTHOR]

Given a set S of n points, a weight function w to associate a non-negative weight to each point in S, a positive integer k ≥ 1 , and a real number > 0 , we devise the following algorithms to compute a k-vertex fault-tolerant spanner network G (S , E) for the metric space induced by the weighted points in S: (1). When the points in S are located in a simple polygon, we present an algorithm to compute G with multiplicative stretch 1 0 + , and the number of edges in G (size of G) is O (k n (lg n) 2). (2) When the points in S are located in the free space of a polygonal domain with h number of obstacles, we present an algorithm to compute G with multiplicative stretch 6 + and size O (h k n (lg n) 2). (3) When the points in S are located on a polyhedral terrain, we devise an algorithm to compute G with multiplicative stretch 6 + and size O (k n (lg n) 2). [ABSTRACT FROM AUTHOR]

In this paper, we consider the spherical k -means problem with penalties, a robust model of spherical clusterings that requires identifying outliers during clustering to improve the quality of the solution. Each outlier will incur a specified penalty cost. In this problem, one should detect the outliers and propose a k -clustering for the given data set so as to minimize the sum of the clustering and penalty costs. As our main contribution, we present a (1 6 + 8 3) -approximation via single-swap local search and an (8 + 2 7 +) -approximation via multi-swap local search. [ABSTRACT FROM AUTHOR]

In this paper, we concentrate on studying the k -means problem with a matroid or a knapsack constraint. In the matroid means problem, given an observation set and a matroid, the goal is to find a center set from the independent sets to minimize the cost. By using the linear programming (LP) -rounding technology, we obtain a constant approximation guarantee. For the knapsack means problem, we adopt a similar strategy to that of matroid means problem, whereas the difference is that we add a knapsack covering inequality to the relaxed LP in order to decrease the unbounded integrality gap. [ABSTRACT FROM AUTHOR]

Clustering is one of the most important problems in the fields of data mining, machine learning, and biological population division, etc. Moreover, robust variant for k -means problem, which includes k -means with penalties and k -means with outliers, is also an active research branch. Most of these problems are NP-hard even the most classical problem, k -means problem. For the NP-hard problems, the heuristic algorithm is a powerful method. When the quality of the output can be guaranteed, the algorithm is called an approximation algorithm. In this paper, combining two types of robust settings, we consider k -means problem with penalties and outliers (k -MPO). In the k -MPO, we are given an n -point set U ⊂ ℝ d , a penalty cost p v ≥ 0 for each v ∈ U , an integer k ≤ n , and an integer z ≤ n. The target is to find a center subset S ⊆ ℝ d with | S | ≤ k , a penalty subset P ⊆ U and an outlier subset Z ⊆ U with | Z | ≤ z , such that the sum of the total costs, including the connection cost and the penalty cost, is minimized. We offer an approximation algorithm using a heuristic local search scheme. Based on a single-swap manipulation, we obtain 2 7 4 -approximation algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a so-called capacitated min–max correlation clustering model, a natural variant of the min–max correlation clustering problem. As our main contribution, we present an integer programming and its integrality gap analysis for the proposed model. Furthermore, we provide two approximation algorithms for the model, one of which is a bi-criteria approximation algorithm and the other is based on LP-rounding technique. [ABSTRACT FROM AUTHOR]

In this paper, we present an approximation algorithm for the maximum independent set (MIS) problem over the class of B 1 -VPG graphs when the input is specified by a B 1 -VPG representation. We obtain a 6 (log n) 2 -approximation algorithm running in O (n (log n) 3) time. This is an improvement over the previously best n -approximation algorithm [J. Fox and J. Pach, Computing the independence number of intersection graphs, in Proc. Twenty-Second Annual ACM-SIAM Symp. Discrete Algorithms (SODA 2011), 2011, pp. 1161–1165, doi:10.1137/1.9781611973082.87] (for some fixed > 0) designed for some subclasses of string graphs, on B 1 -VPG graphs. [ABSTRACT FROM AUTHOR]

In this paper, the problem we study is how to maximize a monotone non-submodular function with cardinality constraint. Different from the previous streaming algorithms, this paper mainly considers the sliding window model. Based on the concept of diminishing-return ratio γ , we propose a (1 3 γ 2 −) -approximation algorithm with the memory O (k log 2 (k Φ 1 γ) 2 ) , where Φ is the ratio between maximum and minimum values of any singleton element of function f. Then, we improve the approximation ratio to (1 2 γ −) through the sub-windows at the expense of losing some memory. Our results generalize the corresponding results for the submodular case. [ABSTRACT FROM AUTHOR]

Given a set S of n points, a weight function w to associate a non-negative weight to each point in S , a positive integer k ≥ 1 , and a real number > 0 , we present algorithms for computing a spanner network G (S , E) for the metric space (S , d w) induced by the weighted points in S. The weighted distance function d w on the set S of points is defined as follows: for any p , q ∈ S , d w (p , q) is equal to w (p) + d π (p , q) + w (q) if p ≠ q , otherwise, d w (p , q) is 0. Here, d π (p , q) is the Euclidean distance between p and q if points in S are in ℝ d , otherwise, it is the geodesic (Euclidean) distance between p and q. The following are our results: (1) When the weighted points in S are located in ℝ d , we compute a k -vertex fault-tolerant (4 +) -spanner network of size O (k n 2 ). (2) When the weighted points in S are located in the relative interior of the free space of a polygonal domain , we detail an algorithm to compute a k -vertex fault-tolerant (4 +) -spanner network with O (k n h + 1 2 lg n) edges. Here, h is the number of simple polygonal holes in . (3) When the weighted points in S are located on a polyhedral terrain , we propose an algorithm to compute a k -vertex fault-tolerant (4 +) -spanner network, and the number of edges in this network is O (k n 2 lg n). [ABSTRACT FROM AUTHOR]

We introduce and study an inductively defined analogue f IND () of any increasing graph invariant f (). An invariant f () is increasing if f (H) ≤ f (G) whenever H is an induced subgraph of G. This inductive analogue simultaneously generalizes and unifies known notions like degeneracy, inductive independence number, etc., into a single generic notion. For any given increasing f () , this gets us several new invariants and many of which are also increasing. It is also shown that f IND () is the minimum (over all orderings) of a value associated with each ordering. We also explore the possibility of computing f IND () (and a corresponding optimal vertex ordering) and identify some pairs (, f ()) for which f IND () can be computed efficiently for members of . In particular, it includes graphs of bounded f IND () values. Some specific examples (like the class of chordal graphs) have already been studied extensively. We further extend this new notion by (i) allowing vertex weighted graphs, (ii) allowing f () to take values from a totally ordered universe with a minimum and (iii) allowing the consideration of r -neighborhoods for arbitrary but fixed r ≥ 1. Such a generalization is employed in designing efficient approximations of some graph optimization problems. Precisely, we obtain efficient algorithms (by generalizing the known algorithm of Ye and Borodin [Y. Ye and A. Borodin, Elimination graphs, ACM Trans. Algorithms  8(2) (2012) 1–23] for special cases) for approximating optimal weighted induced -subgraphs and optimal -colorings (for hereditary 's) within multiplicative factors of (essentially) k and k / (m − 1) , respectively, where k denotes the inductive analogue (as defined in this work) of optimal size of an unweighted induced -subgraph of the input and m is the minimum size of a forbidden induced subgraph of . Our results generalize the previous result on efficiently approximating maximum independent sets and minimum colorings on graphs of bounded inductive independence number to optimal -subgraphs and -colorings for arbitrary hereditary classes . As a corollary, it is also shown that any maximal -subgraph approximates an optimal solution within a factor of k + 1 for unweighted graphs, where k is maximum size of any induced -subgraph in any local neighborhood N G (u). [ABSTRACT FROM AUTHOR]

We introduce and study an inductively defined analogue f IND () of any increasing graph invariant f (). An invariant f () is increasing if f (H) ≤ f (G) whenever H is an induced subgraph of G. This inductive analogue simultaneously generalizes and unifies known notions like degeneracy, inductive independence number, etc., into a single generic notion. For any given increasing f () , this gets us several new invariants and many of which are also increasing. It is also shown that f IND () is the minimum (over all orderings) of a value associated with each ordering. We also explore the possibility of computing f IND () (and a corresponding optimal vertex ordering) and identify some pairs (, f ()) for which f IND () can be computed efficiently for members of . In particular, it includes graphs of bounded f IND () values. Some specific examples (like the class of chordal graphs) have already been studied extensively. We further extend this new notion by (i) allowing vertex weighted graphs, (ii) allowing f () to take values from a totally ordered universe with a minimum and (iii) allowing the consideration of r -neighborhoods for arbitrary but fixed r ≥ 1. Such a generalization is employed in designing efficient approximations of some graph optimization problems. Precisely, we obtain efficient algorithms (by generalizing the known algorithm of Ye and Borodin [Y. Ye and A. Borodin, Elimination graphs, ACM Trans. Algorithms  8(2) (2012) 1–23] for special cases) for approximating optimal weighted induced -subgraphs and optimal -colorings (for hereditary 's) within multiplicative factors of (essentially) k and k / (m − 1) , respectively, where k denotes the inductive analogue (as defined in this work) of optimal size of an unweighted induced -subgraph of the input and m is the minimum size of a forbidden induced subgraph of . Our results generalize the previous result on efficiently approximating maximum independent sets and minimum colorings on graphs of bounded inductive independence number to optimal -subgraphs and -colorings for arbitrary hereditary classes . As a corollary, it is also shown that any maximal -subgraph approximates an optimal solution within a factor of k + 1 for unweighted graphs, where k is maximum size of any induced -subgraph in any local neighborhood N G (u). [ABSTRACT FROM AUTHOR]

This paper reports new techniques that exploit the security of the prime power moduli N = p r q s using continued fraction method. Our study shows that the key equation e d − k ϕ (N) = 1 can be exploited using N − 2 r + s 2 r N r + s − 1 2 r + 2 r + s − 2 2 r N r + s − 2 2 r as good approximation of ϕ (N). This enables us to get k d from the convergents of the continued fractions expansion of e N − 2 r + s 2 r N r + s − 1 2 r + 2 r + s − 2 2 r N r + s − 2 2 r where the bound of the private exponent is d < 1 2 (N − 2 r + s 2 r N r + s − 1 2 r + 2 r + s − 2 2 r N r + s − 2 2 r ) which leads to the polynomial time factorization of the moduli N = p r q s . We further report the polynomial time attacks that can break the security of the generalized prime power moduli N u = p u r q u s using generalized system of equation of the form e u d − k u ϕ (N u) = 1 and e u d u − k ϕ (N u) = 1 by applying simultaneous Diophantine approximations and LLL algorithm techniques where 2 ≤ s < r and u = 1 , ... , v. [ABSTRACT FROM AUTHOR]

In this paper, we derive a new recovery procedure for the reconstruction of extended exponential sums of the form y (t) = ∑ j = 1 M (∑ m = 0 n j γ j , m t m) e 2 π λ j t , where the frequency parameters λ j ∈ ℂ are pairwise distinct. In order to reconstruct y(t) we employ a finite set of classical Fourier coefficients of y with regard to a finite interval (0 , P) ⊂ ℝ with P > 0. For our method, 2N + 2 Fourier coefficients c k (y) are sufficient to recover all parameters of y, where N : = ∑ j = 1 M (1 + n j) denotes the order of y(t). The recovery is based on the observation that for λ j ∉ i P ℤ the terms of y(t) possess Fourier coefficients with rational structure. We employ a recently proposed stable iterative rational approximation algorithm in [Y. Nakatsukasa, O. Sète and L. N. Trefethen, The AAA Algorithm for rational approximation, SIAM J. Sci. Comput.40(3) (2018) A1494A1522]. If a sufficiently large set of L Fourier coefficients of y is available (i.e. L ≥ 2 N + 2), then our recovery method automatically detects the number M of terms of y, the multiplicities n j for j = 1 , ... , M , as well as all parameters λ j , j = 1 , ... , M , and γ j , m , j = 1 , ... , M , m = 0 , ... , n j , determining y(t). Therefore, our method provides a new stable alternative to the known numerical approaches for the recovery of exponential sums that are based on Prony's method. [ABSTRACT FROM AUTHOR]

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 } which satisfies the following conditions is called a weakly connected Roman dominating function (WCRDF) of G with weight h (V) = ∑ p ∈ V h (p). (C1). For all q ∈ V with h (q) = 0 there exists a vertex r such that (q , r) ∈ E and h (r) = 2 and (C2). The graph with vertex set V (G) and edge set { (p , z) : h (p) ≥ 1 or h (z) ≥ 1 or both } is connected. The problem of determining WCRDF of minimum weight is called minimum weakly connected Roman domination problem (MWCRDP). In this paper, we show that MWCRDP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a 2 (1 +) (1 + ln (Δ − 1)) -approximation algorithm for the MWCRDP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless P = N P. Next, we show that MWCRDP is APX-hard for graphs with Δ = 4. We also show that the domination and weakly connected Roman domination problems are not equivalent in computational complexity aspects. Finally, two different integer linear programming formulations for MWCRDP are proposed. [ABSTRACT FROM AUTHOR]

Many modern applications such as sensor networks produce probabilistic data. These data are collected into an uncertain database. To interpret uncertainty and to mine frequent patterns in an uncertain database, all possible certain databases are considered, which generates an exponential number of combinations and makes the mining problem highly complicated. In practice, mining is interactive, which makes the discovery of frequent itemsets in an uncertain database even more challenging. The objective of interactive mining is to shorten the time that is required to obtain the desired patterns in the iterated lengthy mining process. The time-consuming mining process in an uncertain database is exacerbated by repeated processing if the mining is performed from scratch. Therefore, we propose an interactive mining algorithm called iDIP to solve this problem. The iDIP algorithm adopts an approximation mechanism to mine the patterns and prunes candidates by using the existing patterns. Comprehensive experiments using both real and synthetic datasets show that iDIP outperforms the well-known re-mining-based MB algorithm for 4.3 times faster on average. In addition, iDIP has good linear scalability. [ABSTRACT FROM AUTHOR]

Given a complete graph G = (V , E) , with nonnegative edge costs, two subsets R ⊂ V and R ′ ⊂ R , a partition ℛ = { R 1 , R 2 , ... , R k } of R , R i ∩ R j = ϕ , i ≠ j and ℛ ′ = { R 1 ′ , R 2 ′ , ... , R k ′ } of R ′ , R i ′ ⊂ R i , a clustered Steiner tree is a tree T of G that spans all vertices in R such that T can be cut into k subtrees T i by removing k − 1 edges and each subtree T i spans all vertices in R i , 1 ≤ i ≤ k. The cost of a clustered Steiner tree is defined to be the sum of the costs of all its edges. A clustered selected-internal Steiner tree of G is a clustered Steiner tree for R if all vertices in R i ′ are internal vertices of T i . The clustered selected-internal Steiner tree problem is concerned with the determination of a clustered selected-internal Steiner tree T for R and R ′ in G with minimum cost. In this paper, we present the first known approximation algorithm with performance ratio (ρ + 4) for the clustered selected-internal Steiner tree problem, where ρ is the best-known performance ratio for the Steiner tree problem. [ABSTRACT FROM AUTHOR]

Let G A be a family of graphs and let J be a set of connected graphs, each with at most r vertices, r fixed. A J -packing of a graph GA is a vertex induced subgraph of GA with every connected component isomorphic to a member of J. A maximum weight k -covering of a graph GA by J -packings, is a maximum weight subgraph of GA exactly covered by k vertex disjoint J -packings. For a graph G A ∈ G A let J (GA) be a graph, every vertex v of which corresponds to a vertex subgraph a (v) of GA isomorphic to a member of J , two vertices u , v of J (GA) being adjacent if and only if a (u) and a (v) have common vertices or interconnecting edges. The closed neighborhoods containment graph C N C G (G A) of a graph G A (V , D) ∈ G A , is the graph with vertex set V and edges directed from vertices u to v if and only if they are adjacent in GA and the closed neighborhood of u is contained in the closed neighborhood of v. A graph G (V , E) is a G A − H reduced graph if it can be obtained from a graph G A (V , D) ∈ G A by deleting the edges of a transitive subgraph H of CNCG(GA). We describe 1.582-approximation algorithms for maximum weight k -coverings by J -packings of G A and G A − H reduced graphs when G A is vertex hereditary, has an algorithm for maximum weight independent set and J (G A) ⊆ G A. These algorithms can be applied to families of interval filament, subtree filament, weakly chordal, AT-free and circle graphs, to find 1.582 approximate maximum weight k -coverings by vertex disjoint induced matchings, dissociation sets, forests whose subtrees have at most r vertices, etc. [ABSTRACT FROM AUTHOR]

Fog Computing extends storage and computation resources closer to end-devices. In several cases, the Internet of Things (IoT) applications that are time-sensitive require low response time. Thus, reducing the latency in IoT networks is one of the essential tasks. To this end, fog computing is developed with a motive for the data production and consumption to always be within proximity; therefore, the fog nodes must be placed at the edge of the network, which is near the end devices, such that the latency is minimized. The optimal location selection for fog node placement within a network out of a very large number of possibilities, such as minimize latency, is a challenging problem. So, it is a combinatorial optimization problem. Hard combinatorial optimization problems (NP-hard) involve huge discrete search spaces. The fog node placement problem is an NP-hard problem. NP-hard problems are often addressed by using heuristic methods and approximation algorithms. Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items; therefore in principle, any metaheuristic can be used to solve them. To resolve this, meta-heuristic-based methods is proposed. We apply the Simulated Annealing (SA), Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) technique to design fog node placement algorithms. Genetic Algorithm is observed to give better solutions. Since Genetic Algorithm may get stuck in local optima, Hybrid Genetic Algorithm, and Simulated Annealing (GA-SA), Hybrid Genetic Algorithm and Particle Swarm Optimization (GA-PSO) were compared with GA. By extensive simulations, it is observed that hybrid GA-SA-based for node placement algorithm outperforms other baseline algorithms in terms of response time for the IoT applications. [ABSTRACT FROM AUTHOR]

We study how a monopolist seller should price an indivisible product iteratively to the consumers who are connected by a known link-weighted directed social network. For two consumers u and v , there is an arc directed from u to v if and only if v is a fashion leader of u. Assuming complete information about the network, the seller offers consumers a sequence of prices over time and the goal is to obtain the maximum revenue. We assume that the consumers buy the product as soon as the seller posts a price not greater than their valuations of the product. The product's value for a consumer is determined by three factors: a fixed consumer specified intrinsic value and a variable positive (resp. negative) externality that is exerted from the consumer's out(resp. in)-neighbours. The setting of positive externality is that the influence of fashion leaders on a consumer is the total weight of links from herself to her fashion leaders who have owned the product, and more fashion leaders of a consumer owning the product will increase the influence (external value) on the consumer. And the setting of negative externalities is that the product's value of showing off for a consumer is the total weight of links from her followers who do not own the product to herself, and more followers of a consumer owning the product will decrease this external value for the consumer. We confirm that finding an optimal iterative pricing is NP-hard even for acyclic networks with maximum total degree 3 and with all intrinsic values zero. We design a greedy algorithm which achieves (n − 1) -approximation for networks with all intrinsic values zero and show that the approximation ratio n − 1 is tight. Complementary to the hardness result, we design a (1. 8 +) -approximation algorithm for Barabási–Albert networks. [ABSTRACT FROM AUTHOR]

The classical Feynman–Kac identity builds a bridge between stochastic analysis and partial differential equations (PDEs) by providing stochastic representations for classical solutions of linear Kolmogorov PDEs. This opens the door for the derivation of sampling based Monte Carlo approximation methods, which can be meshfree and thereby stand a chance to approximate solutions of PDEs without suffering from the curse of dimensionality. In this paper, we extend the classical Feynman–Kac formula to certain semilinear Kolmogorov PDEs. More specifically, we identify suitable solutions of stochastic fixed point equations (SFPEs), which arise when the classical Feynman–Kac identity is formally applied to semilinear Kolmorogov PDEs, as viscosity solutions of the corresponding PDEs. This justifies, in particular, employing full-history recursive multilevel Picard (MLP) approximation algorithms, which have recently been shown to overcome the curse of dimensionality in the numerical approximation of solutions of SFPEs, in the numerical approximation of semilinear Kolmogorov PDEs. [ABSTRACT FROM AUTHOR]

An important characteristic of a fractal signal is that its graph is not smooth in any small interval. This indicates the difficulty of the approximation of fractal signals, because traditional approximation methods normally require some certain smoothness of the approximated function. However, recent studies have shown that fractal functions that satisfy the Hölder condition can be linearly changed in the fractal dimension of their graphs by the fractional calculus, which implies that we can use the fractional calculus to make graphs of fractal signals smoother, and then approximate these fractal signals. This paper first gives our research background and related theories of fractals and the fractional calculus, and then introduces the main research content, including the following aspects: (1) Proposing a fractal signal approximation algorithm, the R-L algorithm, explaining and deriving how to implement this algorithm. (2) Aiming at a specific fractal signal, carrying out an approximation experiment, and confirming the R-L algorithm is better than a direct approximation. (3) According to the experimental process and conclusions, introducing our future work, such as further optimization of the R-L algorithm, and showing the R-L algorithm may have the predictive capability outside the sampling interval. The R-L algorithm can effectively modify the smoothness of graphs of the fractal signal, so that more types of approximation algorithms can be selected with a better approximation effect. [ABSTRACT FROM AUTHOR]

In some of the previous decades, we have observed that mathematical modeling has become one of the most interesting research fields and has attracted many researchers. In this regard, thousands of researchers have proposed different varieties of mathematical models to study the dynamics of a number of real-world problems. This research work is framed to analyzing the structure of the well-known Lassa hemorrhagic epidemic; a dangerous epidemic for pregnant women, via new generalized Caputo type noninteger order derivative with the help of a modified Predictor–Corrector scheme. Lassa hemorrhagic disease is an epidemical and biocidal fever, whose negative impacts were initially recognized in the countries of Africa. This virus has killed many pregnant women as compared to the Ebola epidemic. It was noticed that Lassa virus was isolated in Vero cell cultures from a blood pattern, and after 12 days it was ejective, after the climb of the sickness. In this research study, necessary theorems and lemmas are reminded to prove the existence of a unique solution and stability of given fractional approximation scheme. All necessary results are reminded to confirm the effectiveness of the proposed approximation algorithm by graphical observations for various fractional-order values. In our practical calculations, we plotted the graphs for two different values of natural death rate along with various values of given fractional-order operator. Our major target is to show the importance of the proposed modified version of the Predictor–Corrector algorithm in epidemic studies by exploring the given Lassa hemorrhagic fever dynamics. [ABSTRACT FROM AUTHOR]

We consider the total weighted early work maximization problem on identical machines in parallel such that the weights are identical, or the due date is the same. First, we present an approach to solve the case with a fixed number of machines in pseudo-polynomial time. Then, we develop approximation algorithms for the two cases with identical weights and with a common due date. For the case with identical weights, furthermore, we show that the parallel-machine and a single-machine cases are strongly NP-hard and weakly NP-hard, respectively, even if the due date of each job is equal to the processing time multiplied by a constant. [ABSTRACT FROM AUTHOR]

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 , 3 } which satisfies the following conditions is called a total Roman {3}-dominating function (TR3DF) of G with weight h (V) = ∑ p ∈ V h (p) : (C1) For every vertex u ∈ V if h (u) = 0 , then u has m (m ≥ 1) neighbors such that whose sum is at least 3, and if h (u) = 1 , then u has n (n ≥ 1) neighbors such that whose sum is at least 2. (C2) The subgraph induced by the set of vertices labeled one, two or three has no isolated vertices. For a graph G , the smallest possible weight of a TR3DF of G denoted γ t { R 3 } (G) is known as the total Roman { 3 } -domination number of G. The problem of determining γ t { R 3 } (G) of a graph G is called minimum total Roman {3}-domination problem (MTR3DP). In this paper, we show that the problem of deciding if G has a TR3DF of weight at most l for chordal graphs is NP-complete. We also show that MTR3DP is polynomial time solvable for bounded treewidth graphs, chain graphs and threshold graphs. We design a 3 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for the MTR3DP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless NP ⊆ DTIME (| V | O (log log | V |)). Next, we show that MTR3DP is APX-complete for graphs with Δ = 4. We also show that the domination and total Roman {3}-domination problems are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MTR3DP. [ABSTRACT FROM AUTHOR]

The problem of maximization submodular functions with a cardinality constraint has been extensively researched in recent years. Balkanski and Singer were the first to study this class problem. Subsequently, Chekuri and Kent recently extended these results to more general constraints, that is, k -cardinality constraint, partition and laminar matroids, matching, knapsack constraints, and including their intersection. They proposed a (1 − 1 / e −) approximation randomized-parallel-greedy algorithm which are poly-logarithmic adaptivity. However, these existing approaches are hardly extended to the nonsubmodular case. In this paper, we investigate the problem of maximization on a nonsubmodular function subject to a cardinality constraint, provided the objective function is specified by a generic submodularity ratio γ. We design a (1 − e − γ −) -approximation Greedy algorithm by using the technical aspects to maximize the multilinear relaxation of the object function under the k -cardinality constraints. The adaptive of multilinear relaxation is O (log n / 2) ; the number of oracle is Õ (n / 4). [ABSTRACT FROM AUTHOR]

Emerging applications such as optimal budget allocation and sensor placement impose problems of maximizing variants of submodular functions with constraints under a streaming setting. In this paper, we first devise a streaming algorithm based on Sieve-Streaming for maximizing a monotone diminishing return submodular (DR-submodular) function with a cardinality constraint on the integer lattice and show it is a one-pass algorithm with approximation ratio 1 2 − . The key idea to ensure one pass for the algorithm is to combine binary search for determining the level of an element with the exponential-growth method for estimating the OPT. Inspired by Sieve-Streaming++, we then improve the memory of the algorithm to O (k ) and the query complexity to O (k log 2 k ). [ABSTRACT FROM AUTHOR]

We investigate the problem of maximizing a γ -submodular function subject to one or multiple matroid constraints and one knapsack constraint. By the greedy local search technique, we present approximation algorithms with constant approximation ratios. When γ = 1 , our model reduces to the regular submodular maximization problem investigated in the literature under the same type of constraints. Our results therefore contribute towards the line of research on constrained non-submodular function maximization. [ABSTRACT FROM AUTHOR]

The implicit frequency dependence of linear systems arising from the acoustic boundary element method necessitates an efficient treatment for problems in a frequency range. Instead of solving the linear systems independently at each frequency point, this paper is concerned with solving them simultaneously at multiple frequency points within a single iteration scheme. The proposed concept is based on truncation of the frequency range solution and is incorporated into two well-known iterative solvers - BiCGstab and GMRes. The proposed method is applied to two acoustic interior problems as well as to an exterior problem in order to assess the underlying approximations and to study the convergence behavior. While this paper provides the proof of concept, its application to large-scale acoustic problems necessitates efficient preconditioning for multi-frequency systems, which are yet to be developed. [ABSTRACT FROM AUTHOR]

In the field of comparative genomics, one way of comparing two genomes is through the analysis of how they distinguish themselves based on a set of mutations called rearrangement events. When considering that genomes undergo different types of rearrangements, it can be assumed that some events are more common than others. To model this assumption, one can assign different weights to different events, where common events tend to cost less than others. However, this approach, called weighted, does not guarantee that the rearrangement assumed to be the most frequent will be also the most frequently returned by proposed algorithms. To overcome this issue, we investigate a new problem where we seek the shortest sequence of rearrangement events able to transform one genome into the other, with a restriction regarding the proportion between the events returned. Here, we consider two rearrangement events: reversal, that inverts the order and the orientation of the genes inside a segment of the genome, and transposition, that moves a segment of the genome to another position. We show the complexity of this problem for any desired proportion considering scenarios where the orientation of the genes is known or unknown. We also develop an approximation algorithm with a constant approximation factor for each scenario and, in particular, we describe an improved (asymptotic) approximation algorithm for the case where the gene orientation is known. At last, we present the experimental tests comparing the proposed algorithms with others from the literature for the version of the problem without the proportion restriction. [ABSTRACT FROM AUTHOR]

k -submodular maximization is a generalization of submodular maximization, which requires us to select k disjoint subsets instead of one subset. Attracted by practical values and applications, we consider k -submodular maximization with two kinds of constraints. For total size and individual size difference constraints, we present a 1 − e − 1 k − 𝜖 -approximation algorithm for maximizing a nonnegative k-submodular function, running in time O (n (k − 1) ! 𝜖 log n 𝜖 + k (k − 1)) at worst. Specially, if B is multiple of k , the approximation ratio can reduce to 1 − e − 1 k − 1 − 𝜖 , running in time O n (k − 1) ! 𝜖 log n 𝜖 at worst. Besides, this algorithm can be applied to α -bisubmodular achieving 1 − 1 e − 𝜖 -approximation running in time O n 𝜖 log n 𝜖 + 2 . Furthermore, if B is multiple of 2, the approximation ratio can reduce to (1 − 1 / e − 𝜖) , running in time O n 𝜖 log n 𝜖 at worst. For individual size constraint, there is a (1 − 1 / e − 𝜖) -approximation algorithm for maximizing a nonnegative k -submodular function and an nonnegative α -bisubmodular function, running in time O n k ! 𝜖 log n 𝜖 and O 2 n 𝜖 log n 𝜖 , respectively, at worst. [ABSTRACT FROM AUTHOR]

The Prize-collecting Steiner tree (PCST) problem is a generalization of the Steiner tree problem that finds applications in network design, content distribution networks, and many more. There are a few centralized approximation algorithms [D. Bienstock, M. X. Goemans, D. Simchi-Levi and D. Williamson, A note on the prize collecting traveling salesman problem. Math. Program.59 (1993) 413–420; M. X. Goemans and D. E. Williamson, A general approximation technique for constrained forest problems, SIAM J. Appl. Math.24(2) (1995) 296–317; D. S. Johnson, M. Minkoff and S. Phillips, The prize collecting Steiner tree problem: Theory and practice, in Proc. Eleventh Annual ACM-SIAM Symp. Discrete Algorithms, SODA '00 (2000), pp. 760–769; A. Archer, M. Hossein Bateni and M. Taghi Hajiaghayi, Improved approximation algorithms for prize-collecting Steiner tree and TSP, SIAM J. Comput.40(2) (2011) 309–332] for solving the PCST problem. However, the problem has seen very little progress in the distributed setting; to the best of our knowledge, the only distributed algorithms proposed so far are due to Rossetti [N. G. Rossetti, A first attempt on the distributed prize-collecting Steiner tree problem, M.Sc. thesis, University of Iceland, Reykjavik (2015)]: one of them fails to guarantee a constant approximation factor while the other one is essentially centralized. In this work, first, we present a deterministic 2 − 1 n − 1 factor distributed approximation algorithm (D-PCST algorithm) that constructs a PCST for a given connected undirected graph of n nodes with non-negative edge weights and non-negative prize value for each node. The D-PCST algorithm is based on the primal-dual method and uses a technique of preserving dual constraints in a distributed manner, without relying on knowledge of the global structure of the network. For an input graph G = (V , E) , the round and message complexities of the D-PCST algorithm in the CONGEST model are O (n 2) and O (m n) , respectively, where n = | V | and m = | E |. Furthermore, we modify the D-PCST algorithm and show that a (2 − 1 n − 1) -approximate PCST can be deterministically computed using O (D n) rounds and O (m n) messages in the CONGEST model, where D is the unweighted diameter of G. For networks with D = o (n) , the modified D-PCST algorithm performs better than the original one in terms of the round complexity. Both the algorithms require O (Δ log n) bits of memory in each node, where Δ is the maximum degree of a node in the graph. [ABSTRACT FROM AUTHOR]

We study a maximization problem for geometric network design. Given a set of n compact neighborhoods in ℝ d , select a point in each neighborhood, so that the longest spanning tree on these points (as vertices) has maximum length. Here, we give an approximation algorithm with ratio 0. 5 1 1 , which represents the first, albeit small, improvement beyond 1 / 2. While we suspect that the problem is NP-hard already in the plane, this issue remains open. [ABSTRACT FROM AUTHOR]

We present new results on two types of guarding problems for polygons. For the first problem, we present an optimal linear time algorithm for computing a smallest set of points that guard a given shortest path in a simple polygon having n edges. We also prove that in polygons with holes, there is a constant c > 0 such that no polynomial-time algorithm can solve the problem within an approximation factor of c log n , unless P=NP. For the second problem, we present a (k + h) -FPT algorithm for computing a shortest tour that sees k specified points in a polygon with h holes. We also present a k -FPT approximation algorithm for this problem having approximation factor 2 . In addition, we prove that the general problem cannot be polynomially approximated better than by a factor of c log n , for some constant c > 0 , unless P  = NP. [ABSTRACT FROM AUTHOR]

Numerous optimization variables cause the optimization of large-scale field development challenging, which can be overcome by constraining wells to be within patterns and optimizing the parameters relevant to the pattern type and geometry. In this study, a new method incorporating well pattern optimization and production optimization for unconventional reservoirs is presented. By defining a quantitative well pattern description approach, we develop the geometric transformation parameters to quantify well pattern operations (e.g., rotation, shear, especially translation) to change the geometric shape of well patterns including five-spot, inverse seven-spot and inverse nine-spot well pattern. In contrast, a variety of optimization algorithms can be applied to accomplish the optimization of well pattern problems but the computational cost is large for many algorithms. Therefore, we also propose a general upscaling stochastic approximation algorithm (GUSA), which is an improved approximate perturbation gradient algorithm, to realize the combination of well pattern optimization and production optimization simultaneously. It is proved that both the gradient formulation of SPSA algorithm and EnOpt algorithm are the special form of the general approximate perturbation gradient. Afterwards, the synthetic cases (homogeneous and heterogeneous models) and actual unconventional field cases are discussed based on the three mentioned well pattern types. The detailed optimization results show that the presented coupling method can achieve the optimization by transforming well pattern geometry, reducing the total number of wells and adjusting the field injection rate, which is proved to be effective. In sum, this coupling method provides an efficient optimization procedure combing the well pattern optimization and production optimization for practical field development. [ABSTRACT FROM AUTHOR]

We propose a variance-based modified backward-forward algorithm with a stochastic approximation version of Armijo's line search, which is robust with respect to an unknown Lipschitz constant, for solving a class of stochastic variational inequality problems. A salient feature of the proposed algorithm is to compute only one projection and two independent queries of a stochastic oracle at each iteration. We analyze the proposed algorithm for its asymptotic convergence, sublinear convergence rate in terms of the mean natural residual function, and optimal oracle complexity under moderate conditions. We also discuss the linear convergence rate with finite computational budget for the proposed algorithm without strong monotonicity. Preliminary numerical experiments indicate that the proposed algorithm is competitive with some existing algorithms. Furthermore, we consider an application in dealing with an equilibrium problem in stochastic natural gas trading market. [ABSTRACT FROM AUTHOR]

One of the main problems in Computational Biology is to find the evolutionary distance among species. In most approaches, such distance only involves rearrangements, which are mutations that alter large pieces of the species' genome. When we represent genomes as permutations, the problem of transforming one genome into another is equivalent to the problem of Sorting Permutations by Rearrangement Operations. The traditional approach is to consider that any rearrangement has the same probability to happen, and so, the goal is to find a minimum sequence of operations which sorts the permutation. However, studies have shown that some rearrangements are more likely to happen than others, and so a weighted approach is more realistic. In a weighted approach, the goal is to find a sequence which sorts the permutations, such that the cost of that sequence is minimum. This work introduces a new type of cost function, which is related to the amount of fragmentation caused by a rearrangement. We present some results about the lower and upper bounds for the fragmentation-weighted problems and the relation between the unweighted and the fragmentation-weighted approach. Our main results are 2-approximation algorithms for five versions of this problem involving reversals and transpositions. We also give bounds for the diameters concerning these problems and provide an improved approximation factor for simple permutations considering transpositions. [ABSTRACT FROM AUTHOR]

In this paper, we consider a restricted covering problem, in which a convex polygon P with n vertices and an integer k are given, the objective is to cover the entire region of P using k congruent disks of minimum radius r o p t , centered on the boundary of P. For k ≥ 7 and any 𝜖 > 0 , we propose an (1 + 7 k + 7 𝜖 k + 𝜖) -factor approximation algorithm for this problem, which runs in O ((n + k) (| log r o p t | + log ⌈ 1 𝜖 ⌉)) time. The best known approximation factor of the algorithm for the problem in the literature is 1.8841 [H. Du and Y. Xu: An approximation algorithm for k -center problem on a convex polygon, J. Comb. Optim. 27(3) (2014) 504–518]. [ABSTRACT FROM AUTHOR]

The minimum power assignment problem in a Wireless Sensor Network (WSN) is to assign transmission range to the nodes of the network with specified connectivity constraints minimizing the total power. This problem is termed as Strong Minimum Energy Topology (SMET) problem. Fault tolerance addresses the issue of a node or link failure in a WSN. So, with an objective of achieving high connectivity, we consider SMET problem with an additional property, i.e., the resultant network must satisfy the property of two or high connectivity. Minimum Power r -Connected Subgraph (MP r CS) problem is to contrive an r -connected network with minimum power. Minimum Power 2 -Connected Subgraph (MP2CS) problem is proved to be NP -hard. Minimum Power k Backbone node r -Connected Subgraph (MP k B r CS) problem is a special case of MP r CS problem, which seeks a power assignment satisfying r -connectivity with k backbone nodes. We study MP k B r CS problem for k backbone nodes, r -connectivity and derive the approximation ratios. We also propose an algorithm of approximation ratio n + 2 2 , for Minimum Power k Backbone node 3-Connected Subgraph (MP k B3CS) problem for k = 2 that runs in O (n 4) time and generalize for the case r = k + 1 for any k and r. [ABSTRACT FROM AUTHOR]