Several well-studied classes of graphs admit structural characterizations via proper 2-cutsets which lead to polynomial-time recognition algorithms. The algorithms so far obtained for those recognition problems do not...
详细信息
Several well-studied classes of graphs admit structural characterizations via proper 2-cutsets which lead to polynomial-time recognition algorithms. The algorithms so far obtained for those recognition problems do not guarantee linear-time complexity. The bottleneck to those algorithms is the Omega(nm)-timecomplexity to fully decompose by proper 2-cutsets a graph with n vertices and m edges. In the present work, we investigate the 3-connected components of a graph and propose the use of the SPQR-tree data structure to obtain a fully decomposed graph in lineartime. As a consequence, we show that the recognition of chordless graphs and of graphs that do not contain a propeller as a subgraph can be done in lineartime, answering questions in the existing literature. (C) 2017 Elsevier B.V. All rights reserved.
Non-convex knapsack separable quadratic optimization with compact box constraints is an NP-hard problem. We present tight lower and upper bounding procedures that are computationally-efficient as the problem size grow...
详细信息
Non-convex knapsack separable quadratic optimization with compact box constraints is an NP-hard problem. We present tight lower and upper bounding procedures that are computationally-efficient as the problem size grows. The lower bound is based on Lagrangian relaxation, and it is computed in linear-time. When the bound is not an exact global solution, a worst-case bound-quality measure is developed. Moreover, the lower bounding (LB) solution is improved to construct a feasible solution, leading to an upper bound (UB) on the given problem. The UB is based on fixing the convex variables and a subset of non-convex and linear variables at the LB solution, and considering the remaining problem, which is always feasible. The UB is computable with linear-time complexity, and it is the global optimum in certain verifiable cases when the duality gap is zero. In our limited computational experiments, the UB has very small relative gap with an exact global optimum solution when there is a nonzero duality gap. Performance of the bounds is demonstrated through a broad range of randomly generated problem instances and comparisons with existing global and non-global solvers. The proposed method on these indefinite problems of extremely large size is an order of magnitude faster than the alternative solvers, including IBM's commercial software Cplex12.6.
Partitional clustering algorithms, which partition the dataset into a pre-defined number of clusters, can be broadly classified into two types: algorithms which explicitly take the number of clusters as input and algo...
详细信息
Partitional clustering algorithms, which partition the dataset into a pre-defined number of clusters, can be broadly classified into two types: algorithms which explicitly take the number of clusters as input and algorithms that take the expected size of a cluster as input. In this paper, we propose a variant of the k-means algorithm and prove that it is more efficient than standard k-means algorithms. An important contribution of this paper is the establishment of a relation between the number of clusters and the size of the clusters in a dataset through the analysis of our algorithm. We also demonstrate that the integration of this algorithm as a pre-processing step in classification algorithms reduces their running-timecomplexity. (C) 2009 Elsevier Ltd. All rights reserved.
In this paper, we provide the first provable linear-time (in terms of the number of nonzero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quad...
详细信息
In this paper, we provide the first provable linear-time (in terms of the number of nonzero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quadratic function over a quadratic constraint under some regularity condition. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 158 (2016), pp. 363-381]. However, due to the nonconvexity and noncompactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regularity condition, the optimal solution is in a compact and convex set and lower and upper bounds of the optimal value can be computed in lineartime. Using these properties, we develop a linear-time algorithm for the GTRS.
Wagner and Whitin (1958) develop an algorithm to solve the dynamic Economic Lot-Sizing Problem (ELSP), which is widely applied in inventory control, production planning, and capacity planning. The original algorithm r...
详细信息
Wagner and Whitin (1958) develop an algorithm to solve the dynamic Economic Lot-Sizing Problem (ELSP), which is widely applied in inventory control, production planning, and capacity planning. The original algorithm runs in 0(T-2) time, where T is the number of periods of the problem instance. Subsequently, other researchers develop linear-time algorithms to solve the Wagner-Whitin (WW) lot-sizing problem;examples include the ELSP and equivalent Single Machine Batch-Sizing Problem (SMBSP). This paper revisits the algorithms for the ELSP and SMBSP under WW cost structure, presents a new efficient linear-time algorithm, and compares the developed algorithm with equivalent algorithms in the literature. The developed algorithm employs a lists and stacks data structure, which is a completely different approach than that of the comparable algorithms for the ELSP and SMBSP. Analysis of the developed algorithm shows that it executes fewer different actions throughout and hence it improves execution time by a maximum of 51.40% for the ELSP and 29.03% for the SMBSP.
We study the problem of minimizing the ratio of quadratic functions with a quadratic constraint (QCRQ), which is a generation of the trust-region subproblem and covers the regularized total least square problem as a s...
详细信息
We study the problem of minimizing the ratio of quadratic functions with a quadratic constraint (QCRQ), which is a generation of the trust-region subproblem and covers the regularized total least square problem as a special case. In this paper, we carefully employ the bisection search method to solve the scaled Lagrangian dual of (QCRQ) as strong duality holds for the primal and dual problems. We show that our algorithm can globally solve the nonconvex optimization (QCRQ) in lineartime. Numerical experiments demonstrate the computational efficiency over other semidefinite programming solvers.
Inheritance graphs of object-oriented languages can be decomposed into independent subgraphs, or modules, which are inheritance graphs themselves. This paper is devoted to the study of efficient algorithms of decompos...
详细信息
Inheritance graphs of object-oriented languages can be decomposed into independent subgraphs, or modules, which are inheritance graphs themselves. This paper is devoted to the study of efficient algorithms of decomposition into modules similar to substitution decomposition algorithms. For 2-connected inheritance graphs we search for maximal modules (under inclusion), whereas we show that the significant modules of non-2-connected graphs are the biconnected components. For the 2-connected case, a method based upon a property of greedy linear extensions is proposed. However, in both cases a linear-time complexity algorithm is provided to decompose into modules. Furthermore, the algorithm can be inserted into the inheritance mechanism (such as in CLOS [14]).
Recent results on supercomputers show that beyond 65K cores, the efficiency of molecular dynamics simulations of interfacial systems decreases significantly. In this paper, we introduce a dynamic cutoff method (DCM) f...
详细信息
ISBN:
(数字)9783319201191
ISBN:
(纸本)9783319201191;9783319201184
Recent results on supercomputers show that beyond 65K cores, the efficiency of molecular dynamics simulations of interfacial systems decreases significantly. In this paper, we introduce a dynamic cutoff method (DCM) for interfacial systems of arbitrarily large size. The idea consists in adopting a cutoff-based method in which the cutoff is chosen on a particle-by-particle basis, according to the distance from the interface. Computationally, the challenge is shifted from the long-range solvers to the detection of the interfaces and to the computation of the particle-interface distances. For these tasks, we present linear-time algorithms that do not rely on global communication patterns. As a result, the DCM algorithm is suited for large systems of particles and massively parallel computers. To demonstrate its potential, we integrated DCM into the LAMMPS open-source molecular dynamics package, and simulated large liquid/vapor systems on two supercomputers: SuperMuc and JUQUEEN. In all cases, the accuracy of DCM is comparable to the traditional particle-particle particle-mesh (PPPM) algorithm, while the performance is considerably superior for large numbers of particles. For JUQUEEN, we provide timings for simulations running on the full system (458, 752 cores), and show nearly perfect strong and weak scaling.
暂无评论