On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients

Kostka numbers and Littlewood-Richardson coefficients appear in combinatorics and representation theory. Interest in their computation stems from the fact that they are present in quantum mechanical computations since Wigner [15]. In recent times, there have been a number of algorithms proposed to perform this task [1–3, 11, 12]. The issue of their computational complexity has received at-tention in the past, and was raised recently by E. Rassart in [11]. We prove that the problem of computing either quantity is #P-complete. Thus, unless P = NP, which is widely disbelieved, there do not exist efficient algorithms that compute these numbers.     

Computation Models for Parameterized Complexity

A parameterized computational problem is a set of pairs (x, k), where k is a distinguished item called “parameter”. FPT is the class of fixed-parameter tractable problems: for any fixed value of k, they are solvable in time bounded by a polynomial of degree α, where α is a constant not dependent on the parameter. In order to deal with parameterized intractability, Downey and Fellows have introduced a hierarchy of classes W[l] ? W[2] ? ? containing likely intractable parameterized problems, and they have shown that such classes have many natural, complete languages. In this paper we analyze several variations of the halting problem for nondeterministic Turing machines with parameterized time, and we show that its parameterized complexity strongly depends on some resources like the number of tapes, head and internal states, and on the size of the alphabet. Notice that classical polynomial-time complexity fails in distinguishing such features. As byproducts, we show that parameterized complexity is a useful tool for the study of the intrinsic power of some computational models, and we underline the different “computational powers” of some levels of the parameterized hierarchy.     

What is the complexity of a distributed computing system?

Distributed computing systems are becoming bigger and more complex. Although the complexity of large‐scale distributed systems has been acknowledged to be an important challenge, there has not been much work in defining or measuring system complexity. Thus, today, it is difficult to compare the complexities of different systems, or to state that one system is easier to program, to manage, or to use than another. In this article, we try to understand the factors that cause computing systems to appear very complex to people. We define different aspects of system complexity and propose metrics for measuring these aspects. We also show how these aspects affect different kinds of people—viz. developers, administrators, and end‐users. On the basis of the aspects and metrics of complexity that we identify, we propose general guidelines that can help reduce the complexity of systems. © 2007 Wiley Periodicals, Inc. Complexity 12: 37–45, 2007     

Batch delivery scheduling with batch delivery cost on a single machine

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on a single machine. The jobs are delivered in batches and the delivery date of a batch equals the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total weighted flow time and delivery cost. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B ? U for a variable U ? 2 or B ? U for any constant U ? 2. For the case of B ? U, we present a dynamic programming algorithm that runs in pseudo-polynomial time for any constant U ? 2. Furthermore, optimal algorithms are provided for two special cases: (i) jobs have a linear precedence constraint, and (ii) jobs satisfy the agreeable ratio assumption, which is valid, for example, when all the weights or all the processing times are equal.     

Iterated Local Search for Fiber Installation in Optical Network Optimization

The problem of Fiber Installation in Optical Network Optimization consists in routing a set of lightpaths (all-optical connections), such that the cost of the optical components necessary to operate the network is minimized. We propose a novel Iterated Local Search heuristic. Computational results showed that the new heuristic is better than the best heuristic in the literature.     

Paley–Wiener–Schwartz type theorem for the wavelet transform

In the present paper, we discuss about extension of the wavelet transform on distribution space of compact support and develop the Paley–Wiener–Schwartz type theorem for the wavelet transform on the same. Furthermore, Paley–Wiener–Schwartz type theorem for the wavelet transform is also established using the relation between the wavelet transform and double Fourier transform.     

Fast algorithms for computing the Boltzmann collision operator

The development of accurate and fast numerical schemes for the five-fold Boltzmann collision integral represents a challenging problem in scientific computing. For a particular class of interactions, including the so-called hard spheres model in dimension three, we are able to derive spectral methods that can be evaluated through fast algorithms. These algorithms are based on a suitable representation and approximation of the collision operator. Explicit expressions for the errors in the schemes are given and spectral accuracy is proved. Parallelization properties and adaptivity of the algorithms are also discussed.

     

A polynomial-time DNA computing solution for the Bin-Packing Problem

It is suggested here an algorithm based on stickers for the DNA Computing model [S. Roweis, E. Winfree, R. Burgoyne, N. Chelyapov, M. Goodman, P. Rothemund, L. Adleman, A sticker-based model for DNA Computation, Journal of Computational Biology 5 (1998) 615–629] that solves the well known Bin-Packing Problem (BPP), that belongs to the class -Hard in the strong sense, in a time bounded by , where n is the quantity of items and q the space requirements expressed in bits.To the best of the authors’ knowledge, this is the first polynomial time algorithmic solution for the BPP in such a model.     

A simple method for computing state probabilities of theM/G/1 andGI/M/1 finite waiting space queues

This paper presents a simple method for computing steady state probabilities at arbitrary and departure epochs of theM/G/1/K queue. The method is recursive and works efficiently for all service time distributions. The only input required for exact evaluation of state probabilities is the Laplace transform of the probability density function of service time. Results for theGI/M/1/K –1 queue have also been obtained from those ofM/G/1/K queue.     

Sobolev空间中的测不准函数

在齐民友[2]的基础上，本文分三种情形讨论了在Sobolev框架下测不准函数的性质：（Ⅰ）H^s-H^-s,(Ⅱ)H^s-H^s,(Ⅲ)Hloc^s-Hcomp^-s.利用Hermite函数作为L^2的正交基底来分解L^2-函数，并引入基本的拟微分算子将H^s-函数化为L^2-函数，本文得到与[2]相似的框架和结果．     

The Fourier Transform of Functions Satisfying the Lipschitz Condition on Rank 1 Symmetric Spaces

We prove an analog of the classical Titchmarsh theorem on the image under the Fourier transform of a set of functions satisfying the Lipschitz condition in L² for functions on noncompact rank 1 Riemannian symmetric spaces.     

Some Generalized Clifford-Jacobi Polynomials and Associated Spheroidal Wavelets

In the present paper, by extending some fractional calculus to the framework of Clifford analysis, new classes of wavelet functions are presented. Firstly, some classes of monogenic polynomials are provided based on 2-parameters weight functions which extend the classical Jacobi ones in the context of Clifford analysis. The discovered polynomial sets are next applied to introduce new wavelet functions. Reconstruction formula as well as Fourier-Plancherel rules have been proved. The main tool reposes on the extension of fractional derivatives, fractional integrals and fractional Fourier transforms to Clifford analysis.     

广义线性多乘积问题的完全多项式时间近似算法

本文针对广义线性多乘积极小化问题,通过一系列的线性规划问题的解提出一种求其全局最优解的完全多项式时间近似算法,并给出该算法的计算复杂性,且数值算例验证该算法是可行的.     

Complexity of the packing coloring problem for trees

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete.We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs.We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers.     

Pseudo-differential operators involving Watson transform

A class of pseudo-differential operators (p.d.o.'s) associated with the general Fourier kernel studied by Hardy and Titchmarsh is defined. A symbol class T ^m is introduced. It is shown that the p.d.o.'s associated with the symbol are continuous linear mappings of the Braaksma and Schuitman space T(λ,μ) into itself. An integral representation of p.d.o. is obtained. Some special forms of the symbol are considered. It is shown that these p.d.o.'s and their products are bounded in certain Sobolev type space.     

A recursive algorithm for the infinity-norm fixed point problem

We present the PFix algorithm for the fixed point problem f(x)=x on a nonempty domain [a,b], where d1, , and f is a Lipschitz continuous function with respect to the infinity norm, with constant q1. The computed approximation satisfies the residual criterion , where >0. In general, the algorithm requires no more than ∑_i=1^dsⁱ function component evaluations, where s≡max(1,log₂(||b−a||_∞/))+1. This upper bound has order as →0. For the domain [0,1]^d with <0.5 we prove a stronger result, i.e., an upper bound on the number of function component evaluations is , where r≡log₂(1/). This bound approaches as r→∞ (→0) and as d→∞. We show that when q<1 the algorithm can also compute an approximation satisfying the absolute criterion , where x^* is the unique fixed point of f. The complexity in this case resembles the complexity of the residual criterion problem, but with tolerance (1−q) instead of . We show that when q>1 the absolute criterion problem has infinite worst-case complexity when information consists of function evaluations. Finally, we report several numerical tests in which the actual number of evaluations is usually much smaller than the upper complexity bound.