Computing Optimal Steiner Trees in Polynomial Space

Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62 ⁿ )-time enumeration are based on dynamic programming, and require exponential space. Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4) ^k n ^O(logk))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to $O(4^{k}n^{O(\log^{2} k)})$ . This improves on trivial enumeration for roughly k<n/3, which covers most of the cases of practical interest. Combining the latter algorithm (for small k) with trivial enumeration (for large k) we obtain a O(1.59 ⁿ )-time polynomial-space algorithm for the weighted Steiner tree problem. As a second contribution of this paper, we present a O(1.55 ⁿ )-time polynomial-space algorithm for the cardinality version of the problem, where all edge weights are one. This result is based on a improved branching strategy. The refined branching is based on a charging mechanism which shows that, for large values of k, convenient local configurations of terminals and non-terminals exist. The analysis of the algorithm relies on the Measure & Conquer approach: the non-standard measure used here is a linear combination of the number of nodes and number of non-terminals. Using a recent result in Nederlof (International colloquium on automata, languages and programming (ICALP), pp. 713–725, 2009), the running time can be reduced to O(1.36 ⁿ ). The previous best algorithm for the cardinality case runs in O(1.42 ⁿ ) time and exponential space.     

An Analysis of the Dependence Among Financial Markets by Spatial Contagion

Spatial contagion between two financial markets X and Y appears when there is more dependence between X and Y when they are doing badly than when they exhibit typical performance. In this paper, we introduce an index to measure the contagion effects. This tool is based on the use of suitable copulas associated with the markets and on the calculation of the related conditional Spearman's correlation coefficients. As an empirical application, the proposed index is used to create a clustering of European stock market indices to assess their behavior in the recent years. The whole procedure is expected to be useful for portfolio diversification in crisis periods.     

Using micro-documents for feature selection: The case of ordinal text classification

Most popular feature selection methods for text classification such as information gain (also known as “mutual information”), chi-square, and odds ratio, are based on binary information indicating the presence/absence of the feature (or “term”) in each training document. As such, these methods do not exploit a rich source of information, namely, the information concerning how frequently the feature occurs in the training document (term frequency). In order to overcome this drawback, when doing feature selection we logically break down each training document of length k into k training “micro-documents”, each consisting of a single word occurrence and endowed with the same class information of the original training document. This move has the double effect of (a) allowing all the original feature selection methods based on binary information to be still straightforwardly applicable, and (b) making them sensitive to term frequency information. We study the impact of this strategy in the case of ordinal text classification, a type of text classification dealing with classes lying on an ordinal scale, and recently made popular by applications in customer relationship management, market research, and Web 2.0 mining. We run experiments using four recently introduced feature selection functions, two learning methods of the support vector machines family, and two large datasets of product reviews. The experiments show that the use of this strategy substantially improves the accuracy of ordinal text classification.     

Optimal resource assignment through negotiation in a multi-agent manufacturing system

Research studies on multi-agent systems have been recently boosted by manufacturing and logistics with deep motivations like the presence of independent human deciders with individual goals, the aspiration to dominate the complexity of decision-making in large organizations, the simplicity and robustness of self-reacting distributed systems. After a survey of the multi-agent paradigm and its applications, the paper introduces the notion of hybrid holonic system to study the effect of supervision on a system whose elements negotiate and cooperate in a rule-settled environment to obtain resources for system operation. The supervisor can spur or disincentive agents by assigning/denying resources to them. A simple single-decider optimization model referred to a real application is described, and solution methodologies for optimal resource allocation fitting different scenarios (centralized, distributed, multi-agent) are discussed, identifying ranges of autonomy, quantifying rewarding and defining a negotiation protocol between the agents and the supervisor. Aim of the paper is to describe through an example a general methodology for quantitative decision-making in multi-agent organizations.     

Synthesis of Autosymmetric Functions in a New Three-Level Form

Autosymmetric functions exhibit a special type of regularity that can speed-up the minimization process. Based on this autosymmetry, we propose a three level form of logic synthesis, called ORAX (EXOR-AND-OR), to be compared with the standard minimal SOP (Sum of Products) form. First we provide a fast ORAX minimization algorithm for autosymmetric functions. The ORAX network for a function f has a first level of at most 2(n−k) EXOR gates, followed by the AND-OR levels, where n is the number of input variables and k is the “autosymmetry degree” of f. In general a minimal ORAX form has smaller size than a standard minimal SOP form for the same function. We show how the gain in area of ORAX over SOP can be measured without explicitly generating the latter. If preferred, a SOP expression can be directly derived from the corresponding ORAX. A set of experimental results confirms that the ORAX form is generally more compact than the SOP form, and its synthesis is much faster than classical three-level logic minimization. Indeed ORAX and SOP minimization times are often comparable, and in some cases ORAX synthesis is even faster.     

A techno-economic comparison between two technologies for bioethanol production from lignocellulose

The conversion of biomass into biofuels can reduce the strategic vulnerability of petroleum-based transportation systems. Bioethanol has received considerable attention over the last years as a fuel extender or even as a neat liquid fuel. Lignocellulosic materials are very attractive substrates for the production of bioethanol because of their low cost and their great potential availability. Two different process alternatives (i.e. the enzymatic hydrolysis and fermentation process and the gasification and fermentation process) for the production of fuel ethanol from lignocellulosic feedstock are considered and analysed. After a rigorous mass and energy balance, design optimisation is carried out. Both processes are assessed in terms of ethanol yield and power generation as well as from a financial point of view. A sensitivity analysis on critical parameters of the processes' productivity and profitability is performed.     

Single thermoplastic pellet molding by means of diode laser for micromolding application

An innovative system for thermoplastic micromolding is presented. A completely transparent mold is used, and a diode laser is used as heating source. Laser heating is performed on a single thermoplastic pellet positioned inside the mold between two glass plates. A very low force is necessary for shaping. Molding tests were performed on commercial ABS and several process parameters were investigated such as laser power, interaction time, focalization condition, and support material properties. High pellet formability was observed in all the cases. Using nontransparent pellet supports it is possible to increase molding efficiency even if the risk of polymer degradation increases. A master curve can be fabricated for molding test results providing a correct comparison among the different process conditions. POLYM. ENG. SCI., 47:168–173, 2007. © 2007 Society of Plastics Engineers     

Spectral Green's Functions for Layered Gyrotropic Structures Through a Transmission-Line Approach

In this work, a straightforward method is shown to derive spectral Green's functions in classes of planar structures including gyrotropic media, based on a recently proposed transmission-line formalism. In particular, the analysis is expressly carried out for a current line source in layered configurations with transversely-magnetized ferrites, useful for microwave and millimeter-wave waveguiding and radiating devices.