Search

Abstract It is well-known that every non-negative univariate real polynomial can be written as the sum of two polynomial squares with real coefficients. When one allows a (non-negatively) weighted sum of finitely many squares instead of a sum of two squares, then one can choose all coefficients in the representation to lie in the field generated by the coefficients of the polynomial. In particular, this allows for an effective treatment of polynomials with rational coefficients. In this article, we describe, analyze and compare, from both the theoretical and practical points of view, two algorithms computing such a weighted sum of squares decomposition for univariate polynomials with rational coefficients. The first algorithm, due to the third author, relies on real root isolation, quadratic approximations of positive polynomials and square-free decomposition, but its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm. They are exponential in the degree of the input univariate polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using quantifier elimination and root isolation bounds. The second algorithm, due to Chevillard, Harrison, Joldes and Lauter, relies on complex root isolation and square-free decomposition, and was introduced for certifying positiveness of polynomials in the context of computer arithmetic. Again, its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm, which are polynomial in the degree of the input polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using Vieta's formula and root isolation bounds. Finally, we report on our implementations of both algorithms and compare them in practice on several application benchmarks. While the second algorithm is, as expected from the complexity result, more efficient on most of examples, we exhibit families of non-negative polynomials for which the first algorithm is better. [ABSTRACT FROM AUTHOR]

Let P w ( E n ; F ) be the space of all continuous n -homogeneous polynomials from a Banach space E into another F , that are weakly continuous on bounded sets. We give sufficient conditions for the weak sequential completeness of P w ( E n ; F ) . These sufficient conditions are also necessary if both E ⁎ and F have the bounded compact approximation property. We also show that the weak sequential completeness and the reflexivity of P w ( E n ; F ) are equivalent whenever both E and F are reflexive. [ABSTRACT FROM AUTHOR]

Abstract: We study -variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For the absolute error criterion, we obtain the necessary and sufficient conditions in terms of the eigenvalues of its covariance operator and obtain an estimate of the exponent of quasi-polynomial tractability which cannot be improved in general. For the linear tensor product problems, we find that the quasi-polynomial tractability is equivalent to the strong polynomial tractability. For the normalized error criterion, we solve a problem related to the Korobov kernels, which is left open in Lifshits et al. (2012). [Copyright &y& Elsevier]

Abstract: We consider the problem of computing the permanent of a n by n matrix. For a class of matrices corresponding to constant degree expanders we construct a deterministic polynomial time approximation algorithm to within a multiplicative factor , for arbitrary . This is an improvement over the best known approximation factor obtained in Linial, Samorodnitsky and Wigderson (2000) , though the latter result was established for arbitrary non-negative matrices. Our results use a recently developed deterministic approximation algorithm for counting partial matchings of a graph (Bayati, Gamarnik, Katz, Nair and Tetali (2007) ) and Jerrum–Vazirani method (Jerrum and Vazirani (1996) ) of approximating permanent by near perfect matchings. [ABSTRACT FROM AUTHOR]

Abstract: This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires time and space, where is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires time and space, and the presented approximation scheme requires time and space, where ϵ is the given approximation parameter and M is the length of the longest path in an optimal solution. [ABSTRACT FROM AUTHOR]

Abstract: We give a trichotomy theorem for the complexity of approximately counting the number of satisfying assignments of a Boolean CSP instance. Such problems are parameterised by a constraint language specifying the relations that may be used in constraints. If every relation in the constraint language is affine then the number of satisfying assignments can be exactly counted in polynomial time. Otherwise, if every relation in the constraint language is in the co-clone from Post''s lattice, then the problem of counting satisfying assignments is complete with respect to approximation-preserving reductions for the complexity class . This means that the problem of approximately counting satisfying assignments of such a CSP instance is equivalent in complexity to several other known counting problems, including the problem of approximately counting the number of independent sets in a bipartite graph. For every other fixed constraint language, the problem is complete for #P with respect to approximation-preserving reductions, meaning that there is no fully polynomial randomised approximation scheme for counting satisfying assignments unless NP=RP. [Copyright &y& Elsevier]

Abstract: We develop an algorithmically useful refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P). This characterization finds applications in new polynomial-time approximation algorithms and fixed-parameter tractability results for the NP-hard problem to delete a minimum number of rows or columns from a 0/1-matrix such that the remaining submatrix has the C1P. [Copyright &y& Elsevier]

Abstract: We present a new hardness of approximation result for the Shortest Vector Problem in norm (denoted by ). Assuming NP ZPP, we show that for every , there is a constant such that for all integers , the problem has no polynomial time approximation algorithm with approximation ratio . [Copyright &y& Elsevier]

Abstract: The main result of this paper is an approximation algorithm for the weighted region optimal path problem. In this problem, a point robot moves in a planar space composed of n triangular regions, each of which is associated with a positive unit weight. The objective is to find, for given source and destination points s and t, a path from s to t with the minimum weighted length. Our algorithm, BUSHWHACK, adopts a traditional approach (see [M. Lanthier, A. Maheshwari, J.-R. Sack, Approximating weighted shortest paths on polyhedral surfaces, in: Proceedings of the 13th Annual ACM Symposium on Coputational Geometry, 1997, pp. 274–283; L. Aleksandrov, M. Lanthier, A. Maheshwari, J.-R. Sack, An ɛ-approximation algorithm for weighted shortest paths on polyhedral surfaces, in: Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, in: Lecture Notes in Comput. Sci., vol. 1432, 1998, pp. 11–22; L. Aleksandrov, A. Maheshwari, J.-R. Sack, Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286–295]) that converts the original continuous geometric search space into a discrete graph by placing representative points on boundary edges. However, by exploiting geometric structures that we call intervals, BUSHWHACK computes an approximate optimal path more efficiently as it accesses only a sparse subgraph of . Combined with the logarithmic discretization scheme introduced by Aleksandrov et al. [Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286–295], BUSHWHACK can compute an ɛ-approximation in time. By reducing complexity dependency on ɛ, this result improves on all previous results with the same discretization approach. We also provide an improvement over the discretization scheme of [L. Aleksandrov, A. Maheshwari, J.-R. Sack, Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286–295] so that the size of is no longer dependent on unit weight ratio, the ratio between the maximum and minimum unit weights. This leads to the first ɛ-approximation algorithm whose time complexity does not depend on unit weight ratio. [Copyright &y& Elsevier]

Let P be an optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A,n) is the maximum real q such that the solution x(I) obtained by A for any instance I of P of size n is not worse than at least a fraction q of the feasible solutions of I. We describe a deterministic, polynomial-time algorithm with domination ratio 1−o(1) for the partition problem, and a deterministic, polynomial-time algorithm with domination ratio Ω(1) for the MaxCut problem and for some far-reaching extensions of it, including Max-r-Sat, for each fixed r. The techniques combine combinatorial and probabilistic methods with tools from harmonic analysis. [Copyright &y& Elsevier]

The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices {si,ti} of G, find a minimum set of edges of G whose removal disconnects each si from the corresponding ti. Multicut is known to be NP-hard and Max SNP-hard even when the input graph is restricted to being a tree. The main result of the paper is a polynomial-time approximation scheme (PTAS) for Multicut in unweighted graphs with bounded degree and bounded tree-width. That is, for any ∊>0, we present a polynomial-time (1+∊)-approximation algorithm. In the particular case when the input is a bounded-degree tree, we have a linear-time implementation of the algorithm. We also provide some hardness results: we prove that Multicut is still NP-hard for binary trees and that it is Max SNP-hard if we drop any of the three conditions (unweighted, bounded-degree, bounded tree-width). Finally we show that some of these results extend to the vertex version of Multicut and to a directed version of Multicut. [Copyright &y& Elsevier]

Let G be an undirected graph with nonnegative edge lengths. Given two vertices as sources and all vertices as destinations, we investigated the problem how to construct a spanning tree of G such that the sum of distances from sources to destinations is minimum. In the paper, we show the NP-hardness of the problem and present a polynomial time approximation scheme. For any ϵ>0, the approximation scheme finds a (1+ϵ)-approximation solution in O(n⌈1/ϵ+1⌉) time. We also generalize the approximation algorithm to the weighted case for distances that form a metric space. [Copyright &y& Elsevier]

Algorithms for finding similar, or highly conserved, regions in a group of sequences are at the core of many molecular biology problems. Assume that we are given n DNA sequences s1, …, sn. The Consensus Patterns problem, which has been widely studied in bioinformatics research, in its simplest form, asks for a region of length L in each si, and a median string s of length L so that the total Hamming distance from s to these regions is minimized. We show that the problem is NP-hard and give a polynomial time approximation scheme (PTAS) for it. We then present an efficient approximation algorithm for the consensus pattern problem under the original relative entropy measure. As an interesting application of our analysis, we further obtain a PTAS for a restricted (but still NP-hard) version of the important consensus alignment problem allowing at most constant number of gaps, each of arbitrary length, in each sequence. [Copyright &y& Elsevier]