最坏情况下Min-2SAT问题的上界

最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题,在求解某些组合优化问题时,将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度,因此对MinSAT问题进行研究.针对Min-2SAT问题提出算法MinSATAlg,该算法首先利用化简算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明Min-2SAT问题可在O(1.134 3m)时间内求解,对于每个变量至多出现在3个2-子句中的情况,得到最坏情况下的上界为O(1.122 5n),其中n为变量的数目.     

New closed-form bounds on the partition function

Estimating the partition function is a key but difficult computation in graphical models. One approach is to estimate tractable upper and lower bounds. The piecewise upper bound of Sutton et al. is computed by breaking the graphical model into pieces and approximating the partition function as a product of local normalizing factors for these pieces. The tree reweighted belief propagation algorithm (TRW-BP) by Wainwright et al. gives tighter upper bounds. It optimizes an upper bound expressed in terms of convex combinations of spanning trees of the graph. Recently, Globerson et al. gave a different, convergent iterative dual optimization algorithm TRW-GP for the TRW objective. However, in many practical applications, particularly those that train CRFs with many nodes, TRW-BP and TRW-GP are too slow to be practical. Without changing the algorithm, we prove that TRW-BP converges in a single iteration for associative potentials, and give a closed form for the solution it finds. The closed-form solution obviates the need for complex optimization. We use this result to develop new closed-form upper bounds for MRFs with arbitrary pairwise potentials. Being closed-form, they are much faster to compute than TRW-based bounds. We also prove similar convergence results for loopy belief propagation (LBP) and use it to obtain closed-form solutions to the LBP pseudomarginals and approximation to the partition function for associative potentials. We then use recent results proved by Wainwright et al for binary MRFs to obtain closed-form lower bounds on the partition function. We then develop novel lower bounds for arbitrary associative networks. We report on experiments with synthetic and real-world graphs. Our new upper bounds are considerably tighter than the piecewise bounds in practice. Moreover, we can compute our bounds on several graphs where TRW-BP does not converge. Our novel lower bound, in spite of being closed-form and much faster to compute, outperforms more complicated popular algorithms for computing lower bounds like mean-field on densely connected graphs by wide margins although it does worse on sparsely connected graphs like chains.     

Tight and efficient surface bounds in meshless animation

This paper presents a fast approach for computing tight surface bounds in meshless animation, and its application to collision detection. Given a high-resolution surface animated by a comparatively small number of simulation nodes, we are able to compute tight bounding volumes with a cost linear in the number of simulation nodes. Our approach extends concepts about bounds of convex sets to the meshless deformation setting, and we introduce an efficient algorithm for finding extrema of these convex sets. The extrema can be used for efficiently updating bounding volumes such as AABBs or k-DOPs, as we show in our results. The choice of particular bounding volume may depend on the complexity of the contact configurations, but in all cases we can compute surface bound orders of magnitude faster and/or tighter than with previous methods.     

An improved method for bounding stationary measures of finite Markov processes

A new method to compute bounds on stationary results of finite Markov processes in discrete or continuous time is introduced. The method extends previously published approaches using polyhedra of eigenvectors for stochastic matrices with a known lower and upper bound of their elements. Known techniques compute bounds for the elements of the stationary vector with respect to the lower bounds of the matrix elements and another set of bounds with respect to the upper bounds of matrix elements. The resulting bounds are usually not sharp, if lower and upper bounds for the elements are known. The new approach combines lower and upper bounds resulting in sharp bounds which are often much tighter than bounds computed using only one bounding value for the matrix elements.     

Efficient Computation of Iceberg Cubes by Bounding Aggregate Functions

The iceberg cubing problem is to compute the multidimensional group-by partitions that satisfy given aggregation constraints. Pruning unproductive computation for iceberg cubing when nonantimonotone constraints are present is a great challenge because the aggregate functions do not increase or decrease monotonically along the subset relationship between partitions. In this paper, we propose a novel bound prune cubing (BP-Cubing) approach for iceberg cubing with nonantimonotone aggregation constraints. Given a cube over n dimensions, an aggregate for any group-by partition can be computed from aggregates for the most specific n--dimensional partitions (MSPs). The largest and smallest aggregate values computed this way become the bounds for all partitions in the cube. We provide efficient methods to compute tight bounds for base aggregate functions and, more interestingly, arithmetic expressions thereof, from bounds of aggregates over the MSPs. Our methods produce tighter bounds than those obtained by previous approaches. We present iceberg cubing algorithms that combine bounding with efficient aggregation strategies. Our experiments on real-world and artificial benchmark data sets demonstrate that BP-Cubing algorithms achieve more effective pruning and are several times faster than state-of-the-art iceberg cubing algorithms and that BP-Cubing achieves the best performance with the top-down cubing approach.     

Upper bounds for reversible circuits based on Young subgroups

We present tighter upper bounds on the number of Toffoli gates needed in reversible circuits. Both multiple controlled Toffoli gates and mixed polarity Toffoli gates have been considered for this purpose. The calculation of the bounds is based on a synthesis approach based on Young subgroups that results in circuits using a more generalized gate library. Starting from an upper bound for this library we derive new bounds which improve the existing bound by around 77%.     

Lower bounds on precedence-constrained scheduling for parallel processors

We consider two general precedence-constrained scheduling problems that have wide applicability in the areas of parallel processing, high performance compiling, and digital system synthesis. These problems are intractable so it is important to be able to compute tight bounds on their solutions. A tight lower bound on makespan scheduling can be obtained by replacing precedence constraints with release and due dates, giving a problem that can be efficiently solved. We demonstrate that recursively applying this approach yields a bound that is provably tighter than other known bounds, and experimentally shown to achieve the optimal value at least 90.3% of the time over a synthetic benchmark.We compute the best known lower bound on weighted completion time scheduling by applying the recent discovery of a new algorithm for solving a related scheduling problem. Experiments show that this bound significantly outperforms the linear programming-based bound. We have therefore demonstrated that combinatorial algorithms can be a valuable alternative to linear programming for computing tight bounds on large scheduling problems.     

A tight upper bound on the Bayesian probability of error

In this paper, we present a new upper bound on the minimum probability of error of Bayesian decision systems for statistical pattern recognition. This new bound is continuous everywhere and is shown to be tighter than several existing bounds such as the Bhattacharyya and the Bayesian bounds. Numerical results are also presented     

Improved Frankl–Rödl Theorem and Some of Its Geometric Consequences

We substantially improve a presently known explicit exponentially growing lower bound on the chromatic number of a Euclidean space with forbidden equilateral triangle. Furthermore, we improve an exponentially growing lower bound on the chromatic number of distance graphs with large girth. These refinements are obtained by improving known upper bounds on the product of cardinalities of two families of homogeneous subsets with one forbidden cross-intersection.     

Robustness analysis with full-structured uncertainties

This paper deals with μ problems involving full-structured (rather than block-diagonal) uncertainty, i.e. uncertainty blocks where each sub-block (or element) may be an independent uncertainty. Rearranging this problem into standard (block-diagonal) form results in an explosion in the required computation, and so a number of researchers have proposed more efficient bounds, in particular those based on non-similarity scaling, for such problems. Here we show how to map such problems into reduced size standard μ problems. The standard bounds applied to the reduced size problem are then shown to be at least as accurate, and require the same computational effort, as earlier techniques, with the added bonus that the standard μ upper bound is convex. Moreover this new approach is applicable in a much more general setting, allowing one to efficiently compute both robust stability and robust performance for problems involving multiple real and complex uncertainty blocks, any number of which may be full-structured.     

TAPER: a two-step approach for all-strong-pairs correlation query in large databases

Given a user-specified minimum correlation threshold /spl theta/ and a market-basket database with N items and T transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold /spl theta/. However, when the number of items and transactions are large, the computation cost of this query can be very high. The goal of this paper is to provide computationally efficient algorithms to answer the all-strong-pairs correlation query. Indeed, we identify an upper bound of Pearson's correlation coefficient for binary variables. This upper bound is not only much cheaper to compute than Pearson's correlation coefficient, but also exhibits special monotone properties which allow pruning of many item pairs even without computing their upper bounds. A two-step all-strong-pairs correlation query (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent of or improves when the number of items is increased in data sets with Zipf-like or linear rank-support distributions. Experimental results from synthetic and real-world data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives. Finally, we demonstrate that the algorithmic ideas developed in the TAPER algorithm can be extended to efficiently compute negative correlation and uncentered Pearson's correlation coefficient.     

Finite time stability conditions for non-autonomous continuous systems

Lower and upper bounds for the quadratic cost functional of linear regulators are derived. These bounds are explicitly expressed in terms of some system parameters, arc independent of the initial conditions and are rather easy to compute. The results are based on a previous work by the authors concerning the lower bound. In this paper, the upper bound established is used to improve the lower bound, both being calculated by an iterative procedure to any degree of accuracy which is dependent on the number of iterations only.     

A fast high average-utility itemset mining with efficient tighter upper bounds and novel list structure

High-utility itemset mining is a prominent data-mining technique where the profit or weight of itemsets plays a crucial role in defining meaningful patterns. High average-utility itemset (HAUI) mining is an advancement over high-utility itemset mining, which introduces an unbiased measure called average utility to associate the utility of itemsets with their length. Several existing HAUI mining algorithms use various upper bounds such as average-utility upper bound, revised tighter upper bound, and looser upper bound to preserve pruning methods. However, these upper bounds overestimate the average-utility of itemsets and slow down the mining process. This paper presents a fast high average-utility itemset miner (FHAIM) algorithm, which uses two improved upper bounds and several efficient pruning strategies to avoid the processing of unpromising candidate itemsets. Moreover, a novel list structure named recommended average-utility list (RAUL) is presented to store the average-utility and the required information for pruning. The RAUL for an itemset can be constructed by joining the RAULs of its subsets to avoid excessive database scans. We have performed substantial experiments on various benchmark datasets to evaluate the performance of the FHAIM in comparison with two existing HAUI mining algorithms. Experimental results show that FHAIM outperforms the existing HAUI mining algorithms in terms of runtime, memory usage, join counts, and scalability.

     

A new exact maximum clique algorithm for large and massive sparse graphs

This paper describes a new very efficient branch-and-bound exact maximum clique algorithm BBMCSP, designed for large and massive sparse graphs which appear frequently in real life problems from different fields.State-of-the-art exact maximum clique algorithms encode the adjacency matrix in full but when dealing with sparse graphs some form of compression is required. The new algorithm is based on a leading bit-parallel non-sparse solver but employs a novel sparse encoding for the adjacency matrix. Moreover, it also improves on recent optimizations proposed in literature for the sparse case such as core-based bounds.Reported results show that it is several orders of magnitude better than state-of-the-art. Moreover, a number of real networks with many millions of nodes are solved in a few seconds.     

On the Incompressibility of Monotone DNFs

We prove optimal lower bounds for multilinear circuits and for monotone circuits with bounded depth. These lower bounds state that, in order to compute certain functions, these circuits need exactly as many OR gates as the respective DNFs. The proofs exploit a property of the functions that is based solely on prime implicant structure. Due to this feature, the lower bounds proved also hold for approximations of the considered functions that are similar to slice functions. Known lower bound arguments cannot handle these kinds of approximations. In order to show limitations of our approach, we prove that cliques of size n - 1 can be detected in a graph with n vertices by monotone formulas with O(log n) OR gates. Our lower bound for multilinear circuits improves a lower bound due to Borodin, Razborov and Smolensky for nondeterministic read-once branching programs computing the clique function.     

A fast algorithm for the maximum weight clique problem

We present a branch and bound method which finds a maximum weight clique in an arbitrary weighted graph. The main ingredients are a weighted coloring heuristic which simultaneously produces lower and upper bounds and a branching rule that uses the information obtained in the coloring. The algorithm performs comparable to the fastest method known so far but is much easier to implement.     

Matrix bounds of the discrete ARE solution

This paper provides new lower and upper matrix bounds of the solution to the discrete algebraic Riccati equation. The lower bound always works if the solution exists. The upper bounds are presented in terms of the solution of the discrete Lyapunov equation and its upper matrix bound. The upper bounds are always calculated if the solution of the Lyapunov equation exists. A numerical example shows that the new bounds are tighter than previous results in many cases.     

Medial Axis Isoperimetric Profiles

Recently proposed as a stable means of evaluating geometric compactness, the isoperimetric profile of a planar domain measures the minimum perimeter needed to inscribe a shape with prescribed area varying from 0 to the area of the domain. While this profile has proven valuable for evaluating properties of geographic partitions, existing algorithms for its computation rely on aggressive approximations and are still computationally expensive. In this paper, we propose a practical means of approximating the isoperimetric profile and show that for domains satisfying a “thick neck” condition, our approximation is exact. For more general domains, we show that our bound is still exact within a conservative regime and is otherwise an upper bound. Our method is based on a traversal of the medial axis which produces efficient and robust results. We compare our technique with the state-of-the-art approximation to the isoperimetric profile on a variety of domains and show significantly tighter bounds than were previously achievable.     

Tighter bounds on full access probability in fault-tolerantmultistage interconnection networks

This paper proposes a cut-based technique to compute bounds on the full access probability of an extra stage shuffle exchange network (ESEN) and a wrap-around inverse banyan network (WIBN). Note that the problem of finding an exact full access probability is known to be NP-hard. Our results obtain tighter bounds as compared to those using existing techniques. For a small size multistage interconnection network, it deviates less from the exact value. We also notice that our proposed lower bound is conservative. Further, the lower bound is important as it suggests that a network is at least this much reliable     

Analysis of time and frequency synchronization error for wireless systems using OFDM

1 Introduction The OFDM process includes the following two steps: splitting the high-rate serial bit stream into N parallel low-rate substreams, and modulating N substreams on N or-thogonal subcarriers by means of inverse fast Fourier transform (IFFT)[1―6]. Orthogonal superposition of subcarriers ensures the OFDM technique to have the higher bandwidth efficiency compared to other frequency division multiplexing[4]. Because OFDM can be arbitrarily combined with high-efficient digital m…