Search

In this paper, we introduce and study a new coloring problem of a graph called the dominated coloring. A dominated coloring of a graph $$G$$ is a proper vertex coloring of $$G$$ such that each color class is dominated by at least one vertex of $$G$$ . The minimum number of colors among all dominated colorings is called the dominated chromatic number, denoted by $$\chi _{dom}(G)$$ . In this paper, we establish the close relationship between the dominated chromatic number $$\chi _{dom}(G)$$ and the total domination number $$\gamma _t(G)$$ ; and the equivalence for triangle-free graphs. We study the complexity of the problem by proving its NP-completeness for arbitrary graphs having $$\chi _{dom}(G) \ge 4$$ and by giving a polynomial time algorithm for recognizing graphs having $$\chi _{dom}(G) \le 3$$ . We also give some bounds for planar and star-free graphs and exact values for split graphs. [ABSTRACT FROM AUTHOR]

Although widely applied in optimisation, relatively little has been proven rigorously about the role and behaviour of populations in randomised search processes. This paper presents a new method to prove upper bounds on the expected optimisation time of population-based randomised search heuristics that use non-elitist selection mechanisms and unary variation operators. Our results follow from a detailed drift analysis of the population dynamics in these heuristics. This analysis shows that the optimisation time depends on the relationship between the strength of the selective pressure and the degree of variation introduced by the variation operator. Given limited variation, a surprisingly weak selective pressure suffices to optimise many functions in expected polynomial time. We derive upper bounds on the expected optimisation time of non-elitist evolutionary algorithms (EA) using various selection mechanisms, including fitness proportionate selection. We show that EAs using fitness proportionate selection can optimise standard benchmark functions in expected polynomial time given a sufficiently low mutation rate. As a second contribution, we consider an optimisation scenario with partial information, where fitness values of solutions are only partially available. We prove that non-elitist EAs under a set of specific conditions can optimise benchmark functions in expected polynomial time, even when vanishingly little information about the fitness values of individual solutions or populations is available. To our knowledge, this is the first runtime analysis of randomised search heuristics under partial information. [ABSTRACT FROM AUTHOR]

Term rewrite systems are useful in many areas of computer science. Two especially important areas are decision procedures for the word problem of some algebraic systems and rule-based programming. One of the most studied properties of rewrite systems is confluence, and one of the primary benefits of having a confluent rewrite system is that the system also has uniqueness of normal forms. However, uniqueness of normal forms is an interesting property in its own right and well studied. Also, confluence can be too strong a requirement for some applications. In this paper, we study the decidability of uniqueness of normal forms. Uniqueness of normal forms is decidable for ground rewrite systems, but is undecidable in general. This paper shows that the uniqueness of normal forms problem is decidable for the class of linear shallow term rewrite systems, and gives a decision procedure that is polynomial as long as the arities of the function symbols are bounded or the signature is fixed. [ABSTRACT FROM AUTHOR]

In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization models have wide applications, e.g., in signal processing, magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions are non-convex, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time approximation algorithms. In particular, we first study optimization of a multi-linear tensor function over the Cartesian product of spheres. We shall propose approximation algorithms for such problem and derive worst-case performance ratios, which are shown to be dependent only on the dimensions of the model. The methods are then extended to optimize a generic multi-variate homogeneous polynomial function with spherical constraint. Likewise, approximation algorithms are proposed with provable approximation performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids; namely, we consider maximization of a homogeneous polynomial over the intersection of ellipsoids centered at the origin, and propose polynomial-time approximation algorithms with provable worst-case performance ratios. Numerical results are reported, illustrating the effectiveness of the approximation algorithms studied. [ABSTRACT FROM AUTHOR]

The paper considers conditions under which rank factorizations of a two-parameter polynomial matrix can be affected with the use of unimodular matrices, as in the one-parameter case. Algorithms for computing such factorizations and a minimal basis of the null space of the corresponding matrix are presented. Also an algorithm for inverting unimodular two-parameter polynomial matrices is suggested. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]

A k-dissimilarity D on a finite set X, | X| ≥ k, is a map from the set of size k subsets of X to the real numbers. Such maps naturally arise from edgeweighted trees T with leaf-set X: Given a subset Y of X of size k, D( Y ) is defined to be the total length of the smallest subtree of T with leaf-set Y . In case k = 2, it is well-known that 2-dissimilarities arising in this way can be characterized by the so-called '4-point condition'. However, in case k > 2 Pachter and Speyer () recently posed the following question: Given an arbitrary k-dissimilarity, how do we test whether this map comes from a tree? In this paper, we provide an answer to this question, showing that for k ≥ 3 a k-dissimilarity on a set X arises from a tree if and only if its restriction to every 2 k-element subset of X arises from some tree, and that 2 k is the least possible subset size to ensure that this is the case. As a corollary, we show that there exists a polynomial-time algorithm to determine when a k-dissimilarity arises from a tree. We also give a 6-point condition for determining when a 3-dissimilarity arises from a tree, that is similar to the aforementioned 4-point condition. [ABSTRACT FROM AUTHOR]

It was shown by Griggs and Wu that a graph of minimal degree 4 on n vertices has a spanning tree with at least $$ \frac{2}{5} $$ n leaves, which is asymptomatically the best possible bound for this class of graphs. In this paper, we present a polynomial time algorithm that finds in any graph with k vertices of degree greater than or equal to 4 and k′ vertices of degree 3 a spanning tree with $$ \left[ {\frac{2}{5} \cdot k + \frac{2}{{15}} \cdot k'} \right] $$ leaves. [ABSTRACT FROM AUTHOR]

This paper presents a simplified algorithm for the profiling of the rack gear tool to generate the active profile associated with rolling centrodes. The algorithm is based on the enveloping surfaces principles and reduces the computational problem by proposing an approximate representation of tool’s profile using only three or four points on the profile to be generated by using Bezier representations of the surfaces. The algorithm computes the coefficients of a Bezier substitution polynomial instead of computing hundreds of points on the active profile. This simplifies the solution methodology and requires only a limited number of points along the profile to be generated. The algorithm is computationally efficient and can also be used in the case when the active profile to be generated is physically measured at a few points. Examples include mill tools, splined shafts, and gears. [ABSTRACT FROM AUTHOR]

Fischer and Rabin proved in (Proceedings of the SIAM-AMS Symposium in Applied Mathematics, vol. 7, pp. 27–41, ) that the decision problem for Presburger Arithmetic has at least double exponential worst-case complexity (for deterministic and for nondeterministic Turing machines). In Kapovich et al. (J. Algebra 264(2):665–694, ) a theory of generic-case complexity was developed, where algorithmic problems are studied on “most” inputs instead of set of all inputs. A question rises about existing of more efficient (say, polynomial) generic algorithm deciding Presburger Arithmetic on a set of closed formulas of asymptotic density 1. We prove in this paper that there is not an exponential generic decision algorithm working correctly on an input set of asymptotic density exponentially converging to 1 (so-called strongly generic sets). [ABSTRACT FROM AUTHOR]

The problem of Horn Minimization (HM) can be stated as follows: given a Horn CNF representing a Boolean function f, find a shortest possible (optimally compressed) CNF representation of f, i.e., a CNF representation of f which consists of the minimum possible number of clauses. This problem is the formalization of the problem of knowledge compression for speeding up queries to propositional Horn expert systems, and it is known to be NP-hard. There are two subclasses of Horn functions for which HM is known to be solvable in polynomial time: acyclic and quasi-acyclic Horn functions. In this paper we define a new class of Horn functions properly containing both of the known classes and design a polynomial time HM algorithm for this new class. [ABSTRACT FROM AUTHOR]

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar “taste” may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible approximation of the player’s real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead. [ABSTRACT FROM AUTHOR]

The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm along with periodic rescaling runs in polynomial-time. The resulting algorithm for linear programming has an elementary description and analysis. [ABSTRACT FROM AUTHOR]

The concept of evolutionarily stable strategies (ESS) has been central to applications of game theory in evolutionary biology, and it has also had an influence on the modern development of game theory. A regular ESS is an important refinement the ESS concept. Although there is a substantial literature on computing evolutionarily stable strategies, the precise computational complexity of determining the existence of an ESS in a symmetric two-player strategic form game has remained open, though it has been speculated that the problem is $$\mathsf{NP}$$ -hard. In this paper we show that determining the existence of an ESS is both $${\mathsf{NP}}$$ -hard and $${\mathsf{coNP}}$$ -hard, and that the problem is contained in $$\Sigma_{2}^{\rm p}$$ , the second level of the polynomial time hierarchy. We also show that determining the existence of a regular ESS is indeed $${\mathsf{NP}}$$ -complete. Our upper bounds also yield algorithms for computing a (regular) ESS, if one exists, with the same complexities. [ABSTRACT FROM AUTHOR]

The paper considers the problem of computing zeros of scalar polynomials in several variables. The zeros of a polynomial are subdivided into the regular (eigen-and mixed) zeros and the singular ones. An algorithm for computing regular zeros, based on a decomposition of a given polynomial into a product of primitive polynomials, is suggested. The algorithm is applied to solving systems of nonlinear algebraic equations. Bibliography: 5 titles. [ABSTRACT FROM AUTHOR]

The paper continues the development of rank-factorization methods for solving certain algebraic problems for multi-parameter polynomial matrices and introduces a new rank factorization of a q-parameter polynomial m × n matrix F of full row rank (called the PG-q factorization) of the form F = PG, where $$P = \prod\limits_{k = 1}^{q - 1} {\prod\limits_{i = 1}^{n_k } {\nabla _i^{(k)} } } $$ is the greatest left divisor of F; Δ i is a regular (q-k)-parameter polynomial matrix the characteristic polynomial of which is a primitive polynomial over the ring of polynomials in q-k-1 variables, and G is a q-parameter polynomial matrix of rank m. The PG-q algorithm is suggested, and its applications to solving some problems of algebra are presented. Bibliography: 6 titles. [ABSTRACT FROM AUTHOR]

The paper continues the investigation of methods for factorizing q-parameter polynomial matrices and considers their applications to solving multiparameter problems of algebra. An extension of the AB-algorithm, suggested earlier as a method for solving spectral problems for matrix pencils of the form A - λB, to the case of q-parameter (q ≥ 1) polynomial matrices of full rank is proposed. In accordance with the AB-algorithm, a finite sequence of q-parameter polynomial matrices such that every subsequent matrix provides a basis of the null-space of polynomial solutions of its transposed predecessor is constructed. A certain rule for selecting specific basis matrices is described. Applications of the AB-algorithm to computing complete polynomials of a q-parameter polynomial matrix and exhausting them from the regular spectrum of the matrix, to constructing irreducible factorizations of rational matrices satisfying certain assumptions, and to computing “free” bases of the null-spaces of polynomial solutions of an arbitrary q-parameter polynomial matrix are considered. Bibliography: 7 titles. [ABSTRACT FROM AUTHOR]

In this paper, we use the Ehlich-Zeller-G9ärtel inequality to derive an algorithm for finding the global minima of polynomials over hyperrectangles as well as to provide a bounding method for the branch-and-bound algorithm. The latter application of the inequality results in an improved algorithm which gives simultaneously a decreasing upper bound and an increasing lower bound for the global minimum at each iteration. The algorithm can be used also to find the Lipschitz constant of a polynomial. [ABSTRACT FROM AUTHOR]