Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion–exclusion characterizations. We show that the Exact Satisfiability problem of size l with m clauses can be solved in time 2 ^m l ^O(1) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2 ⁿ n ^O(1) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732 ⁿ ) and exponential space. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number.     

喇叭增益的精确设计和精确计算

本文综述了作者和他人有关喇叭增益的精确设计与精确计算的理论结果,并且得出结论,举出实例。     

Coinduction for preordered algebra

We develop a combination, called hidden preordered algebra, between preordered algebra, which is an algebraic framework supporting specification and reasoning about transitions, and hidden algebra, which is the algebraic framework for behavioural specification. This combination arises naturally within the heterogeneous framework of the modern formal specification language CafeOBJ. The novel specification concept arising from this combination, and which constitutes its single unique feature, is that of behavioural transition. We extend the coinduction proof method for behavioural equivalence to coinduction for proving behavioural transitions.     

Generalised Coinduction

We introduce the λ-coiteration schema for a distributive law λ of a functor T over a functor F. Under certain conditions it can be shown to uniquely characterise functions into the carrier of a final F-coalgebra, generalising the basic coiteration schema as given by finality. The duals of primitive recursion and course-of-value iteration, which are known extensions of coiteration, arise as instances of our framework. One can furthermore obtain schemata justifying recursive specifications that involve operators such as addition of power series, regular operators on languages, or parallel and sequential composition of processes.Next, the same type of distributive law λ is used to generalise coinductive proof techniques. To this end, we introduce the notion of a λ-bisimulation relation. It specialises to what could be called bisimulation up-to-equality or bisimulation up-to-context for contexts built from operators of the type mentioned above. We state that every such relation is contained in some larger conventional bisimulation and demonstrate that this principle leads to simpler bisimilarity proofs using less complex relations.     

Hypergeometric Functions in Exact Geometric Computation

Most problems in computational geometry are algebraic. A general approach to address nonrobustness in such problems is Exact Geometric Computation (EGC). There are now general libraries that support EGC for the general programmer (e.g., Core Library, LEDA Real). Many applications require non-algebraic functions as well. In this paper, we describe how to provide non-algebraic functions in the context of other EGC capabilities. We implemented a multiprecision hypergeometric series package which can be used to evaluate common elementary math functions to an arbitrary precision. This can be achieved relatively easily using the Core Library which supports a guaranteed precision level of accuracy. We address several issues of efficiency in such a hypergeometric package: automatic error analysis, argument reduction, preprocessing of hypergeometric parameters, and precomputed constants. Some preliminary experimental results are reported.     

Rational vs. Real Computation

There have been several different approaches of investigating computation over the real numbers. Among such computable analysis seems to be the most amenable to physical realization and the most widely accepted model that can also act as a unifying framework. Computable analysis was introduced by A. Turing [1936], A. Grzegorczyk [1955], and D. Lacombe [1955]. A representation based approach to the field was then developed by C. Kreitz and K. Weihrauch [1983]. Any typical representation is based on using the rationals, a countable dense subset of the reals with finite representation, to approximate the real numbers. The purpose of this article is to investigate the transition phenomena between rational computation and the completion of such computation (in some given representation) that induces a computability concept over the reals. This gives deeper insights into the nature of real computation (and generally computation over infinite objects) and how it conceptually differs from the corresponding foundational notion of discrete computation. We have studied both the computability and the complexity-theoretic transition phenomena. The main conclusion is the finding of a conceptual gap between rational and real computation manifested, for instance, by the existence of computable rational functions whose extensions to the reals are not computable and vice versa. This gap can be attributed to two main reasons: (1) continuity and smoothness of real functions play necessary roles in their computability and complexity-theoretic properties whereas the situation is the contrary in rational computation and (2) real computation is approximate and hence robust whereas rational computation is exact and rigid. Despite these negative results, if we relax our framework to include relative computation, then we can bridge the rational-real computation gap relative to ￠2 oracles of the arithmetical hierarchy. We have shown that ￠2 is a tight bound for the rational-real computational equivalence. That is, if a continuous function over the rationals is computable, then its extension to the reals is computable relative to a ￠2 oracle; and vice versa. This result can also be considered an extension of the Shoenfield''s Limit Lemma from classical recursion theory to the computable analysis context.     

Exact Computation of Delaunay and Power Triangulations

In this paper we present a topologically correct and efficient version of the algorithm by Guibas and Stolfi (Algorithmica 7 (1992), pp. 381-413) for the exact computation of Delaunay and power triangulations in two dimensions. The algorithm avoids numerical errors and degeneracies caused by the accumulation of rounding errors in fixed length floating point arithmetic when constructing these triangulations.Most methods for computing Delaunay and power triangulations involve the calculation of two basic primitives: the INCIRCLE test and the CCW orientation test. Both primitives require the computation of the sign of a determinant. The key to our method is the exact computation of this sign and is based on an algorithm for determining the sign of the sum of a finite set of normalized floating point numbers of fixed mantissa length (machine numbers) exactly. The exact computation of the primitives allows the construction of the correct Delaunay and power triangulations. The method has been implemented and tested for the incremental construction of Delaunay and power triangulations. Tests have been conducted for different distributions of points for which non-exact algorithms may encounter difficulties, for example, slightly perturbed points on a grid or on a circle. Experimental results show that the performance of our implementation is comparable with that of a simple implementation of the incremental algorithm in single precision floating point arithmetic. For random distribution of points the exact algorithm is only 4 times slower than the inexact implementation. The algorithm is easy to implement, robust and portable as long as the input data to the algorithm remains exact.     

求图符号控制数的完全算法研究

确定图的符号控制数是NP-难度的问题。针对求解该问题的完全算法即能求得精确最优解的算法进行了研究,提出了几个启发式的限界策略,给出了两个完全算法:回溯算法和A算法。计算实验表明,针对随机产生的问题实例,用这两个算法求解时所生成的结点数目还不到其状态空间树中结点总数目的千分之五。对这两个算法也进行了比较。     

Exact Computation of Polynomial Zeros Expressible by Square Roots

In this paper we give an efficient algorithm to find symbolically correct zeros of a polynomial f ∈ R[X] which can be represented by square roots. R can be any domain if a factorization algorithm over R[X] is given, including finite rings or fields, integers, rational numbers, and finite algebraic or transcendental extensions of those. Asymptotically, the algorithm needs O(T_f(d²)) operations in R, where T_f(d) are the operations for the factorization algorithm over R[X] for a polynomial of degree d. Thus, the algorithm has polynomial running time for instance for polynomials over finite fields or the rationals. We also present a quick test for deciding whether a given polynomial has zeros expressible by square roots and describe some additional methods for special cases.     

<Emphasis Type="SmallCaps">Shrad</Emphasis>: A Language for Sequential Real Number Computation

Since Di Gianantonio [1993] introduced his semantics for exact real number computation, there has always been a struggle to maintain data abstraction and efficiency as much as possible. The interval domain model-or its variations-can be regarded as the standard setting to obtain maximum data abstraction. As for efficiency there has been much focus on sequentiality to the extent that these two terms have become almost synonymous. Escardo et al. [1998, 2004] demonstrated that there is not much one can get by sequential computation in the interval domain model. In Farjudian [2004a, 2003] we reinforced this result by exposing the limited power of (some extensions of) the sequential fragment of Real-PCF. The previous argument suggests some sort of compromise in the beauty of the model in order to keep efficiency. One way forward is to try to sacrifice single-valuedness over partial real numbers. This is exactly what we will see in designing Shrad (which originally comes from Farjudian [2004b]) where we succeed in presenting a framework for exact real number computation which satisfies the following all at the same time: 1) It is sequential. 2) Multi-valuedness over total real numbers is carefully avoided. 3) All the computable first-order functions are defined in the language (expressivity).     

Coinductive Field of Exact Real Numbers and General Corecursion

In this article we present a method to define algebraic structure (field operations) on a representation of real numbers by coinductive streams. The field operations will be given in two algorithms (homographic and quadratic algorithm) that operate on streams of Möbius maps. The algorithms can be seen as coalgebra maps on the coalgebra of streams and hence they will be formalised as general corecursive functions. We use the machinery of Coq proof assistant for coinductive types to present the formalisation.     

精确实数计算在求两条直线段交点问题中的应用

求两条直线段的交点问题是计算机图形学、计算几何、几何造型等领域的最基本问题之一。精确实数计算是指以任意精度表示实数,并能进行计算,以任意精度得到结果。给出了一种把基于LFT方法的精确实数的表示与计算应用在求两条直线段的交点问题中的算法,该算法能够以任意的精度得到两条直线段的交点。     

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

We prove that the exact versions of the domatic number problem are complete for the levels of the boolean hierarchy over NP. The domatic number problem, which arises in the area of computer networks, is the problem of partitioning a given graph into a maximum number of disjoint dominating sets. This number is called the domatic number of the graph. We prove that the problem of determining whether or not the domatic number of a given graph is exactly one of k given values is complete for BH_2k(NP), the 2kth level of the boolean hierarchy over NP. In particular, for k = 1, it is DP-complete to determine whether or not the domatic number of a given graph equals exactly a given integer. Note that DP = BH₂(NP). We obtain similar results for the exact versions of generalized dominating set problems and of the conveyor flow shop problem. Our reductions apply Wagner's conditions sufficient to prove hardness for the levels of the boolean hierarchy over NP.     

Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram

We propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT) . Constructing CVT requires to repeatedly compute Restricted Voronoi Diagram (RVD) , defined as the intersection between a 3D Voronoi diagram and an input mesh surface. Existing methods use some approximations of RVD. In this paper, we introduce an efficient algorithm that computes RVD exactly and robustly. As a consequence, we achieve better remeshing quality than approximation-based approaches, without sacrificing efficiency. Our method for RVD computation uses a simple procedure and a kd -tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity is O ( m log n ), where n is the number of seed points and m is the number of triangles of the input mesh. Fast convergence of CVT is achieved using a quasi-Newton method, which proved much faster than Lloyd's iteration. Examples are presented to demonstrate the better quality of remeshing results with our method than with the state-of-art approaches.     

Gesture-Tracking in Real Time with Dynamic Regional Range Computation

This paper presents a new approach to the range data utilization in a gesture-tracking system. The use of three-dimensional data is essential for human motion analysis; however, the speed of complete range estimation prohibits from including it in most real-time systems. This work describes a gesture-tracking system using real-time local range on-demand. The system represents a gesture-controlled interface for interactive visual exploration of large data sets. The paper describes a method performing range processing only when necessary and where necessary. Range data is processed only for non-static regions of interest. This is accomplished by a set of filters on the color, motion, and range data. The speed-up achieved is between 1.70 and 2.15. The algorithm also includes a robust skin-color segmentation insensitive to illumination changes. Selective range processing results in dynamic regional range images that contain only information needed by the system.     

A Coinduction Principle for Recursive Data Types Based on Bisimulation

The concept of bisimulation from concurrency theory is used to reason about recursively defined data types. From two strong-extensionality theorems stating that the equality (resp. inequality) relation is maximal among all bisimulations, a proof principle for the final coalgebra of an endofunctor on a category of data types (resp. domains) is obtained. As an application of the theory developed, an internal full abstraction result (in the sense of S. Abramsky and C.-H. L. Ong [Inform. and Comput.105, 159–267 (1993)] for the canonical model of the untyped call-by-valueλ-calculus is proved. Also, the operational notion of bisimulation and the denotational notion of final semantics are related by means of conditions under which both coincide.