Search

In this paper we present an efficient framework for the evaluation of subdivision schemes with polynomial reproduction property. For all interested rational parameters between 0 and 1 with the same denominator, their exact limit positions on the subdivision curve can be obtained by solving a system of linear equations. When the framework is applied to binary and ternary 4-point interpolatory subdivision schemes, we find that the corresponding coefficient matrices are strictly diagonally dominant, and so the evaluation processes are robust. For any individual irrational parameters between 0 and 1, its approximate value is computed by a recursive algorithm which can attain an arbitrary error bound. For surface schemes generalizing univariate subdivision schemes with polynomial reproduction property, exact evaluation methods can also be derived by combining Stam’s method with that of this paper. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we concern ourselves with the determination and evaluation of polynomials that are orthogonal with respect to a general discrete Sobolev inner product, that is, an ordinary inner product on the real line plus a finite sum of atomic inner products involving a finite number of derivatives. In a previous paper we provided a complete set of formulas to compute the coefficients of this recurrence. Here, we study the numerical stability of these algorithms for the generation and evaluation of a finite series of Sobolev orthogonal polynomials. Besides, we propose several techniques for reducing and controlling the rounding errors via theoretical running error bounds and a carefully chosen recurrence. [Copyright &y& Elsevier]

We consider a variant of the well-known Longest Common Subsequence (LCS) problem for weighted sequences. A weighted sequence determines the probability for each symbol to occur at a given position of the sequence (such sequences are also called Position Weighted Matrices, PWM). Two possible such versions of the problem were proposed by (Amir et al., 2009 and 2010), they are called LCWS and LCWS2 (Longest Common Weighted Subsequence 1 and 2). We solve an open problem, stated in the paper by Amir et al., of the tractability of a log-probability version of LCWS2 problem for bounded alphabets, showing that it is NP-hard already for an alphabet of size 2. We also improve the ( 1 / | Σ | ) -approximation algorithm given by Amir et al. (where Σ is the alphabet): we show a polynomial-time approximation scheme (PTAS) for the LCWS2 problem using O ( n 5 ) space. We also give a simpler (1/2)-approximation algorithm for the same problem using only O ( n 2 ) space. [ABSTRACT FROM AUTHOR]

Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least 2 n 3 + 1 in 2-connected n -node solid grid graphs. [ABSTRACT FROM AUTHOR]

Abstract: An extensive literature in economics and social science addresses contests, in which players compete to outperform each other on some measurable criterion, often referred to as a player’s score, or output. Players incur costs that are an increasing function of score, but receive prizes for obtaining higher score than their competitors. In this paper we study finite games that are discretized contests, and the problems of computing exact and approximate Nash equilibria. Our motivation is the worst-case hardness of Nash equilibrium computation, and the resulting interest in important classes of games that admit polynomial-time algorithms. For games that have a tie-breaking rule for players’ scores, we present a polynomial-time algorithm for computing an exact equilibrium in the 2-player case, and for multiple players, a characterization of Nash equilibria that shows an interesting parallel between these games and unrestricted 2-player games in normal form. When ties are allowed, via a reduction from these games to a subclass of anonymous games, we give approximation schemes for two special cases: constant-sized set of strategies, and constant number of players. [Copyright &y& Elsevier]

Abstract: In this paper, an algorithm to construct -point (for any integer ) binary approximating subdivision schemes has been developed using the Cox–de Boor recursion formula. Some properties like symmetry of basis functions and polynomial reproduction are also discussed. It can be observed that most of the existing binary approximating schemes (corner cutting scheme developed by Chaikin, and 3-point, 4-point, 5-point and 6-point schemes introduced by Siddiqi and Ahmad) are either special cases or can be reproduced by the proposed algorithm. [Copyright &y& Elsevier]

Abstract: The voting rules proposed by Dodgson and Young are both designed to find an alternative closest to being a Condorcet winner, according to two different notions of proximity; the score of a given alternative is known to be hard to compute under either rule. In this paper, we put forward two algorithms for approximating the Dodgson score: a combinatorial, greedy algorithm and an LP-based algorithm, both of which yield an approximation ratio of , where m is the number of alternatives and is the st harmonic number. We also prove that our algorithms are optimal within a factor of 2, unless problems in have quasi-polynomial-time algorithms. Despite the intuitive appeal of the greedy algorithm, we argue that the LP-based algorithm has an advantage from a social choice point of view. Further, we demonstrate that computing any reasonable approximation of the ranking produced by Dodgsonʼs rule is -hard. This result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the social choice theory literature when comparing Dodgson elections with simpler voting rules. Finally, we show that the problem of calculating the Young score is -hard to approximate by any factor. This leads to an inapproximability result for the Young ranking. [Copyright &y& Elsevier]

Abstract: In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem (Min-TCO in short) has been investigated: given a set of topics and a collection of users together with the lists of topics they are interested in, the aim is to connect these users to a network by a minimum number of edges such that every graph induced by users interested in a common topic is connected. It is known that Min-TCO is -hard and approximable within in polynomial time. In this paper, we further investigate the problem and some of its special instances. We give various hardness results for instances where the number of topics in which a user is interested in is bounded by a constant, and also for the instances where the number of users interested in a common topic is a constant. For the latter case, we present a first constant approximation algorithm. We also present some polynomial-time algorithms for very restricted instances of Min-TCO. [Copyright &y& Elsevier]

Abstract: This paper considers bi-criteria scheduling on a single parallel-batch machine to minimizing two regular scheduling criteria that are non-decreasing in the job completion times. For minimizing the total weighted completion time and the makespan simultaneously, we prove that the problem is NP-hard in the ordinary sense and possesses a fully polynomial-time approximation scheme. For minimizing the weighted total number of tardy jobs and the makespan simultaneously, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme. Furthermore, we identify that all Pareto-optimal solutions for and can be found in pseudo-polynomial time, respectively. [Copyright &y& Elsevier]

Abstract: In this paper we show that the problem of identifying an edge of a graph such that there exists an optimal vertex cover of containing exactly one of the vertices and is NP-hard. Such an edge is called a weak edge. We then develop a polynomial time approximation algorithm for the vertex cover problem with performance guarantee , where is an upper bound on a measure related to a weak edge of a graph. A related problem of identifying an edge such that there exists an optimal vertex cover containing both vertices and is also shown to be NP-hard. Further, we discuss a new relaxation of the vertex cover problem which is used in our approximation algorithm to obtain smaller values of . We also obtain linear programming representations of the vertex cover problem on special graphs. [Copyright &y& Elsevier]

Abstract: The problem of economic dispatch with multiple fuel units has been widely addressed via different techniques using approximate methods due to the exponential complexity of full enumeration in the underlying combinatory problem. A method has recently been outlined by Min et al. (2008), that allows the problem to be solved in an exact way in polynomial time. In this paper, we present an alternative technique and take this idea further, studying and comparing two algorithms of polynomial complexity: basic recurrence and divide-and-conquer. Moreover, we provide the exact solution to the problem by Lin and Viviani (1984), that constitutes the traditional test for all approximate methods and present a comprehensive survey of several heuristic approaches. [Copyright &y& Elsevier]

Abstract: We consider the minimum rainbow subgraph problem (MRS): given a graph , whose edges are coloured with colours. Find a subgraph of of minimum order and with edges such that each colour occurs exactly once. For graphs with maximum degree there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of . In this paper we present a polynomial-time approximation algorithm with an approximation ratio of for . [ABSTRACT FROM AUTHOR]

Abstract: In this paper we introduce and study cooperative variants of the Traveling Salesperson Problem. In these problems a salesperson has to make deliveries to customers who are willing to help in the process. Customer cooperativeness may be manifested in several modes: they may assist by approaching the salesperson, by reselling the goods they purchased to other customers, or by doing both. Several objectives are of interest: minimizing the total distance traveled by all of the participants, minimizing the maximal distance traveled by a participant and minimizing the total time until all of the deliveries are made. All of the combinations of cooperation modes and objective functions are considered, both in weighted undirected graphs and in Euclidean space. We show that most of the problems have a constant approximation algorithm, many of the others admit a PTAS, and a few are solvable in polynomial time. On the intractability side we provide NP-hardness proofs and inapproximability factors, some of which are tight. [Copyright &y& Elsevier]

Abstract: Given an -vertex directed graph and a set of requests, we consider assigning a set of edges to each vertex in so that for every request in the union of the edge sets assigned to and contains a path from to . The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinalities of the edge sets assigned to each vertex. This problem has been shown to be NP-hard in general, though it is polynomially solvable for some restricted classes of graphs and restricted request structures, such as bidirectional trees with requests of all pairs of vertices. In this paper, we give an advanced investigation about the difficulty of MCD by focusing on the relationship between its (in)approximability and request structures. We first show that MCD with general has lower and upper bounds on approximation ratio under the assumption . We then assume forms a clique structure, called Subset-Full, which is a natural setting in the context of the application. Interestingly, under this natural setting, MCD becomes 2-approximable, though it has still no polynomial time approximation algorithm whose factor is better than 677/676 unless . Finally, we show that this approximation ratio can be improved to 3/2 for the undirected variant of MCD with Subset-Full. [Copyright &y& Elsevier]

Abstract: The well-known problem of the longest common subsequence (LCS), of two strings of lengths and respectively, is -time solvable and is a classical distance measure for strings. Another well-studied string comparison measure is that of parameterized matching, where two equal-length strings are a parameterized match if there exists a bijection on the alphabets such that one string matches the other under the bijection. All works associated with parameterized pattern matching present polynomial time algorithms. There have been several attempts to accommodate parameterized matching along with other distance measures, as these turn out to be natural problems, e.g., Hamming distance, and a bounded version of edit-distance. Several algorithms have been proposed for these problems. In this paper we consider the longest common parameterized subsequence problem which combines the LCS measure with parameterized matching. We prove that the problem is -hard, and then show a couple of approximation algorithms for the problem. [Copyright &y& Elsevier]

Abstract: By introducing a bivariate matrix-valued linear functional on the scalar polynomial space, a general two-dimensional (2-D) matrix Padé-type approximant () in the inner product space is defined in this paper. The coefficients of its denominator polynomials are determined by taking the direct inner product of matrices. The remainder formula is developed and an algorithm for the numerator polynomials is presented when the generating polynomials are given in advance. By means of the Hankel-like coefficient matrix, a determinantal expression of is presented. Moreover, to avoid the computation of the determinants, two efficient recursive algorithms are proposed. At the end the method of is applied to partial realization problems of 2-D linear systems. [Copyright &y& Elsevier]

Abstract: This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm that achieves an expected ratio of for any constant . By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of for any constant . [Copyright &y& Elsevier]

Abstract: The piecewise algebraic variety, as a set of the common zeros of multivariate splines, is a kind of generalization of the classical algebraic variety. In this paper, we present an algorithm for isolating the zeros of the zero-dimensional piecewise algebraic variety which is primarily based on the interval zeros of univariate interval polynomials. Numerical example illustrates that the proposed algorithm is flexible. [Copyright &y& Elsevier]

Abstract: Method of augmenting graphs is a general approach to solve the maximum independent set problem. As the problem is generally NP-hard, no polynomial time algorithms are available to implement the method. However, when restricted to particular classes of graphs, the approach may lead to efficient solutions. A famous example of this type is the maximum matching algorithm: it finds a maximum matching in a graph , which is equivalent to finding a maximum independent set in the line graph of . In the particular case of line graphs, the method reduces to finding augmenting (alternating) chains. Recent investigations of more general classes of graphs revealed many more types of augmenting graphs. In the present paper we study the problem of finding augmenting graphs different from chains. To simplify this problem, we introduce the notion of a redundant set. This allows us to reduce the problem to finding some basic augmenting graphs. As a result, we obtain a polynomial time solution to the maximum independent set problem in a class of graphs which extends several previously studied classes including the line graphs. [Copyright &y& Elsevier]

Abstract: Polynomials with perturbed coefficients, which can be regarded as interval polynomials, are very common in the area of scientific computing due to floating point operations in a computer environment. In this paper, the zeros of interval polynomials are investigated. We show that, for a degree n interval polynomial, the number of interval zeros is at most n and the number of complex block zeros is exactly n if multiplicities are counted. The boundaries of complex block zeros on a complex plane are analyzed. Numeric algorithms to bound interval zeros and complex block zeros are presented. [Copyright &y& Elsevier]

Abstract: This paper derives an approximation algorithm for multi-degree reduction of a degree n triangular Bézier surface with corners continuity in the norm . The new idea is to use orthonormality of triangular Jacobi polynomials and the transformation relationship between bivariate Jacobi and Bernstein polynomials. This algorithm has a very simple and explicit expression in matrix form, i.e., the reduced matrix depends only on the degrees of the surfaces before and after degree reduction. And the approximation error of this degree-reduced surface is minimum and can get a precise expression before processing of degree reduction. Combined with surface subdivision, the piecewise degree-reduced patches possess global continuity. Finally several numerical examples are presented to validate the effectiveness of this algorithm. [Copyright &y& Elsevier]

Abstract: The plurality problem is a game between two participants: Paul and Carole. We are given n balls, each of them is colored with one out of c colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carole answers yes or no. The game ends when Paul either produces a ball a of the plurality color (meaning that the number of balls colored like a exceeds those of the other colors), or when Paul states that there is no plurality. How many questions does Paul have to ask in the worst case? For , the problem is equivalent to the well-known majority problem which has already been solved (Combinatorica 11 (1991) 383–387). In this paper we show that Moreover, for any , we show that surprisingly the naive algorithm for the plurality problem is asymptotically optimal. [Copyright &y& Elsevier]

In this paper, algorithms for the computation of all matrices of the generalized polynomial Bezout identity are proposed. The algorithms are based on the computation of minimal polynomial basis for the right null spaces of certain polynomial matrices. For this reason, an algorithm for the computation of minimal polynomial bases is also proposed. Since this algorithm relies solely on singular value decompositions of certain real matrices, formed with the coefficients of the polynomial matrix whose minimal polynomial bases one is interested in finding, it can be said to be robust. [Copyright &y& Elsevier]