In this paper, we propose an algorithm for enumerating all integers nonrepresentable by a given set of positive integers. We say that a positive integer n is nonrepresentable by positive integers a(0), a(1),..., a(d-1...
详细信息
In this paper, we propose an algorithm for enumerating all integers nonrepresentable by a given set of positive integers. We say that a positive integer n is nonrepresentable by positive integers a(0), a(1),..., a(d-1) if there exist no nonnegative integers x(0), x(1),..., x(d-1) such that Sigma(d-1)(i=0) x(i)a(i) = n. In this paper, we prove that the new algorithm runs in O (t(2)s) time, where t and s denote the input and output sizes, respectively;i.e. we prove that the algorithm can enumerate all the integers nonrepresentable by a given set of positive integers in amortized polynomial-time delay. (C) 2014 Elsevier B.V. All rights reserved.
Background: Protein structure comparison and classification is an effective method for exploring protein structure-function relations. This problem is computationally challenging. Many different computational approach...
详细信息
Background: Protein structure comparison and classification is an effective method for exploring protein structure-function relations. This problem is computationally challenging. Many different computational approaches for protein structure comparison apply the secondary structure elements (SSEs) representation of protein structures. Results: We study the complexity of the protein structure comparison problem based on a mixed-graph model with respect to different computational frameworks. We develop an effective approach for protein structure comparison based on a novel independent set enumeration algorithm. Our approach (named: ePC, efficient enumeration-based Protein structure Comparison) is tested for general purpose protein structure comparison as well as for specific protein examples. Compared with other graph-based approaches for protein structure comparison, the theoretical running-time O(1.47(rn)n(2)) of our approach ePC is significantly better, where n is the smaller number of SSEs of the two proteins, r is a parameter of small value. Conclusion: Through the enumeration algorithm, our approach can identify different substructures from a list of high-scoring solutions of biological interest. Our approach is flexible to conduct protein structure comparison with the SSEs in sequential and non-sequential order as well. Supplementary data of additional testing and the source of ePC will be available at http://***/.
This paper develops an enumeration algorithm for the no-wait flow shop scheduling problem with due date constraints. In this problem, waiting time is not allowed between successive operations of jobs. Plus, each job i...
详细信息
This paper develops an enumeration algorithm for the no-wait flow shop scheduling problem with due date constraints. In this problem, waiting time is not allowed between successive operations of jobs. Plus, each job is accompanied by a due date which is dealt with as a hard constraint The considered performance criterion is makespan. The problem is strongly NP-hard. In this research, a new modelling approach is developed for the problem. This new modelling technique and the resulting observations are incorporated into a new exact algorithm to solve the problem to optimality. To investigate the performance of the algorithm, a number of test problems arc solved and the results are reported. Computational results demonstrate that the developed algorithm is significantly faster than the mathematical models. (C) 2016, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.
The enumeration of all outputs of a given multivariate polynomial is a fundamental mathematical problem and is incorporated in some algebraic attacks on multivariate public key cryptosystems. For a degree-d polynomial...
详细信息
ISBN:
(纸本)9783031400025;9783031400032
The enumeration of all outputs of a given multivariate polynomial is a fundamental mathematical problem and is incorporated in some algebraic attacks on multivariate public key cryptosystems. For a degree-d polynomial in n variables over the finite field with q elements, solving the enumeration problem classically requires O ((n+d/d) . q(n)) operations. At CHES 2010, Bouillaguet et al. proposed a fast enumeration algorithm over the binary field F-2. Their proposed algorithm covers all the inputs of a given polynomial following the order of Gray codes and is completed by O(d . 2(n)) bit operations. However, to the best of our knowledge, a result achieving the equivalent efficiency in general finite fields is yet to be proposed. In this study, we propose a novel algorithm that enumerates all the outputs of a degree-d polynomial in n variables over F-q with a prime number q by O(d . q(n)) operations. The proposed algorithm is constructed by using a lexicographic order instead of Gray codes to cover all the inputs. This result can be seen as an extension of the result of Bouillaguet et al. to general finite fields and is almost optimal in terms of time complexity. We can naturally apply the proposed algorithm to the case where q is a prime power. Notably, our enumeration algorithm differs from the algorithm by Bouillaguet et al. even in the case of q = 2.
Based on the study of enumeration algorithm, the paper proposes the multi-parameter setting method in enumeration algorithm parameter values to achieve operation independence of parameters. That is: in order to achiev...
详细信息
ISBN:
(纸本)9780769547923
Based on the study of enumeration algorithm, the paper proposes the multi-parameter setting method in enumeration algorithm parameter values to achieve operation independence of parameters. That is: in order to achieve the independence of variable values, and in order to facilitate program design, if there were m variables in enumeration algorithm and each variable may have n states, the value of the n states could be set at a geometric sequence, the ratio of which is not less than m+1. Generally choose to use 1, m +1, (m +1)(2) ... (m +1) (n-1) of the geometric progression.
From social to biological networks, prior research in complex networks have demonstrated the importance of the frequency and distribution of different types of motifs to important network functions and properties. A n...
详细信息
From social to biological networks, prior research in complex networks have demonstrated the importance of the frequency and distribution of different types of motifs to important network functions and properties. A network motif (or graphlet) is defined as a small connected sub-pattern which is over-represented in a network. Network motifs have been widely applied in a wide range of applications, namely biological, social, and technical networks. The counting of the network motif involves expensive enumeration of graph sub-patterns along with the detection of graph isomorphism. In general, network motif detection algorithms are computationally expensive and often designed to operate over static networks, which is infeasible for dynamic network structures. While significant work has been conducted to improve the efficiency of motif enumeration algorithms for complex networks, it is generally accepted that for most applications where dynamic network structure is important, the use of such algorithms is very limited and often impractical. In this dissertation, we emphasize on providing an exact count of a selected set of motifs in dynamic networks. We propose, develop, and demonstrate an efficient and robust algorithmic approach to achieve fast enumeration of motif distribution based on localized changes in network structure. The proposed technique will enable the tracking of motif distributions in large scale dynamic networks. We show how our algorithm can quickly update the frequency of different network motifs in dynamic networks. Starting from an initial frequency of network motif types, the proposed algorithmic approach monitors local network changes. Then, it efficiently updates the motif distribution at run-time without requiring the re-evaluation of the complete network, thereby avoiding redundant searches. The experimental results show that our approach is successful in reducing the computational time by eliminating the overlapped sub-patterns. Run-time monit
Data envelopment analysis (DEA) models assume real-valued inputs and outputs, but on many occasions, some inputs and/or outputs can only take integer values. In these cases, using DEA models can result in misleading e...
详细信息
Data envelopment analysis (DEA) models assume real-valued inputs and outputs, but on many occasions, some inputs and/or outputs can only take integer values. In these cases, using DEA models can result in misleading efficiency assessments and inaccurate performance targets. In this paper, we propose an enumeration algorithm for computing efficiency scores and performance targets of decision-making units with integer value inputs/outputs. In the presented algorithm, we do not use any of the mixed integer linear programming (MILP) models that are used in previous studies. We show that the result of our algorithm and that of the MILP model presented in this context is the same. We also generalize our algorithm for different types of returns to scale as well as for the hybrid setting with real-valued data.
Finding, Counting, and Enumerating different structural patterns in a large graph is a fundamental task in graph mining and forms the basis of many disciplines such as social network analysis, computational epidemiolo...
详细信息
ISBN:
(纸本)9789819612413;9789819612420
Finding, Counting, and Enumerating different structural patterns in a large graph is a fundamental task in graph mining and forms the basis of many disciplines such as social network analysis, computational epidemiology, etc. Clique is one such structural pattern which is basically a subset of the vertices such that every pair of vertices in this subset is an edge in the graph. In practice, many graphs that we deal with are time-varying, i.e., the edge set of the graph is changing over time. To analyze the structural patterns of such graphs, the notion of temporal clique has been introduced. In this paper, we define the concept of alpha-Persistent Temporal Clique (alpha-PT Clique) in a binary node-attributed temporal network and propose an enumeration strategy for such cliques present in a given temporal network. The correctness of the proposed methodology has been illustrated and the complexity analysis has been done. Several experiments have been conducted with real-world temporal network datasets to illustrate the efficiency and effectiveness of the proposed solution approach. We have also demonstrated that alpha-PT Clique enumeration will be useful to choose Top-k people to be vaccinated to reduce the propagation of pandemic.
We study linear bilevel programming problems whose lower-level objective is given by a random cost vector with known distribution. We consider the case where this distribution is nonatomic, allowing to reformulate the...
详细信息
We study linear bilevel programming problems whose lower-level objective is given by a random cost vector with known distribution. We consider the case where this distribution is nonatomic, allowing to reformulate the problem of the leader using the Bayesian approach in the sense of Salas and Svensson (SIAM J Optim 33(3):2311-2340, 2023), with a decision-dependent distribution that concentrates on the vertices of the feasible set of the follower's problem. We call this a vertex-supported belief. We prove that this formulation is piecewise affine over the so-called chamber complex of the feasible set of the high-point relaxation. We propose two algorithmic approaches to solve general problems enjoying this last property. The first one is based on enumerating the vertices of the chamber complex. This approach is not scalable, but we present it as a computational baseline and for its theoretical interest. The second one is a Monte-Carlo approximation scheme based on the fact that randomly drawn points of the domain lie, with probability 1, in the interior of full-dimensional chambers, where the problem (restricted to this chamber) can be reduced to a linear program. Finally, we evaluate these methods through computational experiments showing both approaches' advantages and challenges.
In the monotone integer dualization problem, we are given two sets of vectors in an integer box such that no vector in the first set is dominated by a vector in the second. The question is to check if the two sets of ...
详细信息
In the monotone integer dualization problem, we are given two sets of vectors in an integer box such that no vector in the first set is dominated by a vector in the second. The question is to check if the two sets of vectors cover the entire integer box by upward and downward domination, respectively. It is known that the problem is (quasi-)polynomially equivalent to that of enumerating all maximal feasible solutions of a given monotone system of linear/separable/supermodular inequalities over integer vectors. The equivalence is established via showing that the dual family of minimal infeasible vectors has size bounded by a (quasi-)polynomial in the sizes of the family to be generated and the input description. Continuing in this line of work, in this paper, we consider systems of polynomial, second-order cone, and semidefinite inequalities. We give sufficient conditions under which such bounds can be established and highlight some applications.
暂无评论