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]

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]

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 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]

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]

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]

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]

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 Resource Allocation Problem with Time Dependent Penalties (RAPTP) is a variant of uncapacitated resource allocation problems generally referred as uncapacitated facility allocation problems or uncapacitated facility location problem (UFLP). Work done in this paper is motivated by the work of Du, Lu and Xu [7] in which authors considered facility location problems with submodular penalties and presented a 3-approximation primal dual algorithm. This paper considers that each unallocated demand point adds to penalty that increases as time passes and is thus represented by function x (t i , p i) where t i and p i are elapse time and priority of demand point d i . As this problem has been considered for emergency service allocation, all demand points should be allocated to some facility or resource within some stipulated time limit beyond which it may lose its purpose. Thus penalty incurred by a demand point is considered till that threshold value only. Thus it is assumed that penalty contribution by a demand point remains constant after a specified threshold value. By exploiting the properties of time dependent penalties, a 4-approximation primal-dual algorithm is proposed which is based on LP framework, and is the first constant-factor approximation algorithm for RAPTP. [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]

We study the problem of maximizing non-monotone diminish return (DR)-submodular function on the bounded integer lattice, which is a generalization of submodular set function. DR-submodular functions consider the case that we can choose multiple copies for each element in the ground set. This generalization has many applications in machine learning. In this paper, we propose a 1 / 2 -approximation algorithm with a running time of O (n log B) , where n is the size of the ground set, B is the upper bound of integer lattice. Discovering important properties of DR-submodular function, we propose a fast double greedy algorithm which improves the running time. [ABSTRACT FROM AUTHOR]

Broadcasting is an information dissemination problem in a connected network in which one node, called the originator, must distribute a message to all other nodes by placing a series of calls along the communication lines of the network. In every unit of time, the informed nodes aid the originator in distributing the message. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for certain graphs like trees, unicyclic graphs, tree of cycles, necklace graphs, fully connected trees and tree of cliques. In this paper we study the broadcast problem in k-path graphs. For any originator of the k-path graph we present a (4 – ϵ)-approximation algorithm in the worst case. The algorithm gives a better approximation ratio for some large classes of k-path graphs. Moreover, our algorithm generates the optimal broadcast time for some cases. [ABSTRACT FROM AUTHOR]

The K-nearest neighbor graph (K-NNG) is a data structure used by many machine-learning algorithms. Naive computation of the K-NNG has quadratic time complexity, which in many cases is not efficient enough, producing the need for fast and accurate approximation algorithms. NN-Descent is one such algorithm that is highly efficient, but has a major drawback in that K-NNG approximations are accurate only on data of low intrinsic dimensionality. This paper represents an experimental analysis of this behavior, and investigates possible solutions. Experimental results show that there is a link between the performance of NN-Descent and the phenomenon of hubness, defined as the tendency of intrinsically high-dimensional data to contain hubs – points with large in-degrees in the K-NNG. First, we explain how the presence of the hubness phenomenon causes bad NN-Descent performance. In light of that, we propose four NN-Descent variants to alleviate the observed negative inuence of hubs. By evaluating the proposed approaches on several real and synthetic data sets, we conclude that our approaches are more accurate, but often at the cost of higher scan rates. [ABSTRACT FROM AUTHOR]

The characterization of interconnect delay metrics in terms of process variations is an important but complicated task for statistical timing analysis in today's integrated circuits (ICs). This paper presents a stochastic delay characterization framework for multicoupled interconnects in the presence of process variation. The proposed method starts with deriving the stochastic nodal equations for the RLC network that models multicoupled interconnects. By employing polynomial chaos (PC) expansion, a nonsampling-based stochastic prediction method, we further represent the voltage responses of network nodes as a series of orthogonal polynomials of random variables. During the expansion procedure, we use an adaptive approximation algorithm to reduce the number of required sampling points. We then use a stochastic collocation method to estimate the coefficients in the PC expansion model. With the voltage response determined as an expression of a multi-dimensional polynomial of random variables, the stochastic properties of the delay of multicoupled interconnects can be predicted. The proposed method not only takes into account the strong correlations among process variations, but also extracts an explicit delay representation for multicoupled interconnects in terms of process variations. Experimental results demonstrate that the delay characteristics predicted by the proposed method match well with the results by the brute-force Monte-Carlo method. Moreover, a significant speedup over the Monte-Carlo method has been achieved by the proposed delay characterization framework. [ABSTRACT FROM AUTHOR]

Given a set of points in the Euclidean plane, the Euclidean δ -minimum spanning tree (δ -MST) problem is the problem of finding a spanning tree with maximum degree no more than δ for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean δ -minimum bottleneck spanning tree (δ -MBST) problem, is the problem of finding a degree-bounded spanning tree for a set of points in the plane such that the length of the longest edge is minimum. When δ ≤ 4 , these two problems may yield disjoint sets of optimal solutions for the same set of points. In this paper, we perform computational experiments to compare the accuracies of a variety of heuristic and approximation algorithms for both these problems. We develop heuristics for these problems and compare them with existing algorithms. We also describe a new type of edge swap algorithm for these problems that outperforms all the algorithms we tested. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of finding the minimum number of searchers to sweep networks/graphs with special topological structures. Such a number is called the search number. We first study graphs, which contain only one cycle, and present a linear time algorithm to compute the vertex separation and the optimal layout of such graphs; by a linear-time transformation, we can find the search number of this kind of graphs in linear time. We also investigate graphs, in which every vertex lies on at most one cycle and each cycle contains at most three vertices of degree more than two, and we propose a linear time algorithm to compute their search number and optimal search strategy. We prove explicit formulas for the search number of the graphs obtained from complete k-ary trees by replacing vertices by cycles. We also present some results on approximation algorithms. [ABSTRACT FROM AUTHOR]

The genomic scaffold filling problem has attracted a lot of attention recently. The problem is on filling an incomplete sequence (scaffold) I into I ′ , with respect to a complete reference genome G , such that the number of common/shared adjacencies between G and I ′ is maximized. The problem is NP-complete, and admits a constant-factor approximation. However, the sequence input I is not quite practical and does not fit most of the real datasets (where a scaffold is more often given as a list of contigs). In this paper, we revisit the genomic scaffold filling problem by considering this important case when a scaffold S is given, the missing genes can only be inserted in between the contigs, and the objective is to maximize the number of common adjacencies between G and the filled genome S ′ . For this problem, we present a simple NP-completeness proof, we then present a factor-2 approximation algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider the discrete unit square cover (DUSC) problem as follows: given a set 𝒫 of n points and a set 𝒮 of m axis-aligned unit squares in ℝ 2 , the objective is (i) to check whether the union of the squares in 𝒮 covers all the points in 𝒫 , and (ii) if the answer is yes, then select a minimum cardinality subset 𝒮 ∗ ⊆ 𝒮 such that each point in 𝒫 is covered by at least one square in 𝒮 ∗ . For the DUSC problem: (i) we propose a (2 + 4 k − 2) -approximation algorithm, where k (> 2) is an integer parameter that defines a trade-off between the running time and the approximation factor of the algorithm. The running time of our proposed algorithm is O (k m k n + n log n). Our solution of the DUSC problem is based on a simple (1 + 2 k − 2) -approximation algorithm for the subproblem strip square cover (SSC) problem, where all the points in 𝒫 are lying within a horizontal strip of unit height. (ii) we also propose a 2-approximation algorithm, which runs in O (m 4 n) time. The 2-approximation algorithm is based on an algorithm for the subproblem SSC problem. The algorithm for the subproblem is developed using plane sweep and graph search traversal techniques. We also extend this algorithm to get 2-approximation result for the weighted DUSC problem where the squares are assigned weights, and the aim is to choose a subset 𝒮 ∗ ⊆ 𝒮 such that each point in 𝒫 is covered by at least one square in 𝒮 ∗ and the sum of the weights of squares in 𝒮 ∗ is minimized. [ABSTRACT FROM AUTHOR]

We propose a new, low-complexity solution to realize multi-input-bit gates acting on exponentially large superpositions in noise-based logic processors. Two examples are shown, the NOT gate and the CNOT gate. The operations can be executed and repeated with polynomial time and hardware complexity. The lack of a solution for this problem had been one of the major issues prohibiting the efficient realization of Shor’s algorithm by Instantaneous Noise-Based Logic, which runs on a classical Turing computer with a true random number generator. With the method described in this paper, we are one step closer to this goal. [ABSTRACT FROM AUTHOR]

In the past decades, there has been a burst of activity to simplify implementation of complex software systems. The solution framework in software engineering community for this problem is called component-based software design (CBSD), whereas in the modeling and simulation community it is called composability. Composability is a complex feature due to the challenges of creating components, selecting combinations of components, and integrating the selected components. In this paper, we address the challenge through the analysis of Component Selection (CS), the NP-complete process of selecting a minimal set of components to satisfy a set of objectives. Due to the computational complexity of CS, we consider approximation algorithms that make the component selection process practical. We define three variations of CS and present good approximation algorithms to find near optimal solutions. In spite of our creation of approximable variants of Component Selection, we prove that the general Component Selection problem is inapproximable. [ABSTRACT FROM AUTHOR]

In a sweep-coverage problem, each point of interest should be visited at least once by some mobile sensor every required time interval. Because of energy constraint, each mobile sensor has to visit a base station for replenishment before running out of its power. We model the problem as a distance constraint sweep-coverage problem the goal of which is to minimize the sum of the number of mobile sensors and the number of base stations used to meet the requirements. This paper presents an approximation algorithm with a guaranteed approximation ratio 7. [ABSTRACT FROM AUTHOR]

Aiming at optimizing polymer flooding, we establish an optimal control model of polymer flooding, which has an objective function of the net present value (NPV) involving the effect of polymer injection. An improved Monte Carlo gradient approximation (MCGA) algorithm, based on the idea of the ensemble-based optimization (EnOpt) scheme to solve the problem of strongly fluctuating perturbation gradients, is proposed by introducing the covariance matrix of the control vectors to filter and smooth the searching direction. A synthetic heterogeneous reservoir model is built to test the performance of the algorithms including the improved MCGA, standard MCGA and finite difference stochastic approximation (FDSA) algorithm. For the results, the improved MCGA gets closer to the optimal NPV of FDSA than the standard algorithm, and shows the high efficiency of saving calculation time compared with the FDSA. The value of NPV increases more than 20% for the improved algorithm, and the optimal production rates, injection rates, polymer concentrations, polymer slug sizes are obtained simultaneously. This paper subsequently discusses the influence of different time step sizes and oil prices. It can be concluded that moderate step size and relatively low oil price are applicable. Finally, an actual block application of the improved MCGA shows a 11.3% increase of NPV and a 6.5% increase of field oil production total (FOPT), showing the feasibility in optimizing real reservoirs. [ABSTRACT FROM AUTHOR]

We consider the problem of sorting signed permutations by reversals, transpositions, transreversals, and block-interchanges. The problem arises in the study of species evolution via large-scale genome rearrangement operations. Recently, Hao et al. gave a 2-approximation scheme called genome sorting by bridges (GSB) for solving this problem. Their result extended and unified the results of (i) He and Chen - a 2-approximation algorithm allowing reversals, transpositions, and block-interchanges (by also allowing transversals) and (ii) Hartman and Sharan - a 1.5-approximation algorithm allowing reversals, transpositions, and transversals (by also allowing block-interchanges). The GSB result is based on introduction of three bridge structures in the breakpoint graph, the L-bridge, T-bridge, and X-bridge that models goodreversal, transposition/transreversal, and block-interchange, respectively. However, the paper by Hao et al. focused on proving the 2-approximation GSB scheme and only mention a straightforward algorithm. In this paper, we give an algorithm for implementing the GSB scheme. The key idea behind our faster GSB algorithm is to represent cycles in the breakpoint graph by their canonical sequences, which greatly simplifies the search for these bridge structures. We also give some comparison results (running time and computed distances) against the original GSB implementation. [ABSTRACT FROM AUTHOR]

Lip segmentation is one of critical steps in a lip-reading system, because it closely relates to the accuracy of system recognition. In this paper, we aim to improve the accuracy of lip segmentation. A novel color space is proposed which consists of the component in the CIE-LUV space and the sum of 2 and 3 components of the image after discrete Hartley transform (DHT). We select a rhombus as the initial contour as its shape is approximate to a closed lip shape relatively. These notions are achieved based on the method of the Active contour model. The active contour model (ACM) is performed by the Chan-Vese model, and the result of each component is gained separately. Finally, the ultimate results are obtained by merging the result of each component together. Through experiments we can get a conclusion that this method can get more accurate and smoother lip contour. Meanwhile, the proposed method is more efficient compared with the classic ACM because it avoids some problems in the classic active contour model, like the radius of the initial contour needs to be set manually according to the size of images. [ABSTRACT FROM AUTHOR]

Scale-free networks have several favorable properties as the topology of interconnection networks such as the short diameter and the quick message propagation. In this paper, we propose a method to construct scale-free networks in a semi-deterministic manner. The proposed algorithm extends the Bulut's algorithm for constructing scale-free networks with designated minimum degree k and maximum degree m, in such a way that: (1) it determines the ideal number of edges derived from the ideal degree distribution; and (2) after connecting each new node to k existing nodes as in the Bulut's algorithm, it adjusts the number of edges to the ideal value by conducting add/removal of edges. We prove that such an adjustment is always possible if the number of nodes in the network exceeds . The performance of the algorithm is experimentally evaluated. [ABSTRACT FROM AUTHOR]

More and more parallel computing platforms are built upon hybrid architectures combining multi-core processors (CPUs) and hardware accelerators like General Purpose Graphics Processing Units (GPGPUs). We present in this paper a new method for scheduling efficiently parallel applications with CPUs and GPGPUs, where each task of the application can be processed either on an usual core (CPU) or on a GPGPU. We consider the problem of scheduling independent tasks with the objective to minimize the time for completing the whole application (makespan). This problem is NP-hard, thus, we present two families of approximation algorithms that can achieve approximation ratios of or for any integer when only one GPGPU is considered, and or for GPGPUs, where is an arbitrary small value which corresponds to the target accuracy of a binary search. The proposed method is based on a dual approximation scheme that uses a dynamic programming algorithm. The associated computational costs are for the first (resp. second) family in (resp. ) per step of dual approximation. The greater the value of parameter , the better the approximation, but the more expensive the computational cost. Finally, we propose a relaxed version of the algorithm which achieves a running time in with a constant approximation bound of . This last result is compared to the state-of-the-art algorithm HEFT. The proposed solving method is the first general purpose algorithm for scheduling on hybrid machines with a theoretical performance guarantee that can be used for practical purposes. [ABSTRACT FROM AUTHOR]

In literature the references to EM estimation of product mixtures are not very frequent. The simplifying assumption of product components, e.g. diagonal covariance matrices in case of Gaussian mixtures, is usually considered only as a compromise because of some computational constraints or limited dataset. We have found that the product mixtures are rarely used intentionally as a preferable approximating tool. Probably, most practitioners do not 'trust' the product components because of their formal similarity to 'naive Bayes models.' Another reason could be an unrecognized numerical instability of EM algorithm in multidimensional spaces. In this paper we recall that the product mixture model does not imply the assumption of independence of variables. It is even not restrictive if the number of components is large enough. In addition, the product components increase numerical stability of the standard EM algorithm, simplify the EM iterations and have some other important advantages. We discuss and explain the implementation details of EM algorithm and summarize our experience in estimating product mixtures. Finally we illustrate the wide applicability of product mixtures in pattern recognition and in other fields. [ABSTRACT FROM AUTHOR]

In the strongly connected spanning subgraph () problem, the goal is to find a minimum weight spanning subgraph of a strongly connected directed graph that maintains the strong connectivity. In this paper, we consider the problem for two families of geometric directed graphs; -spanners and symmetric disk graphs. Given a constant , a directed graph is a -spanner of a set of points if, for every two points and in , there exists a directed path from to in of length at most , where is the Euclidean distance between and . Given a set of points in the plane such that each point has a radius , the symmetric disk graph of is a directed graph , such that . Thus, if there exists a directed edge , then exists as well. We present and approximation algorithms for the problem for -spanners and for symmetric disk graphs, respectively. Actually, our approach achieves a -approximation algorithm for all directed graphs satisfying the property that, for every two nodes and , the ratio between the shortest paths, from to and from to in the graph, is at most . [ABSTRACT FROM AUTHOR]

Some interesting combinatorial problems have been motivated by genome rearrangements, which are mutations that affect large portions of a genome. When we represent genomes as permutations, the goal is to transform a given permutation into the identity permutation with the minimum number of rearrangements. When they affect segments from the beginning (respectively end) of the permutation, they are called prefix (respectively suffix) rearrangements. This paper presents results for rearrangement problems that involve prefix and suffix versions of reversals and transpositions considering unsigned and signed permutations. We give 2-approximation and ()-approximation algorithms for these problems, where is a constant divided by the number of breakpoints (pairs of consecutive elements that should not be consecutive in the identity permutation) in the input permutation. We also give bounds for the diameters concerning these problems and provide ways of improving the practical results of our algorithms. [ABSTRACT FROM AUTHOR]

This paper discusses a new approach to use a specially constructed social relation graph with high homophily to select a survey respondent group under a limited budget such that the result of the survey is biased to the minority opinions. This approach has a wide range of potential applications, e.g., collecting diversified complaints from the customers while most of them are satisfied, but is hardly investigated. We formulate the problem of computing such a group as the -biased-representative selection problem (-BRSP), where represents the size of the group constraint by the available budget. This problem has two independent optimization goals and therefore is difficult to deal with. We introduce two polynomial time algorithms for the problem, where each of which has an approximation ratio with respect to each of the objectives when the other optimization objective is substituted with a constraint. Under the substituted constraint, we prove that the first algorithm is an -approximation (which is best possible) algorithm with respect to the first objective and the second algorithm is a 2-approximation (which is best possible) with respect to the second objective, where is the degree of the input social relation graph. [ABSTRACT FROM AUTHOR]

Online social relationships which can be extracted from various online resources such as online social networks are getting much attention from the research communities since they are rich resources to learn about the members of our society as well as the relationships among them. With the advances of Internet related technologies, online surveys are established as an essential tool for a wide range of applications. One significant issue of online survey is how to select a quality respondent group so that the survey result is reliable. This paper studies the use of pairwise online social relationships among the members of a society to form a biased survey respondent group, which might be useful for various applications. We first introduce a way to construct a homophily-high social relation graph. Then, we introduce the minimum inverse k-core dominating set problem (MIkCDSP), which aims to compute a biased respondent group using the homophily-high social relation graph. We show the problem is NP-hard and most importantly propose a greedy approximation for it. Our simulation based on a real social network shows the proposed algorithm is very effective. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem), the goal is to minimize the total length of tours that cover all points in P, such that each tour starts and ends in O and covers at most k points from P. The k-tour cover problem is known to be $\mathcal{N}\mathcal{P}$-hard. It is also known to admit constant factor approximation algorithms for all values of k and even a polynomial-time approximation scheme (PTAS) for small values of k, k = Ø(log n/log log n). In this paper, we significantly enlarge the set of values of k for which a PTAS is provable. We present a new PTAS for all values of k ≤ 2logδ n, where δ = δ(ε). The main technical result proved in the paper is a novel reduction of the k-tour cover problem with a set of n points to a small set of instances of the problem, each with Ø((k/ε)Ø(1)) points. [ABSTRACT FROM AUTHOR]

This paper studies the problem of orienting all edges of a weighted graph such that the maximum weighted outdegree of vertices is minimized. This problem, which has applications in the guard arrangement for example, can be shown to be $\mathcal{NP}$-hard generally. In this paper we first give optimal orientation algorithms which run in polynomial time for the following special cases: (i) the input is an unweighted graph, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a simple, combinatorial, $\min \{\frac{w_{max}}{w_{min}},(2 - \varepsilon)\}$-approximation algorithm for the general case, where wmax and wmin are the maximum and the minimum weights of edges, respectively, and ε is some small positive real number that depends on the input. [ABSTRACT FROM AUTHOR]

Outlier detection is a difficult problem due to its time complexity being quadratic or cube in most cases, which makes it necessary to develop corresponding acceleration algorithms. Since the index structure (c.f. R tree) is used in the main acceleration algorithms, those approaches deteriorate when the dimensionality increases. In this paper, an approach named VBOD (vibration-based outlier detection) is proposed, in which the main variants assess the vibration. Since the basic model and approximation algorithm FASTVBOD do not need to compute the index structure, their performances are less sensitive to increasing dimensions than traditional approaches. The basic model of this approach has only quadratic time complexity. Furthermore, accelerated algorithms decrease time complexity to . The fact that this approach does not rely on any parameter selection is another advantage. FASTVBOD was compared with other state-of-the-art algorithms, and it performed much better than other methods especially on high dimensional data. [ABSTRACT FROM AUTHOR]

At a container port, container vessels are served by quay cranes for loading and unloading containers. Each vessel is typically split into bays from head to tail where containers are stored. Parallel quay cranes can process different bays simultaneously, and their processing efficiency significantly affects the turn-around time of a container vessel. Sharing a single traveling rail, the quay cranes cannot crossover each other, and this phenomenon is referred as the non-crossing constraint. In addition, the quay cranes may have different processing speeds due to gradual equipment updates. Inspired by updating activities of cranes in modern container terminals, this paper studies a scheduling problem with two uniform quay cranes, aiming at minimizing the turn-around time of a vessel, i.e., the makespan. We mainly develop an integrated approximation algorithm which is -approximation, where the two quay cranes are of processing speeds 1 and , respectively. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of gathering information in a gateway in a radio mesh access network. Due to interferences, calls (transmissions) cannot be performed simultaneously. This leads us to define a round as a set of non-interfering calls. Following the work of Klasing, Morales and Pérennes, we model the problem as a Round Weighting Problem (RWP) in which the objective is to minimize the overall period of non-interfering calls activations (total number of rounds) providing enough capacity to satisfy the throughput demand of the nodes. We develop tools to obtain lower and upper bounds for general graphs. Then, more precise results are obtained considering a symmetric interference model based on distance of graphs, called the distance- interference model (the particular case corresponds to the primary node model). We apply the presented tools to get lower bounds for grids with the gateway either in the middle or in the corner. We obtain upper bounds which in most of the cases match the lower bounds, using strategies that either route the demand of a single node or route simultaneously flow from several source nodes. Therefore, we obtain exact and constructive results for grids, in particular for the case of uniform demands answering a problem asked by Klasing, Morales and Pérennes. [ABSTRACT FROM AUTHOR]

This paper presents an 8-bit configurable time-interleaved (TI) successive approximation register (SAR) analog-to-digital converter (ADC). By using a mode selection circuit, four modes of sampling rate are provided: Single channel at 333.3 MS/s, 2-channel at 666.7 MS/s, 3-channel at 1 GS/s and 6-channel at 2 GS/s. An on-chip delay-locked loop (DLL) uniformly generates six-phase clock with 20% duty cycle, and the timing errors are reduced to a tolerable range. In low sampling rate modes, the corresponding sampling switches and comparators in the idle sub-ADCs are shut down to save power consumption. Based on the 65-nm CMOS technology, the post-layout simulation results show that at 1.2 V supply, the proposed ADC consumes 8.6, 10.9, 13.1 and 19.9 mW under different modes. With an ENOB of 7.92, 7.34, 7.01 and 6.37 bit, this results in a FOM of 106.6, 100.9, 101.6 and 120.3 fJ/conversion-step respectively. [ABSTRACT FROM AUTHOR]

In geometric covering problems, the aim is to cover a set of given points using a minimum number of shapes with prescribed properties. These problems extend in many ways such as covering in the presence of obstacles and partial covering. Since in most cases these problems are NP-hard, researchers have developed a large number of approximation algorithms to solve them. In this paper, with a more general view on these approaches, we propose an algorithmic framework that gives an approximation algorithm for the covering problem at hand, provided that its prerequisites are satisfied. As the result, we present a general class of geometric covering problems for which one can obtain polynomial-time approximation schemes (PTASs). This class of problems involves covering point sets with bounded shapes in a space with fixed dimension. For a problem to be in this class, it must be possible to find a polynomial number of maximal shapes and it must be possible to cover all the points in a small box with a small number of shapes. Using this framework, we present two new PTASs for the problems of covering with disks in the presence of polygonal obstacles and covering with sectors (pie-shaped wedges). The first problem has never been addressed before and for the second problem, only a logarithmic approximation algorithm was known in general and a 9-approximation algorithm for wide angles. [ABSTRACT FROM AUTHOR]

In this paper, we consider the k-center problem for streaming points in ℝ d. More precisely, we consider the single-pass streaming model, where each point in the stream is allowed to be examined only once and a small amount of information can be stored in a device. Since the size of memory is much smaller than the size of the data in the streaming model, it is important to develop an algorithm whose space complexity does not depend on the number of input data. We present an approximation algorithm for k = 2 that guarantees a (2 + ε)-factor using O(d/ε) space and update time in arbitrary dimensions for any metric. We show that our algorithm can be extended to approximate an optimal k-center within factor (2 + ε) for k > 2. [ABSTRACT FROM AUTHOR]

In this paper, we consider constant factor approximation algorithms for a variant of the discrete piercing set problem for unit disks. Here a set of points P is given; the objective is to choose minimum number of points in P to pierce the unit disks centered at all the points in P. We first propose a very simple algorithm that produces 12-approximation result in O(n log n) time. Next, we improve the approximation factor to 4 and then to 3. The worst case running time of these algorithms are O(n8 log n) and O(n15 log n) respectively. Apart from the space required for storing the input, the extra work-space requirement for each of these algorithms is O(1). Finally, we propose a PTAS for the same problem. Given a positive integer k, it can produce a solution with performance ratio (1+1/k)2 in nO(k) time. [ABSTRACT FROM AUTHOR]

Phylogenetic networks are useful for visualizing evolutionary relationships between species with reticulate events such as hybridizations and horizontal gene transfers. In this paper, we consider the problem of constructing undirected phylogenetic networks that (1) are planar graphs and (2) admit embeddings in the plane where the vertices labeling all taxa are on the boundary of the network. We develop a new algorithm for constructing phylogenetic networks satisfying these constraints. First, we show that only approximate networks can be constructed for some distance matrices with at least five taxa. Then we prove that any five-point metric can be represented approximately by a planar boundary-labeled network with guaranteed fit value of 94.79. We extend the networks constructed in the proof to design an algorithm for computing planar boundary-labeled networks for any number of taxa. [ABSTRACT FROM AUTHOR]

Automatic signature segmentation from a printed document is a challenging task due to the nature of handwriting of the signatory, overlapping/touching of signature strokes with printed text, graphics, noise, etc. In this paper, we propose a two-stage approach for signature seg-mentation from a document page. In the first stage, a document is segmented into blocks and then blocks are classified into two classes: signature block and printed word block. Gradient-based features are used for block feature extraction and support vector machine classifier is used for block-wise classification. In the second stage, printed characters that may be present in isolated form or overlapped/touched with signature part are removed from signature blocks. From each of the detected signature blocks, the isolated printed characters (if exist) are re-moved using context information. To detect overlapping/touching printed stroke in a signature block, at first some hypothetical zones are detected where possible overlapping/touching may occur. Bounding box information of neighboring printed word block and local linearity of character strings near the signature blocks are used to detect hypothetical zones. Next, to detect the overlapping/touching printed strokes in hypothetical zones of a signature block, the corner points of contours obtained by Douglas and Peucker polygonal approximation algorithm and skeleton junction points are used. Finally, the touching strokes of signature are separated from text characters using the contour smoothness information near skeleton junction points. The experiment is performed in "Tobacco-800" dataset [The legacy tobacco document library (ltdl), available at http://legacy.library.ucsf.edu/, University of California, San Francisco, 2007.] and the results obtained from the experiment are promising. [ABSTRACT FROM AUTHOR]

Given a set P of n points and a set D of m unit disks on a 2-dimensional plane, the discrete unit disk cover (DUDC) problem is (i) to check whether each point in P is covered by at least one disk in D or not and (ii) if so, then find a minimum cardinality subset D* C D such that the unit disks in D* cover all the points in P. The discrete unit disk cover problem is a geometric version of the general set cover problem which is NP-hard. The general set cover problem is not approximable within c log 1|, for some constant c, but the DUDC problem was shown to admit a constant factor approximation. In this paper, we provide an algorithm with constant approximation factor 18. The running time of the proposed algorithm is O(n logn + mlogm + mn). The previous best known tractable solution for the same problem was a 22-factor approximation algorithm with running time O(m²n4). [ABSTRACT FROM AUTHOR]

The minimum latency data aggregation schedule is one of the fundamental problems in wireless sensor networks. Most existing works assumed that the transmission ranges of sensor nodes cannot be adjusted. However, sensors with adjustable transmission ranges have advantages in energy saving, reducing transmission interference and latency. In this paper, we study the minimum latency conflict-aware data aggregation scheduling problem with adjustable transmission radii: given locations of sensors along with a base station, all sensors could adjust their transmission radii and each sensor's interference radius is α times of its transmission radius, we try to find a data aggregation schedule in which the data from all sensors can be transmitted to the base station without conflicts, such that the latency is minimized. We first partition the set of all nodes into two parts: the major set and the minor set. Then, we design different scheduling strategies for the two sets, respectively. Finally, we propose an approximation algorithm for the problem and prove the performance ratio of the algorithm is bounded by a nearly constant. Our experimental results evaluate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]