Narrow Results

In this paper, we consider a set of mobile nodes, each of which moves with constant velocity. We present algorithms to determine which of these mobile nodes can be captured the soonest by a set of one or more pursuers. We use a time parameterized R-tree (TPR-tree) to index these moving points. We then develop algorithms that operate on the TPR-tree to answer three query variations: (1) a single pursuer that is faster than all of the mobile nodes, (2) a single pursuer that is slower than some of the mobile nodes and (3) multiple pursuers. Experimental results show that our algorithms are simpler and faster than other approaches to solve the problem.

Founded on the idea of subdividing the $(p-1)$-dimensional output space, a branch-and-bound algorithm for solving the sum-of-linear-ratios(SLR) problem is proposed. First, a two-stage equivalent transformation method is adopted to obtain an equivalent problem(EP) for the problem SLR. Second, by dealing with all nonlinear constraints and bilinear terms in EP and its sub-problems, a corresponding convex relaxation subproblem is obtained. Third, all redundant constraints in each convex relaxation subproblem are eliminated, which leads to a linear programming problem with smaller scale and fewer constraints. Finally, the theoretical convergence and computational complexity of the algorithm are demonstrated, and a series of numerical experiments illustrate the effectiveness and feasibility of the proposed algorithm.

The CDT subproblem, which minimizes a quadratic function over the intersection of two ellipsoids, is a classical quadratic programming problem. In this paper, we study a method of solving CDT with a positive Lagrangian duality gap. An efficient splitting algorithm is proposed for finding the global optimal solutions. A cutting plane is firstly added to divide the feasible set of CDT into two subsets, and then two new quadratic programming problems with ellipsoidal and linear constraints are generated accordingly. Using the newly developed technique — second-order cone constraints to enhance the efficiencies of the SDP relaxation-based algorithms on the two subproblems, an optimal solution of CDT can be acquired by comparing the objective values of the two subproblems. Numerical experiments show that the new algorithm outperforms the two recent SDP relaxation-based algorithms, the two-parameter eigenvalue-based algorithm and the solver Gurobi 9.5 for certain types of CDT.

We present an efficient feature selection algorithm for computer aided detection (CAD) computed tomographic (CT) colonography. The algorithm (1) determines an appropriate piecewise linear network (PLN) model by cross validation, (2) applies the orthonormal least square (OLS) procedure to the PLN model utilizing a Modified Schmidt procedure, and (3) uses a floating search algorithm to select features that minimize the output variance. The undesirable "nesting effect" is prevented by the floating search approach, and the piecewise linear OLS procedure makes this algorithm very computationally efficient because the Modified Schmidt procedure only requires one data pass during the whole searching process. The selected features are compared to those obtained by other methods, through cross validation with support vector machines (SVMs).

Propositional satisfiability (SAT) problem is fundamental to the theory of NP-completeness. Indeed, using the concept of "polynomial-time reducibility" all NP-complete problems can be polynomially reduced to SAT. Thus, any new technique for satisfiability problems will lead to general approaches for thousands of hard combinatorial problems. In this paper, we introduce the incremental propositional satisfiability problem that consists of maintaining the satisfiability of a propositional formula anytime a conjunction of new clauses is added. More precisely, the goal here is to check whether a solution to a SAT problem continues to be a solution anytime a new set of clauses is added and if not, whether the solution can be modified efficiently to satisfy the old formula and the new clauses. We will study the applicability of systematic and approximation methods for solving incremental SAT problems. The systematic method is based on the branch and bound technique while the approximation methods rely on stochastic local search and genetic algorithms. Experimental tests, conducted on randomly generated SAT instances, demonstrate the efficiency in time of the approximation methods over the branch and bound algorithm. However these approximation methods do not always guarantee the completeness of the solution returned. We show that a method we propose that uses non systematic search in a limited form together with branch and bound has the best compromise, in practice, between time and quality of the solution returned (success ratio).

The $k$-plex is a relaxation of the classical clique structure, which is usually used to characterize the cohesiveness of a subgroup in social networks. In this paper, we propose a new notion called the $k$-plex influence to depict the outward connection of a $k$-plex. The influence of a $k$-plex is defined as the number of outside vertices adjacent to the vertices of the $k$-plex. With the new notion, we can distinguish different $k$-plexes and find more pivotal subgroups in networks. We propose an exact algorithm to find the $k$-plex with the maximum influence. The algorithm implements a branch-and-bound approach, in which we integrate a novel upper bound and an effective preprocessing strategy. We conducted experiments to evaluate the performance of the algorithm and compared it with the general mixed integer linear programming approach. The results show that both the preprocessing strategy and the upper bound can effectively reduce the search space, and the proposed branch-and-bound algorithm can solve the problem in massive graphs effectively and has a significant performance advantage over the general mixed integer linear programming approach.

Due to the rapid development of algorithms and techniques that are used to deal with mixed integer nonlinear programming (MINLP) problems, many global MINLP solvers were introduced. In this paper, computational experiments were done to compare between the performances of five of these solvers. Some of these solvers do not support trigonometric functions. Therefore, piecewise linear approximation (PLA) is applied to problems having these function so the solvers can deal with these problems. Additional computational tests were performed on to show how PLA can be useful, even to some powerful global solvers.

Propositional satisfiability (SAT) problem is fundamental to the theory of NP-completeness. Indeed, using the concept of "polynomial-time reducibility" all NP-complete problems can be polynomially reduced to SAT. Thus, any new technique for satisfiability problems will lead to general approaches for thousands of hard combinatorial problems. In this paper, we introduce the incremental propositional satisfiability problem that consists of maintaining the satisfiability of a propositional formula anytime a conjunction of new clauses is added. More precisely, the goal here is to check whether a solution to a SAT problem continues to be a solution anytime a new set of clauses is added and if not, whether the solution can be modified efficiently to satisfy the old formula and the new clauses. We will study the applicability of systematic and approximation methods for solving incremental SAT problems. The systematic method is based on the branch and bound technique, whereas the approximation methods rely on stochastic local search (SLS) and genetic algorithms (GAs). A comprehensive empirical study, conducted on a wide range of randomly generated consistent SAT instances, demonstrates the efficiency in time of the approximation methods over the branch and bound algorithm. However, these approximation methods do not guarantee the completeness of the solution returned. We show that a method we propose that uses nonsystematic search in a limited form together with branch and bound has the best compromise, in practice, between time and the success ratio (percentage of instances completely solved).

Kernel density estimators are established tools in nonparametric statistics. Due to their flexibility and ease of use, these methods are popular in computer vision and pattern recognition for tasks such as object tracking in video or image segmentation. The most frequently used algorithm for finding the modes in such densities (the mean shift) is a gradient ascent rule, which converges to local maxima. We propose a novel, globally optimal branch and bound algorithm for finding the modes in kernel densities. We show in experiments on datasets up to dimension five that the branch and bound method is faster than local optimization and observe linear runtime scaling of our method with sample size. Quantitative experiments on simulated data show that our method gives statistically significantly more accurate solutions than the mean shift. The mode localization accuracy is about five times more precise than that of the mean shift for all tested parameters. Applications to color image segmentation on an established benchmark test set also show measurably improved results when using global optimization.