Search

We present a general technique for approximating bicriteria minimization problems with positive-valued, polynomially computable objective functions. Given 0 < ϵ ≤ 1 and a polynomial-time α -approximation algorithm for the corresponding weighted sum problem, we show how to obtain a bicriteria ( α ⋅ ( 1 + 2 ϵ ) , α ⋅ ( 1 + 2 ϵ ) ) -approximation algorithm for the budget-constrained problem whose running time is polynomial in the encoding length of the input and linear in 1 ϵ . Moreover, we show that our method can be extended to compute an ( α ⋅ ( 1 + 2 ϵ ) , α ⋅ ( 1 + 2 ϵ ) ) -approximate Pareto curve under the same assumptions. Our technique applies to many minimization problems to which most previous algorithms for computing approximate Pareto curves cannot be applied because the corresponding gap problem is NP -hard to solve. For maximization problems, however, we show that approximation results similar to the ones presented here for minimization problems are impossible to obtain in polynomial time unless P = NP . [ABSTRACT FROM AUTHOR]

We revisit a classical problem in transportation, known as the (bilevel) continuous network design problem, CNDP for short. Given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed, the goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing costs of the induced Wardrop equilibrium and the investment costs for installing the edge's capacities. While this problem is considered to be challenging in the literature, its complexity status was still unknown. We close this gap, showing that CNDP is strongly NP-hard and APX-hard, both on directed and undirected networks and even for instances with affine latencies. As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions [P. Marcotte, Math. Prog., 34 (1986), pp. 142{162]. We derive a closed form expression of its approximation guarantee for arbitrary sets of latency functions. We then propose a different approximation algorithm and show that it has the same approximation guarantee. Then, we prove that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we derive a closed form expression. For affine latencies, for example, this best-of-two approach achieves an approximation factor of 49=41 ≈ 1:195, which improves on the factor of 5=4 that has been shown before by Marcotte. [ABSTRACT FROM AUTHOR]

In this paper we study parallel-machine scheduling with job rejection, where the total processing time of the rejected jobs is required to be no greater than a predefined bound. The objective is to minimize the makespan of the accepted jobs plus the total penalty cost of the rejected jobs. The scheduling problem is NP-hard in the strong sense. We present a 2-approximation algorithm with a time complexity of O ( n log ⁡ n ) by making use of specific data structure. We also develop a polynomial time approximation scheme (PTAS). Due to the job rejection restriction, some techniques for knapsack problems are applied in the development of our PTAS. [ABSTRACT FROM AUTHOR]

The capacitated unit covering problem is a generalization of the bin packing and the unit covering problems. In its one-dimensional case, there arenweighted points on a line and we want to partition them into a minimum number of sets such that (i) the total weight of points in each set is no more than one and (ii) the points in each set can be covered by a unit-length interval. The problem is not approximable within a factor better than 1.5 unless P = NP. We analyse a generalization of the first-fit algorithm for this problem, which runs inO(nlogn) time, and prove that when no point has weight more than, its approximation ratio is exactly ≈ 1.667. [ABSTRACT FROM AUTHOR]

Progressive Visual Analytics aims at improving the interactivity in existing analytics techniques by means of visualization as well as interaction with intermediate results. One key method for data analysis is dimensionality reduction, for example, to produce 2D embeddings that can be visualized and analyzed efficiently. t-Distributed Stochastic Neighbor Embedding (tSNE) is a well-suited technique for the visualization of high-dimensional data. tSNE can create meaningful intermediate results but suffers from a slow initialization that constrains its application in Progressive Visual Analytics. We introduce a controllable tSNE approximation (A-tSNE), which trades off speed and accuracy, to enable interactive data exploration. We offer real-time visualization techniques, including a density-based solution and a Magic Lens to inspect the degree of approximation. With this feedback, the user can decide on local refinements and steer the approximation level during the analysis. We demonstrate our technique with several datasets, in a real-world research scenario and for the real-time analysis of high-dimensional streams to illustrate its effectiveness for interactive data analysis. [ABSTRACT FROM AUTHOR]

A novel adaptive step-size matching pursuit algorithm (AStMP) is proposed. AStMP reduces the computational cost and increases the accuracy of reconstructing practical signals (i) whose sparsity K is unknown and/or (ii) may be corrupted by noise. AStMP accurately estimates K by combining the sparsity estimate of sparsity adaptive subspace pursuit (SASP) with the adaptively changing stepsize at each stage of sparsity adaptive matching pursuit (SAMP). Thus, AStMP can quickly achieve accurate estimation of the sparsity level and the true support set of the target signals. Meanwhile, a preselection is employed to reduce the computational complexity of each stage. When K is greater than half the number of measurements M, the probability of exact recovery is improved by analyzing the support set. Since the stepsize changes adaptively, AStMP can be applied in both the noiseless and noisy cases when the signal is not strictly sparse, allowing for exact or approximate signal recovery. Experimental results demonstrate that the AStMP is effective in fast and exact reconstruction and has good performance. [ABSTRACT FROM AUTHOR]

Multi-group multicast beamforming in wireless systems with large antenna arrays and massive audience is investigated in this paper. Multicast beamforming design is a well-known non-convex quadratically constrained quadratic programming (QCQP) problem. A conventional method to tackle this problem is to approximate it as a semi-definite programming problem via semi-definite relaxation, whose performance, however, deteriorates considerably as the number of per-group users goes large. A recent attempt is to apply convex-concave procedure (CCP) to find a stationary solution by treating it as a difference of convex programming problem, whose complexity, however, increases dramatically as the problem size increases. In this paper, we propose a low-complexity high-performance algorithm for multi-group multicast beamforming design in large-scale wireless systems by leveraging the alternating direction method of multipliers (ADMM) together with CCP. In specific, the original non-convex QCQP problem is first approximated as a sequence of convex subproblems via CCP. Each convex subproblem is then reformulated as a novel ADMM form. Our ADMM reformulation enables that each updating step is performed by solving multiple small-size subproblems with closed-form solutions in parallel. Numerical results show that our fast algorithm maintains the same favorable performance as state-of-the-art algorithms but reduces the complexity by orders of magnitude. [ABSTRACT FROM PUBLISHER]

Let G = ( V , E ) be a unit disk graph corresponding to a given set P of n points in R 2 . We propose a distributed approximation algorithm to find a minimum connected dominating set of G . The maintenance of the connected dominating set constructed is fully localized. Our algorithm produces a connected dominating set of size ( 104 o p t + 52 ) , where o p t is the size of a minimum connected dominating set. The time and message complexities of our algorithm are O ( Δ ) and O ( n ) respectively, where Δ and n are the maximum node degree and number of nodes in G respectively. Our distributed approximation algorithm outperforms existing algorithms in terms of its time and message complexities. We also propose a scheduling scheme that obtains O ( Δ ) conflict-free time slots to deal with interference. [ABSTRACT FROM AUTHOR]

The Gromov-Hausdorff distance of two compact metric spaces is a measure for how far the spaces are from being isometric and has been extensively studied in the field of metric geometry. In recent years, a lot of attention has been devoted to computational aspects of the Gromov-Hausdorff distance. One of the most prominent applications is the problem of shape matching, where the goal is to decide whether two shapes given as polygonal meshes are equivalent under certain invariances. Therefore, many methods have been proposed which heuristically estimate the Gromov-Hausdorff distance of metric spaces induced by the shapes. However, the computational complexity of computing the Gromov-Hausdorff distance has not yet been thoroughly investigated. We show that-under standard complexity theoretic assumptions-determining the Gromov-Hausdorff distance of two finite metric spaces cannot be approximated within any reasonable bound in polynomial time. Furthermore, we discover attributes of metric spaces which have a major impact on the complexity of an instance. This enables us to develop an approximation algorithm which is fixed parameter tractable with respect to corresponding parameters. [ABSTRACT FROM AUTHOR]

We consider scheduling of unit-length jobs with release times and deadlines, where the objective is to minimize the number of gaps in the schedule. Polynomial-time algorithms for this problem are known, yet they are rather inefficient, with the best algorithm running in time $$O(n^4)$$ and requiring $$O(n^3)$$ memory. We present a greedy algorithm that approximates the optimum solution within a factor of 2 and show that our analysis is tight. Our algorithm runs in time $$O(n^2 \log n)$$ and needs only O( n) memory. In fact, the running time is $$O(n (g^*+1)\log n)$$ , where $$g^*$$ is the minimum number of gaps. [ABSTRACT FROM AUTHOR]

The search and detection of the different regions constituting an image is a problem of great complexity and the use of the approximation algorithms is inevitable. For this purpose, several algorithms have been applied. Among the latter, we are interested in bio-inspiration by hybridizing two algorithms: Artificial Immunity Systems (AIS) with Evolutionary Algorithms (AE) in order to benefit from the good codification of the immune systems and the variation of the operators of the evolutionary algorithms, ensuring that the entire population is the solution. The main interests of this hybridization are to minimize the size of the representation of the individuals and to accelerate the convergence. [ABSTRACT FROM AUTHOR]

A total dominating set of an undirected graph G = ( V , E ) is a set S ⊆ V of vertices such that each vertex of G is adjacent to at least one vertex of S . A secure total dominating set of G is a set D ⊆ V of vertices such that D is a total dominating set of G and each vertex v ∈ V ∖ D is adjacent to at least one vertex u ∈ D with the property that the set ( D ∖ { u } ) ∪ { v } is a total dominating set of G . The secure total domination number γ s t ( G ) of G is the minimum cardinality of a secure total dominating set of G . We establish bounds on the secure total domination number. In particular, we show that every graph G with no isolated vertices satisfies γ s t ( G ) ≤ 2 α ( G ) , where α ( G ) is the independence number of G . Further, we study the problem of finding the secure total domination number. We show that the decision version of the problem is N P -complete for chordal bipartite graphs, planar bipartite graphs with arbitrary large girth and maximum degree 3, split graphs and graphs of separability at most 2. Finally, we show that the optimisation version of the problem can be approximated in polynomial time within a factor of c ln | V | for some constant c > 1 and cannot be approximated in polynomial time within a factor of c ′ ln | V | for some constant c ′ < 1 , unless P = N P . [ABSTRACT FROM AUTHOR]

Let $$P$$ and $$Q$$ be two simple polygons in the plane of total complexity n, each of which can be decomposed into at most k convex parts. We present a $$(1-\varepsilon )$$ -approximation algorithm, for finding the translation of $$Q$$ , which maximizes its area of overlap with $$P$$ . Our algorithm runs in $$O\left( {c n}\right) $$ time, where c is a constant that depends only on k and $$\varepsilon $$ . This suggests that for polygons that are 'close' to being convex, the problem can be solved (approximately), in near linear time. [ABSTRACT FROM AUTHOR]

The generalized bin packing problem (GBPP) is a novel packing problem arising in many transportation and logistic settings, characterized by multiple items and bins attributes and the presence of both compulsory and non-compulsory items. In this paper, we study the computational complexity and the approximability of the GBPP. We prove that the GBPP cannot be approximated by any constant, unless [ABSTRACT FROM AUTHOR]

A graph G is weakly semiregular if there are two numbers a , b , such that the degree of every vertex is a or b . The weakly semiregular number of a graph G , denoted by w r ( G ) , is the minimum number of subsets into which the edge set of G can be partitioned so that the subgraph induced by each subset is a weakly semiregular graph. We present a polynomial time algorithm to determine whether the weakly semiregular number of a given tree is two. On the other hand, we show that determining whether w r ( G ) = 2 for a given bipartite graph G with at most three numbers in its degree set is NP -complete. Among other results, for every tree T , we show that w r ( T ) ≤ 2 log 2 ⁡ Δ ( T ) + O ( 1 ) , where Δ ( T ) denotes the maximum degree of T . A graph G is a [ d , d + s ] -graph if the degree of every vertex of G lies in the interval [ d , d + s ] . A [ d , d + 1 ] -graph is said to be semiregular . The semiregular number of a graph G , denoted by s r ( G ) , is the minimum number of subsets into which the edge set of G can be partitioned so that the subgraph induced by each subset is a semiregular graph. We prove that the semiregular number of a tree T is ⌈ Δ ( T ) 2 ⌉ . On the other hand, we show that determining whether s r ( G ) = 2 for a given bipartite graph G with Δ ( G ) ≤ 6 is NP -complete. In the second part of the work, we consider the representation number. A graph G has a representation modulo r if there exists an injective map ℓ : V ( G ) → Z r such that vertices v and u are adjacent if and only if | ℓ ( u ) − ℓ ( v ) | is relatively prime to r . The representation number , denoted by r e p ( G ) , is the smallest r such that G has a representation modulo r . Narayan and Urick conjectured that the determination of r e p ( G ) for an arbitrary graph G is a difficult problem [38] . In this work, we confirm this conjecture and show that if N P ≠ P , then for any ϵ > 0 , there is no polynomial time ( 1 − ϵ ) n 2 -approximation algorithm for the computation of representation number of regular graphs with n vertices. [ABSTRACT FROM AUTHOR]

After the successful development of the discrete cosine transform (DCT) especially in audio, image and video coding, many state-of-the-arts DCT-based fast algorithms have been developed. However, these algorithms are floating-point and are implemented with high algorithmic complexity and memory intensive. Therefore, they consume large system resources. In particular, those requirements pose a serious limitation on multimedia applications in resource-constrained systems, such as wireless multimedia sensor networks (WMSNs). In this paper we investigate an alternative to DCT transform which known as discrete Tchebichef transform (DTT). Despite its good energy compaction property, low algorithmic complexity and low memory requirements, the DTT is potentially unexploited in the literature. To further reduce its complexity and memory requirements, in this paper we propose a pruned version of DTT (P-DTT). Simulation results show that P-DTT requires a reduced number of arithmetic operations, energy consumption and memory. And it has at the same time competitive compression efficiency compared with Loeffler-DCT and exact DTT. The proposed P-DTT transform is a viable option for image compression and/or communication over WMSNs. [ABSTRACT FROM AUTHOR]

Partial words are sequences of characters from an alphabet in which some positions may be marked with a "hole" symbol, ⋄. We can create a ⋄-substitution mapping this symbol to a subset of the alphabet, so that applying such a substitution to a partial word results in a set of total words (ones without holes). This setup allows us to compress regular languages into smaller partial languages. Deterministic finite automata for such partial languages, referred to as ⋄-DFAs, employ a limited nondeterminism that can allow them to have lower state complexity than the minimal DFAs for the corresponding total languages. Our paper focuses on algorithms for the construction of minimal partial languages, associated with some ⋄-substitution, as well as approximation algorithms for the construction of minimal ⋄-DFAs. [ABSTRACT FROM AUTHOR]

We solve a sum rate maximization problem of full-duplex (FD) multiuser multiple-input–multiple-output (MU-MIMO) systems. Since additional self-interference (SI) in the uplink channel and cochannel interference (CCI) in the downlink channel are coupled in FD communication, the downlink and uplink multiuser beamforming vectors are required to be jointly designed. However, the joint optimization problem is nonconvex and difficult to solve due to the coupled effect. To properly address the coupled design issue, we reformulate the problem into an equivalent uplink channel problem by using the uplink and downlink channel duality known as multiple-access channel–broadcast channel duality (MAC–BC duality). Then, using a minorization–maximization (MM) algorithm based on an affine approximation, we obtain a solution for the reformulated problem. In addition, without any approximation and thus performance degradation, we develop an alternative algorithm based on iterative water filling (IWF) to solve the nonconvex problem. The proposed algorithms warrant fast convergence and low computational complexity. [ABSTRACT FROM PUBLISHER]

We introduce an adaptive scattered data fitting scheme as extension of local least squares approximations to hierarchical spline spaces. To efficiently deal with non-trivial data configurations, the local solutions are described in terms of (variable degree) polynomial approximations according not only to the number of data points locally available, but also to the smallest singular value of the local collocation matrices. These local approximations are subsequently combined without the need of additional computations with the construction of hierarchical quasi-interpolants described in terms of truncated hierarchical B-splines. A selection of numerical experiments shows the effectivity of our approach for the approximation of real scattered data sets describing different terrain configurations. [ABSTRACT FROM AUTHOR]

This paper provides an enhanced method focused on reducing the computational complexity of function approximation problems by dividing the input data vectors into small groups, which avoids the curse of dimensionality. The computational complexity and memory requirements of the approximated problem are higher when the input data dimensionality increases. A divide-and-conquer algorithm is used to distribute the input data of the complex problem to a divided radial basis function neural network (Div-RBFNN). Under this algorithm, the input data variables are typically distributed to different RBFNNs based on whether the number of the input data dimensions is odd or even. In this paper, each Div-RBFNN will be executed independently and the resulting outputs of all Div-RBFNNs will be grouped using a system of linear combination function. The parameters of each Div-RBFNN (centers, radii, and weights) will be optimized using an efficient learning algorithm, which depends on an enhanced clustering algorithm for function approximation, which clusters the centers of the RBFs. Compared to traditional RBFNNs, the proposed methodology reduces the number of executing parameters. It further outperforms traditional RBFNNs not only with respect to the execution time but also in terms of the number of executing parameters of the system, which produces better approximation error. [ABSTRACT FROM AUTHOR]

Advances in research on quality metrics for bounding volume hierarchies (BVHs) have shown that greedy top-down SAH builders construct BVHs with superior traversal performance despite the fact that the resulting SAH values are higher than those created by more sophisticated builders. Motivated by this observation we examine three construction algorithms that use recursive SAH values of temporarily constructed SAH-built BVHs to guide the construction and perform an extensive evaluation. The resulting BVHs achieve up to 37% better trace performance for primary rays and up to 32% better trace performance for secondary diffuse rays compared to standard plane sweeping without applying spatial splits. Allowing spatial splits still achieves up to 18% resp. 15% better performance. While our approach is not suitable for real-time BVH construction, we show that the proposed algorithm has subquadratic computational complexity in the number of primitives, which renders it usable in practical applications. Additionally, we describe an approach for improving the forecasting abilities of the SAH-EPO ray tracing performance predictor which also increases its relevance for primary rays. [ABSTRACT FROM AUTHOR]

In this work, we propose a combinative strategy based on regression and clustering for solving point set matching problems under a Bayesian framework, in which the regression estimates the transformation from the model to the sceneand the clustering establishes the correspondence between two point sets. The point set matching model is illustrated by a hierarchical directed graph, and the matching uncertainties are approximated by a coarse-to-fine variational inference algorithm. Furthermore, two Gaussian mixtures are proposed for the estimation of heteroscedastic noise and spurious outliers, and an isotropic or anisotropic covariance can be imposed on each mixture in terms of the transformed model points. The experimental results show that the proposed approach achieves comparable performance to state-of-the-art matching or registration algorithms in terms of both robustness and accuracy. [ABSTRACT FROM PUBLISHER]

We present an algorithm for resampling a function from its values on a non-Cartesian grid onto a Cartesian grid. This problem arises in many applications such as MRI, CT, radio astronomy and geophysics. Our algorithm, termed SParse Uniform ReSampling (SPURS), employs methods from modern sampling theory to achieve a small approximation error while maintaining low computational cost. The given non-Cartesian samples are projected onto a selected intermediate subspace, spanned by integer translations of a compactly supported kernel function. This produces a sparse system of equations describing the relation between the nonuniformly spaced samples and a vector of coefficients representing the projection of the signal onto the chosen subspace. This sparse system of equations can be solved efficiently using available sparse equation solvers. The result is then projected onto the subspace in which the sampled signal is known to reside. The second projection is implemented efficiently using a digital linear shift invariant (LSI) filter and produces uniformly spaced values of the signal on a Cartesian grid. The method can be iterated to improve the reconstruction results. We then apply SPURS to reconstruction of MRI data from nonuniformly spaced k-space samples. Simulations demonstrate that SPURS outperforms other reconstruction methods while maintaining a similar computational complexity over a range of sampling densities and trajectories as well as various input SNR levels. [ABSTRACT FROM PUBLISHER]

We study a variant of an abstract scheduling problem inspired by the management of reclaimers in the stockyard of a coal export terminal. We prove NP-completeness of the problem and formulate it as a mixed-integer program. We show that for a given reclaiming sequence, the problem can be solved in pseudo-polynomial time. In addition, we provide simple, constant-factor approximation algorithms as well as exact branch-and-bound algorithms. An extensive computational study analyzes the performance of the algorithms. [ABSTRACT FROM AUTHOR]

Network infections that are already in progress cause challenges to those officers trying to preserve those nodes not yet infected. Static solutions can take advantage of global knowledge of the network to produce quick and approximate answers for those members who should be vaccinated. In dynamic situations however, small changes can severely alter those static solutions making them irrelevant. Yet in dynamic situations it can not be known with certainty which small changes will affect the solution and those that will not. Computational resources are wasted recalculating a global solution for the entire network, when a local recalculation may be enough. This paper presents a dynamic node vaccination solution that seeks to take advantage of these local recalculations. [ABSTRACT FROM AUTHOR]

A data-driven algorithm recently proposed to solve the problem of model reduction by moment matching is extended to multi-input, multi-output systems. The algorithm is exploited for the model reduction of large-scale interconnected power systems and it offers, simultaneously, a low computational complexity approximation of the moments and the possibility to easily enforce constraints on the reduced order model. This advantage is used to preserve selected slow and poorly damped modes. The preservation of these modes has been shown to be important from a physical point of view and in obtaining an overall good approximation. The problem of the choice of the so-called tangential directions is also analyzed. The algorithm and the resulting reduced order model are validated with the study of the dynamic response of the NETS-NYPS benchmark system (68-Bus, 16-Machine, 5-Area) to multiple fault scenarios. [ABSTRACT FROM AUTHOR]

A new class of discretization-based look-ahead algorithms (DLAAs) for the Dubins traveling salesperson problem (DTSP) is presented that compares favorably with the existing algorithms from the literature. The discretization level and the length of the look-ahead horizon are the two parameters that uniquely determine a DLAA, and depending on the application in hand, their values can be easily modified to strike a balance between the execution time and the length of the resulting admissible tour. The time complexity of a DLAA is the sum of two terms, one linear in the number of targets (cities) and one that corresponds to the specification of an initial order for the targets. For instances of the DTSP with densely distributed targets, an algorithm that relies on clustering and leads to shorter tours than the DLAA is also presented. [ABSTRACT FROM AUTHOR]

Salient object detection is an important issue in computer vision and image procession in that it can facilitate humans to locate conspicuous visual regions in complex scenes rapidly and improve the performance of object detection and video tracking. In recent years, low-rank matrix approximation has been proved to be favorable in image saliency detection and gained a great deal of attention. An underlying assumption of low-rank recovery is that an image is a combination of background regions being low-rank and salient objects being sparse, which corresponds to tough non-smooth optimization problems. In this paper, by incorporating ℓ 2,1 -norm minimization, we obtain the corresponding smooth optimization problems and propose two effective algorithms with proved convergence. To guarantee the robustness of the proposed methods, the input image is divided into patches and each patch is approximately represented by its mean value. Besides, multi-scale visual features of each patch of the given image are extracted to capture common low-level features such as color, edge, shape and texture. The salient objects of a given image are indicated with sparse coefficients solved by the low-rank matrix approximation problem. Saliency maps are further produced with integration of the high-level prior knowledge. Finally, extensive experiments in four real-world datasets demonstrate that the proposed methods come with competitive performance over the eight compared state-of-the-arts. [ABSTRACT FROM AUTHOR]

In this article, we study a parallel machine scheduling problem with inclusive processing set restrictions and the option of job rejection. In the problem, each job is compatible to a subset of machines, and machines are linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process (but not conversely). To achieve a tight production due date, some of the jobs might be rejected at certain penalty. We first study the problem of minimizing the makespan of all accepted jobs plus the total penalty cost of all rejected jobs, where we develop a [ABSTRACT FROM AUTHOR]

We consider the m-Cycle Cover Problem of covering a complete undirected graph by m vertex-nonadjacent cycles of extremal total edge weight. The so-called TSP approach to the construction of an approximation algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the Euclidean Max m-Cycle Cover Problem with deterministic instances (edge weights) in a multidimensional Euclidean space and the Random Min m-Cycle Cover Problem with random instances UNI(0,1) are analyzed. It is shown that both algorithms have time complexity O( n ) and are asymptotically optimal for the number of covering cycles m = o( n) and $$m \leqslant \frac{{n^{1/3} }} {{\ln n}}$$ , respectively. [ABSTRACT FROM AUTHOR]

A low complexity carrier phase estimation (CPE) for 16-QAM systems is investigated in this letter. First, we propose a single-stage CPE algorithm based on the error function calculation. In this CPE algorithm, we define an error function and use the four error function values corresponding to four test phase angles ( $-\pi $ /4, $-\pi $ /8, 0, and $\pi $ /8) to directly calculate the optimal phase angle, which effectively reduces the computational complexity compared with the blind phase search algorithm. Next, we combine the proposed CPE algorithm with an improved V&V algorithm and propose a two-stage CPE algorithm, which has both advantages of good linewidth tolerance and low computational complexity. Through simulations, the effectiveness of the proposed algorithms is demonstrated in a 28-Gbaud 16-QAM coherent optical transmission system. [ABSTRACT FROM PUBLISHER]

System Operators in many countries are required to maintain contingency plans for critical N-2 contingencies. Huge number of possible N-2 contingencies makes their direct assessment computationally prohibitive forcing the operators to rely on engineering judgement or uncontrollable heuristics. We present a novel algorithm for identification of critical N-2 contingencies that result in line overloads in post-contingency equilibrium. High computational efficiency of the algorithm is achieved via effective certification of safety for the majority of contingencies. Unlike many common heuristics, the algorithm is guaranteed to have zero missing rate in DC approximation models. Performance of the algorithm is validated by simulation of several IEEE case scenarios which demonstrate 30 – 1000 fold acceleration of contingency selection process in comparison with naïve brute-force approach. Various possible applications of the approach in the problems of security assessment, transmission topology control and planning are discussed in the end of the manuscript. [ABSTRACT FROM PUBLISHER]

The energy efficiency (EE) of a multi-user multi-relay system with the maximum diversity network coding (MDNC) is studied. We explicitly find the connection among the outage probability, energy consumption, and EE, and formulate the maximizing EE problem under the outage probability constraint. Relay scheduling (RS) and power allocation (PA) are applied to schedule the relay states (transmitting, sleeping, and so on) and optimize the transmitting power under the practical channel and power consumption models. Since the optimization problem is NP hard, to reduce computational complexity, the outage probability is first tightly approximated to a log-convex form. Furthermore, the EE is converted into a subtractive form based on the fractional programming. Then, a convex mixed-integer nonlinear problem is eventually obtained. With a generalized outer approximation algorithm, RS and PA are solved in an iterative manner. The Pareto-optimal curves between the EE and the target outage probability show the EE gains from PA and RS. Moreover, by comparing with the no network coding (NoNC) scenario, we conclude that with the same number of relays, MDNC can lead to EE gains. However, if RS is implemented, NoNC can outperform MDNC in terms of the EE when more relays are needed in the MDNC scheme. [ABSTRACT FROM PUBLISHER]

Given a graph with labels defined on edges and a source-sink pair ( s , t ) , the Label s - t Cut problem asks for a minimum number of labels such that the removal of edges with these labels disconnects s and t . Similarly, the Global Label Cut problem asks for a minimum number of labels to disconnect G itself. For these two problems, we identify two useful parameters, i.e., l max , the maximum length of any s - t path (only applies to Label s - t Cut ), and f max , the maximum number of appearances of any label in the graph (applies to the two problems). We show that l max = 2 and f max = 2 are two complexity thresholds for Label s - t Cut . Furthermore, we give (i) an O ⁎ ( c k ) time parameterized algorithm for Label s - t Cut with l max bounded from above, where parameter k is the number of labels in a solution, and c is a constant with l max − 1 < c < l max , (ii) a combinatorial l max -approximation algorithm for Label s - t Cut , and (iii) a polynomial time exact algorithm for Global Label Cut with f max bounded from above. [ABSTRACT FROM AUTHOR]

Parameterized Approximation is a topic of considerable interest in the field of Parameterized Complexity. In the past decade, new color coding-related techniques, including the breakthrough representative sets technique, have been proven extremely powerful in the design of fast parameterized algorithms. Furthermore, packing problems, which are often solved via color coding-related techniques, have enjoyed a race towards obtaining the fastest parameterized algorithms that solve them. Therefore, it is natural to ask whether packing problems admit efficient parameterized approximation algorithms. In this paper, we answer this question affirmatively. We present tradeoffs that improve the running times of algorithms for well-known special cases of the 3 -Set k -Packing problem at the cost of their accuracy. Consider a packing problem for which there is no known algorithm with approximation ratio α , and a parameter k . If the value of an optimal solution is at least k , we seek a solution of value at least αk ; otherwise, we seek an arbitrary solution. Clearly, if the best known parameterized algorithm that finds a solution of value t runs in time O ⁎ ( f ( t ) ) for some function f , we are interested in running times better than O ⁎ ( f ( α k ) ) . Our main contribution lies in the adaptation of notions fundamental to the representative sets technique to the design of approximation algorithms: We introduce the definition of “approximate lopsided universal sets”, combine partial executions of representative sets-based algorithms with approximation algorithms, and adapt the iterative expansion framework (in the context of representative sets) to the design of parameterized approximation algorithms. Our ideas are intuitive, and may be relevant to the design of other parameterized approximation algorithms. [ABSTRACT FROM AUTHOR]

We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor approximation algorithm. [ABSTRACT FROM AUTHOR]

Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indices, as well as in hierarchy based knowledge representation. In this paper we focus on tree-like partial orders and consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query e returns the component of T − e containing the vertex sought for, while incurring some known cost c ( e ) . The Tree Search Problem with Non-Uniform Cost is the following: given a tree T on n vertices, each edge having an associated cost, construct a strategy that minimizes the total cost of the identification in the worst case. Finding the strategy guaranteeing the minimum possible cost is an NP-complete problem already for input trees of degree 3 or diameter 6. The best known approximation guarantee was an O ( log ⁡ n / log ⁡ log ⁡ log ⁡ n ) -approximation algorithm of Cicalese et al. (2012) [4] . We improve upon the above results both from the algorithmic and the computational complexity point of view: We provide a novel algorithm that provides an O ( log ⁡ n log ⁡ log ⁡ n ) -approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-hard even when the input tree is a spider of diameter 6, i.e., at most one vertex has degree larger than 2. [ABSTRACT FROM AUTHOR]

In this paper, we propose a strategy that is based on expectation maximization for tracking multiple point targets. The algorithm is similar to probabilistic multi-hypothesis tracking (PMHT) but does not relax the point target model assumptions. According to the point target models, a target can generate at most one measurement, and a measurement is generated by at most one target. With this model assumption, we show that the proposed algorithm can be implemented as iterations of Rauch-Tung-Striebel (RTS) smoothing for state estimation, and the loopy belief propagation method for marginal data association probabilities calculation. Using example illustrations with tracks, we compare the proposed algorithm with PMHT and joint probabilistic data association (JPDA) and show that PMHT and JPDA exhibit coalescence when there are closely moving targets whereas the proposed algorithm does not. Furthermore, extensive simulations c comparing the mean optimal subpattern assignment (MOSPA) performance of the algorithm for different scenarios averaged over several Monte Carlo iterations show that the proposed algorithm performs better than JPDA and PMHT. We also compare it to benchmarking algorithm: $N$-scan pruning based track-oriented multiple hypothesis tracking (TOMHT). The proposed algorithm shows a good tradeoff between computational complexity and the MOSPA performance. [ABSTRACT FROM PUBLISHER]

In 2011, Khattri and Abbasbandy developed an optimal two-step Jarratt-like method for approximating simple roots of a nonlinear equation. We develop their method for solving nonlinear systems of equations. The main feature of the extended methods is that it uses only one LU factorization which preserves and reduces computational complexities. Following this aim, the suggested method is generalized in such a way that we increase the order of convergence but we do not need new LU factorization. Convergence and complexity analysis are provided rigorously. Using some small and large systems, applicability along with some comparisons are illustrated. [ABSTRACT FROM AUTHOR]

Given a nondominated point set X ⊂ Rd of size n and a suitable reference point r ∈ Rd, the Hypervolume Subset Selection Problem (HSSP) consists of finding a subset of size k ≤ n that maximizes the hypervolume indicator. It arises in connection with multiobjective selection and archiving strategies, as well as Pareto-front approximation postprocessing for visualization and/or interaction with a decision maker. Efficient algorithms to solve the HSSP are available only for the 2-dimensional case, achieving a time complexity of O(n(k + log n)). In contrast, the best upper bound available for d > 2 is O(nd/2 log n + nn-k ). Since the hypervolume indicator is a monotone submodular function, the HSSP can be approximated to a factor of (1 − 1/e) using a greedy strategy. In this article, greedy O(n(k + log n))-time algorithms for the HSSP in 2 and 3 dimensions are proposed, matching the complexity of current exact algorithms for the 2-dimensional case, and considerably improving upon recent complexity results for this approximation problem. [ABSTRACT FROM AUTHOR]

This work deals with frequency-domain equalization for faster-than-Nyquist (FTN) signaling in doubly selective channels (DSCs). To handle the interference of frequency-domain symbols, the minimum mean square error (MMSE) equalizer involves high complexity in DSCs. To overcome the problem, we propose low-complexity receivers based on two variational methods, i.e., mean field (MF) and Bethe approximations. Compared with the MF method, the Bethe approximation takes into account the conditional dependencies of pairwise symbols. By only considering a small set of the frequency-domain symbols that have strong interference to each other, the complexity of the proposed algorithms increases linearly with the block length. Simulation results demonstrate that the proposed algorithms for FTN signaling are able to perform close to the MMSE equalizer in DSCs while with significantly reduced computational complexity. [ABSTRACT FROM PUBLISHER]

The fact that polynomial time algorithm is very unlikely to be devised for an optimal solving of the NP-hard problems strongly motivates both the researchers and the practitioners to try to solve such problems heuristically, by making a trade-off between computational time and solution's quality. In other words, heuristic computation consists of trying to find not the best solution but one solution which is 'close to' the optimal one in reasonable time. Among the classes of heuristic methods for NP-hard problems, the polynomial approximation algorithms aim at solving a given NP-hard problem in poly-nomial time by computing feasible solutions that are, under some predefined criterion, as near to the optimal ones as possible. The polynomial approximation theory deals with the study of such algorithms. This survey first presents and analyzes time approximation algorithms for some classical examples of NP-hard problems. Secondly, it shows how classical notions and tools of complexity theory, such as polynomial reductions, can be matched with polynomial approximation in order to devise structural results for NP-hard optimization problems. Finally, it presents a quick description of what is commonly called inapproximability results. Such results provide limits on the approximability of the problems tackled.

In this paper we establish an algorithmic framework between bin packing and strip packing, with which strip packing can be very well approximated by applying some bin packing algorithms. More precisely we obtain the following results: (1) Any off-line bin packing algorithm can be applied to strip packing maintaining almost the same asymptotic worst-case ratio. (2) A class of Harmonic-based algorithms for bin packing, such as Refined Harmonic, Modified Harmonic, Harmonic++, can be applied to online strip packing. In particular, we show that online strip packing admits an upper bound of 1.58889 + ϵ on the asymptotic competitive ratio, for any arbitrarily small ϵ > 0 . This significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed by Csirik and Woeginger (1997). Moreover, the time complexity mainly depends on a sorting procedure and the bin packing algorithms employed. [ABSTRACT FROM AUTHOR]