Lower Bounds for Kernelizations and Other Preprocessing Procedures

We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P≠NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563–574, Springer, Berlin, 2008; Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), ACM, New York, pp. 133–142, 2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a “linear OR” and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with |y|=k ^O(1)⋅|x|^1−ε (here ε is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of preprocessing procedures, namely the various notions of kernelizations, self-reductions and compressions.     

Computation of Minimum Energy Paths for Quasi-Linear Problems

We investigate minimum energy paths of the quasi-linear problem with the p-Laplacian operator and a double-well potential. We adapt the String method of E, Ren, and Vanden-Eijnden (J. Chem. Phys. 126, 2007) to locate saddle-type solutions. In one-dimension, the String method is shown to find a minimum energy path that can align along one-dimensional “ridges” of saddle-continua. We then apply the same method to locate saddle solutions and transition paths of the two-dimensional quasi-linear problem. The method developed is applicable to a general class of quasi-linear PDEs.     

Unified Computation of Strict Maximum Likelihood for Geometric Fitting

A new numerical scheme is presented for computing strict maximum likelihood (ML) of geometric fitting problems having an implicit constraint. Our approach is orthogonal projection of observations onto a parameterized surface defined by the constraint. Assuming a linearly separable nonlinear constraint, we show that a theoretically global solution can be obtained by iterative Sampson error minimization. Our approach is illustrated by ellipse fitting and fundamental matrix computation. Our method also encompasses optimal correction, computing, e.g., perpendiculars to an ellipse and triangulating stereo images. A detailed discussion is given to technical and practical issues about our approach.     

The Computation of a Locally Conservative Stress for the Continuous Galerkin Method for Compressible Linearly Elastic Materials

We show how to postprocess the approximate displacement given by the continuous Galerkin method for compressible linearly elastic materials to obtain an optimally convergent approximate stress that renders the method locally conservative. The postprocessing is extremely efficient as it requires the inversion of a symmetric, positive definite matrix whose condition number is independent of the mesh size. Although the new stress is not symmetric, its asymmetry can be controlled by a small term which is of the same order as that of the error of the approximate stress itself. The continuous Galerkin method is thus competitive with mixed methods providing stresses with similar convergence properties. The first author was supported in part by the National Science Foundation (Grant DMS-0411254) and by the University of Minnesota Supercomputing Institute.     

Context,Computation, and Optimal ROC Performance in Hierarchical Models

It is widely recognized that human vision relies on contextual information, typically arising from each of many levels of analysis. Local gradient information, otherwise ambiguous, is seen as part of a smooth contour or sharp angle in the context of an object’s boundary or corner. A stroke or degraded letter, unreadable by itself, contributes to the perception of a familiar word in the context of the surrounding strokes and letters. The iconic Dalmatian dog stays invisible until a multitude of clues about body parts and posture, and figure and ground, are coherently integrated. Context is always based on knowledge about the composition of parts that make up a whole, as in the arrangement of strokes that make up a letter, the arrangement of body parts that make up an animal, or the poses and postures of individuals that make up a mob. From this point of view, the hierarchy of contextual information available to an observer derives from the compositional nature of the world being observed. We will formulate this combinatorial viewpoint in terms of probability distributions and examine the computational implications. Whereas optimal recognition performance in this formulation is NP-complete, we will give mathematical and experimental evidence that a properly orchestrated computational algorithm can achieve nearly optimal recognition within a feasible number of operations. We will interpret the notions of bottom-up and top-down processing as steps in the staging of one such orchestration.     

Competitive Analysis of Scheduling Algorithms for Aggregated Links

We study an online job scheduling problem arising in networks with aggregated links. The goal is to schedule n jobs, divided into k disjoint chains, on m identical machines, without preemption, so that the jobs within each chain complete in the order of release times and the maximum flow time is minimized. We present a deterministic online algorithm with competitive ratio , and show a matching lower bound, even for randomized algorithms. The performance bound for we derive in the paper is, in fact, more subtle than a standard competitive ratio bound, and it shows that in overload conditions (when many jobs are released in a short amount of time), ’s performance is close to the optimum. We also show how to compute an offline solution efficiently for k=1, and that minimizing the maximum flow time for k,m≥2 is -hard. As by-products of our method, we obtain two offline polynomial-time algorithms for minimizing makespan: an optimal algorithm for k=1, and a 2-approximation algorithm for any k. W. Jawor and M. Chrobak supported by NSF grants OISE-0340752 and CCR-0208856. Work of C. Dürr conducted while being affiliated with the Laboratoire de Recherche en Informatique, Université Paris-Sud, 91405 Orsay. Supported by the CNRS/NSF grant 17171 and ANR Alpage.     

A Convergence Analysis of the Inexact Simplified Jacobi–Davidson Algorithm for Polynomial Eigenvalue Problems

The simplified Jacobi–Davidson (JD) method is a variant of the JD method without subspace acceleration. If the correction equation is solved approximately, the inexact simplified JD method is obtained. In this paper, we present a new convergence analysis of the inexact simplified JD method. The analysis applies to polynomial eigenvalue problems with simple eigenpairs. We first establish a relationship between the solution of the correction equation and the residual of the approximate eigenpair. From this relationship, we find the difference of two adjacent approximate eigenvalues bounded in terms of the residual norm of the approximate eigenpair. Then we prove the convergence of the inexact simplified JD method in terms of the residual norm of the approximate eigenpair. Depending on how accurately we solve the correction equation, the convergence rate of the inexact simplified JD may take several different forms. Numerical experiments confirm the convergence analysis.     

A Primal-Dual Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions

We develop an algorithm for computing the equilibrium price in the Fisher’s exchange market model with logarithmic utility functions. The algorithm is proved to converge to the equilibrium price in finite time and performs well in experimental tests. Supported by Natural Science Foundation of China (No.60135010,60321002) and the Chinese National Key Foundation Research and Development Plan (2004CB318108).     

Is there a Need for Survivable Computation in Critical Infrastructures?

Which critical infrastructures are vulnerable to cyber terrorist and information warfare attacks today is decided on an ad-hoc basis. This has lead to incorrect conclusions and may imply a waste of money. Moreover, the issue of which infrastructures are the most critical to the survival of our economy is not obvious. Methods to evaluate these questions are discussed. We also discuss some of the methods that can be used to increase the survivability of computation.     

Exponential Lower Bounds on the Complexity of?a?Class of?Dynamic Programs for Combinatorial Optimization Problems

We prove exponential lower bounds on the running time of Dynamic Programs (DP) of a certain class for some Combinatorial Optimization Problems. The class of DPs for which we derive the lower bounds is general enough to include well-known DPs for Combinatorial Optimization Problems, such as the ones developed for the Shortest Path Problem, the Knapsack Problem, or the Traveling Salesman Problem. The problems analyzed include the Traveling Salesman Problem (TSP), the Bipartite Matching Problem (BMP), the Min and the Max Cut Problems (MCP), the Min Partition Problem (MPP), and the Min Cost Test Collection Problem (MCTCP). We draw a connection between Dynamic Programs and algorithms for polynomial evaluation. We then derive and use complexity results of polynomial evaluation to prove similar results for Dynamic Programs for the TSP or the BMP. We define a reduction between problems that allows us to generalize these bounds to problems for which either the TSP or the BMP transforms to. Moreover, we show that some standard transformations between problems are of this kind. In this fashion, we extend the lower bounds to other Combinatorial Optimization Problems.     

Model-based control architecture for attentive robots in rescue scenarios

In this paper we present a control architecture for an autonomous rescue robot specialized in victim finding in an unknown and unstructured environment. The reference domain for rescue robots is the rescue-world arenas purposefully arranged for the Robocup competitions. The main task of a rescue mobile robot is to explore the environment and report to the rescue-operators the map of visited areas annotated with its finding. In this context all the attentional activities play a major role in decision processes: salient elements in the environment yield utilities and objectives. A model-based executive controller is proposed to coordinate, integrate, and monitor the distributed decisions and initiatives emerging from the modules involved in the control loop. We show how this architecture integrates the reactive model-based control of a rescue mission, with an attentive perceptual activity processing the sensor and visual stimuli. The architecture has been implemented and tested in real-world experiments by comparing the performances of metric exploration and attentive exploration. The results obtained demonstrate that the attentive behavior significantly focus the exploration time in salient areas enhancing the overall victim finding effectiveness.

Syllable modeling in continuous speech recognition for Tamil language

In automatic speech recognition, the phone has probably been a dominating sub-word unit for more than one decade. Context Dependent phone or triphone modeling accounts for contextual variations between adjacent phones and state tying addresses modeling of triphones that are not seen during training. Recently, syllable is gaining momentum as a new sub-word unit. Syllable being a larger unit than a phone addresses the severe contextual variations between phones within it. Therefore, it is more stable than a phone and models pronunciation variability in a systematic way. Tamil language has challenging features like agglutination and morpho-phonology. In this paper, attempts have been made to provide solutions to these issues by using the syllable as a sub-word unit in an acoustic model. Initially, a small vocabulary context independent word models and a medium vocabulary context dependent phone models are developed. Subsequently, an algorithm based on prosodic syllable is proposed and two experiments have been conducted. First, syllable based context independent models have been trained and tested. Despite large number of syllables, this system has performed reasonably well compared to context independent word models in terms of word error rate and out of vocabulary words. Subsequently, in the second experiment, syllable information is integrated in conventional triphone modeling wherein cross-syllable triphones are replaced with monophones and the number of context dependent phone models is reduced by 22.76% in untied units. In spite of reduction in the number of models, the accuracy of the proposed system is comparable to that of the baseline triphone system.     

Genetic Algorithm for Boolean minimization in an FPGA cluster

Evolutionary algorithms are an alternative option to the Boolean synthesis due to that they allow one to create hardware structures that would not be able to be obtained with other techniques. This paper shows a parallel genetic programming (PGP) Boolean synthesis implementation based on a cluster of FPGAs that takes full advantage of parallel programming and hardware/software co-design techniques. The performance of our cluster of FPGAs implementation has been compared with an HPC implementation. The experimental results have shown an excellent behavior in terms of speed up (up to ×500) and in terms of solving the scalability problems of this algorithms present in previous works.     

Stackelberg Strategies for Selfish Routing in General Multicommodity Networks

A natural generalization of the selfish routing setting arises when some of the users obey a central coordinating authority, while the rest act selfishly. Such behavior can be modeled by dividing the users into an α fraction that are routed according to the central coordinator’s routing strategy (Stackelberg strategy), and the remaining 1−α that determine their strategy selfishly, given the routing of the coordinated users. One seeks to quantify the resulting price of anarchy, i.e., the ratio of the cost of the worst traffic equilibrium to the system optimum, as a function of α. It is well-known that for α=0 and linear latency functions the price of anarchy is at most 4/3 (J. ACM 49, 236–259, 2002). If α tends to 1, the price of anarchy should also tend to 1 for any reasonable algorithm used by the coordinator. We analyze two such algorithms for Stackelberg routing, LLF and SCALE. For general topology networks, multicommodity users, and linear latency functions, we show a price of anarchy bound for SCALE which decreases from 4/3 to 1 as α increases from 0 to 1, and depends only on α. Up to this work, such a tradeoff was known only for the case of two nodes connected with parallel links (SIAM J. Comput. 33, 332–350, 2004), while for general networks it was not clear whether such a result could be achieved, even in the single-commodity case. We show a weaker bound for LLF and also some extensions to general latency functions. The existence of a central coordinator is a rather strong requirement for a network. We show that we can do away with such a coordinator, as long as we are allowed to impose taxes (tolls) on the edges in order to steer the selfish users towards an improved system cost. As long as there is at least a fraction α of users that pay their taxes, we show the existence of taxes that lead to the simulation of SCALE by the tax-payers. The extension of the results mentioned above quantifies the improvement on the system cost as the number of tax-evaders decreases. Research of G. Karakostas supported by an NSERC Discovery Grant and MITACS. Research of S. Kolliopoulos partially supported by the University of Athens under the project Kapodistrias.     

Rule-based data mining for yield improvement in semiconductor manufacturing

We describe an automated system for improving yield, power consumption and speed characteristics in the manufacture of semiconductors. Data are continually collected in the form of a history of tool usage, electrical and other real-valued measurements—a dimension of tens of thousands of features. Unique to this approach is the inference of patterns in the form of binary regression rules that demonstrate a significantly higher or lower performance value for tools relative to the overall mean for that manufacturing step. Results are filtered by knowledge-based constraints, increasing the likelihood that empirically validated rules will prove interesting and worth further investigation. This system is currently installed in the IBM 300 mm fab, manufacturing game chips and microprocessors. It has detected numerous opportunities for yield and performance improvement, saving many millions of dollars.     

A recursive genetic framework for evolutionary decision-making in problems with high dynamism

Communication and coordination are the main cores for reaching a constructive agreement among multi-agent systems (MASs). Dividing the overall performance of MAS to individual agents may lead to group learning as opposed to individual learning, which is one of the weak points of MASs. This paper proposes a recursive genetic framework for solving problems with high dynamism. In this framework, a combination of genetic algorithm and multi-agent capabilities is utilised to accelerate team learning and accurate credit assignment. The argumentation feature is used to accomplish agent learning and the negotiation features of MASs are used to achieve a credit assignment. The proposed framework is quite general and its recursive hierarchical structure could be extended. We have dedicated one special controlling module for increasing convergence time. Due to the complexity of blackjack, we have applied it as a possible test bed to evaluate the system’s performance. The learning rate of agents is measured as well as their credit assignment. The analysis of the obtained results led us to believe that our robust framework with the proposed negotiation operator is a promising methodology to solve similar problems in other areas with high dynamism.     

Evolution of Probability Distribution in Time for Solutions of Hyperbolic Equations

We investigate the evolution of the probability distribution function in time for some wave and Maxwell equations in random media for which the parameters, e.g. permeability, permittivity, fluctuate randomly in space; more precisely, two different media interface randomly in space. We numerically compute the probability distribution and density for output solutions. The underlying numerical and statistical techniques are the so-called polynomial chaos Galerkin projection, which has been extensively used for simulating partial differential equations with uncertainties, and the Monte Carlo simulations.