OpenRaiser/Intern-Atlas huggingface dataset:
Support driven reweighted $\ell_1$ minimization
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose a support driven reweighted $\ell_1$ minimization algorithm (SDRL1) that solves a sequence of weighted $\ell_1$ problems and relies on the support estimate accuracy. Our SDRL1 algorithm is related to the IRL1 algorithm proposed by Cand{è}s, Wakin, and Boyd. We demonstrate that it is sufficient to find support estimates with \emph{good} accuracy and apply constant weights instead of using the inverse coefficient magnitudes to achieve gains similar to those of IRL1. We then prove that given a support estimate with sufficient accuracy, if the signal decays according to a specific rate, the solution to the weighted $\ell_1$ minimization problem results in a support estimate with higher accuracy than the initial estimate. We also show that under certain conditions, it is possible to achieve higher estimate accuracy when the intersection of support estimates is considered. We demonstrate the performance of SDRL1 through numerical simulations and compare it with that of IRL1 and standard $\ell_1$ minimization.
A Simulation Model for the Waterfall Software Development Life Cycle
Venue: arXiv cs.SE 2012
Year: 2012

Software development life cycle or SDLC for short is a methodology for designing, building, and maintaining information and industrial systems. So far, there exist many SDLC models, one of which is the Waterfall model which comprises five phases to be completed sequentially in order to develop a software solution. However, SDLC of software systems has always encountered problems and limitations that resulted in significant budget overruns, late or suspended deliveries, and dissatisfied clients. The major reason for these deficiencies is that project directors are not wisely assigning the required number of workers and resources on the various activities of the SDLC. Consequently, some SDLC phases with insufficient resources may be delayed; while, others with excess resources may be idled, leading to a bottleneck between the arrival and delivery of projects and to a failure in delivering an operational product on time and within budget. This paper proposes a simulation model for the Waterfall development process using the Simphony.NET simulation tool whose role is to assist project managers in determining how to achieve the maximum productivity with the minimum number of expenses, workers, and hours. It helps maximizing the utilization of development processes by keeping all employees and resources busy all the time to keep pace with the arrival of projects and to decrease waste and idle time. As future work, other SDLC models such as spiral and incremental are to be simulated, giving project executives the choice to use a diversity of software development methodologies.
Robust self-triggered coordination with ternary controllers
Venue: arXiv cs.SY 2012
Year: 2012

This paper regards coordination of networked systems, which is studied in the framework of hybrid dynamical systems. We design a coordination scheme which combines the use of ternary controllers with a self-triggered communication policy. The communication policy requires the agents to collect, at each sampling time, relative measurements of their neighbors' states: the collected information is then used to update the control and determine the following sampling time. We prove that the proposed scheme ensures finite-time convergence to a neighborhood of a consensus state. We then study the robustness of the proposed self-triggered coordination system with respect to skews in the agents' local clocks, to delays, and to limited precision in communication. Furthermore, we present two significant variations of our scheme. First, we design a time-varying controller which asymptotically drives the system to consensus. Second, we adapt our framework to a communication model in which an agent does not poll all its neighbors simultaneously, but single neighbors instead. This communication policy actually leads to a self-triggered "gossip" coordination system.
Engineering hierarchical complex systems: an agent-based approach. The case of flexible manufacturing systems
Venue: arXiv cs.MA 2012
Year: 2012

This article introduces a formal model to specify, model and validate hierarchical complex systems described at different levels of analysis. It relies on concepts that have been developed in the multi-agent-based simulation (MABS) literature: level, influence and reaction. One application of such model is the specification of hierarchical complex systems, in which decisional capacities are dynamically adapted at each level with respect to the emergences/constraints paradigm. In the conclusion, we discuss the main perspective of this work: the definition of a generic meta-model for holonic multi-agent systems (HMAS).
ACME vs PDDL: support for dynamic reconfiguration of software architectures
Venue: arXiv cs.SE 2012
Year: 2012

On the one hand, ACME is a language designed in the late 90s as an interchange format for software architectures. The need for recon guration at runtime has led to extend the language with speci c support in Plastik. On the other hand, PDDL is a predicative language for the description of planning problems. It has been designed in the AI community for the International Planning Competition of the ICAPS conferences. Several related works have already proposed to encode software architectures into PDDL. Existing planning algorithms can then be used in order to generate automatically a plan that updates an architecture to another one, i.e., the program of a recon guration. In this paper, we improve the encoding in PDDL. Noticeably we propose how to encode ADL types and constraints in the PDDL representation. That way, we can statically check our design and express PDDL constraints in order to ensure that the generated plan never goes through any bad or inconsistent architecture, not even temporarily.
Comparison between Poissonian and Markovian Primary Traffics in Cognitive Radio Networks
Venue: arXiv cs.NI 2012
Year: 2012

Cognitive Radio generates a big interest as a key cost-effective solution for the underutilization of frequency spectrum in legacy communication networks. The objective of this work lies in conducting a performance evaluation of the end-to-end message delivery under both Markovian and Poissonian primary traffics in lossy Cognitive Radio networks. We aim at inferring the most appropriate conditions for an efficient secondary service provision according to the Cognitive Radio network characteristics. Meanwhile, we have performed a general analysis for many still open issues in Cognitive Radio, but at the end only two critical aspects have been considered, namely, the unforeseen primary reclaims in addition to the collided cognitive transmissions due to the Opportunistic Spectrum Sharing. Some graphs, in view of the average Spectral Efficiency, have been computed and plotted to report some comparative results for a given video transmission under the Markovian and the Poissonian primary interruptions.
Bounds on Contention Management in Radio Networks
Venue: arXiv cs.DS 2012
Year: 2012

The local broadcast problem assumes that processes in a wireless network are provided messages, one by one, that must be delivered to their neighbors. In this paper, we prove tight bounds for this problem in two well-studied wireless network models: the classical model, in which links are reliable and collisions consistent, and the more recent dual graph model, which introduces unreliable edges. Our results prove that the Decay strategy, commonly used for local broadcast in the classical setting, is optimal. They also establish a separation between the two models, proving that the dual graph setting is strictly harder than the classical setting, with respect to this primitive.
Fairness and Stability Analysis of Congestion Control Schemes in Vehicular Ad-hoc Networks
Venue: arXiv cs.NI 2012
Year: 2012

Cooperative vehicle safety (CVS) systems operate based on broadcast of vehicle position and safety information to neighboring cars. The communication medium of CVS is a vehicular ad-hoc network. One of the main challenges in large scale deployment of CVS systems is the issue of scalability. To address the scalability problem, several congestion control methods have been proposed and are currently under field study. These algorithms adapt transmission rate and power based on network measures such as channel busy ratio. We examine two such algorithms and study their dynamic behavior in time and space to evaluate stability (in time) and fairness (in space) properties of these algorithms. We present stability conditions and evaluate stability and fairness of the algorithms through simulation experiments. Results show that there is a trade-off between fast convergence, temporal stability and spatial fairness. The proper ranges of parameters for achieving stability are presented for the discussed algorithms. Stability is verified for all typical road density cases. Fairness is shown to be naturally achieved for some algorithms, while under the same conditions other algorithms may suffer from unfairness issues. A method for resolving unfairness is introduced and evaluated through simulations.
On the Computation of the Higher-Order Statistics of the Channel Capacity for Amplify-and-Forward Multihop Transmission
Venue: arXiv cs.IT 2012
Year: 2012

Higher-order statistics (HOS) of the channel capacity provide useful information regarding the level of reliability of the signal transmission at a particular rate. We propose in this letter a novel and unified analysis, which is based on the moment-generating function (MGF) approach, to efficiently and accurately compute the HOS of the channel capacity for amplify-and-forward multihop transmission over generalized fading channels. More precisely, our mathematical formulism is easy-to-use and tractable specifically requiring only the reciprocal MGFs of the instantaneous signal-to-noise ratio distributions of the transmission hops. Numerical and simulation results, performed to exemplify the usefulness of the proposed MGF-based analysis, are shown to be in perfect agreement.
Sumset and Inverse Sumset Inequalities for Differential Entropy and Mutual Information
Venue: arXiv cs.IT 2012
Year: 2012

The sumset and inverse sumset theories of Freiman, Plünnecke and Ruzsa, give bounds connecting the cardinality of the sumset $A+B=\{a+b\;;\;a\in A,\,b\in B\}$ of two discrete sets $A,B$, to the cardinalities (or the finer structure) of the original sets $A,B$. For example, the sum-difference bound of Ruzsa states that, $|A+B|\,|A|\,|B|\leq|A-B|^3$, where the difference set $A-B= \{a-b\;;\;a\in A,\,b\in B\}$. Interpreting the differential entropy $h(X)$ of a continuous random variable $X$ as (the logarithm of) the size of the effective support of $X$, the main contribution of this paper is a series of natural information-theoretic analogs for these results. For example, the Ruzsa sum-difference bound becomes the new inequality, $h(X+Y)+h(X)+h(Y)\leq 3h(X-Y)$, for any pair of independent continuous random variables $X$ and $Y$. Our results include differential-entropy versions of Ruzsa's triangle inequality, the Plünnecke-Ruzsa inequality, and the Balog-Szemerédi-Gowers lemma. Also we give a differential entropy version of the Freiman-Green-Ruzsa inverse-sumset theorem, which can be seen as a quantitative converse to the entropy power inequality. Versions of most of these results for the discrete entropy $H(X)$ were recently proved by Tao, relying heavily on a strong, functional form of the submodularity property of $H(X)$. Since differential entropy is {\em not} functionally submodular, in the continuous case many of the corresponding discrete proofs fail, in many cases requiring substantially new proof strategies. We find that the basic property that naturally replaces the discrete functional submodularity, is the data processing property of mutual information.
Automatic Generation of OWL Ontology from XML Data Source
Venue: arXiv cs.DL 2012
Year: 2012

The eXtensible Markup Language (XML) can be used as data exchange format in different domains. It allows different parties to exchange data by providing common understanding of the basic concepts in the domain. XML covers the syntactic level, but lacks support for reasoning. Ontology can provide a semantic representation of domain knowledge which supports efficient reasoning and expressive power. One of the most popular ontology languages is the Web Ontology Language (OWL). It can represent domain knowledge using classes, properties, axioms and instances for the use in a distributed environment such as the World Wide Web. This paper presents a new method for automatic generation of OWL ontology from XML data sources.
Multi-Sparse Signal Recovery for Compressive Sensing
Venue: arXiv cs.IT 2012
Year: 2012

Signal recovery is one of the key techniques of Compressive sensing (CS). It reconstructs the original signal from the linear sub-Nyquist measurements. Classical methods exploit the sparsity in one domain to formulate the L0 norm optimization. Recent investigation shows that some signals are sparse in multiple domains. To further improve the signal reconstruction performance, we can exploit this multi-sparsity to generate a new convex programming model. The latter is formulated with multiple sparsity constraints in multiple domains and the linear measurement fitting constraint. It improves signal recovery performance by additional a priori information. Since some EMG signals exhibit sparsity both in time and frequency domains, we take them as example in numerical experiments. Results show that the newly proposed method achieves better performance for multi-sparse signals.
Theoretical foundation for CMA-ES from information geometric perspective
Venue: arXiv cs.NE 2012
Year: 2012

This paper explores the theoretical basis of the covariance matrix adaptation evolution strategy (CMA-ES) from the information geometry viewpoint. To establish a theoretical foundation for the CMA-ES, we focus on a geometric structure of a Riemannian manifold of probability distributions equipped with the Fisher metric. We define a function on the manifold which is the expectation of fitness over the sampling distribution, and regard the goal of update of the parameters of sampling distribution in the CMA-ES as maximization of the expected fitness. We investigate the steepest ascent learning for the expected fitness maximization, where the steepest ascent direction is given by the natural gradient, which is the product of the inverse of the Fisher information matrix and the conventional gradient of the function. Our first result is that we can obtain under some types of parameterization of multivariate normal distribution the natural gradient of the expected fitness without the need for inversion of the Fisher information matrix. We find that the update of the distribution parameters in the CMA-ES is the same as natural gradient learning for expected fitness maximization. Our second result is that we derive the range of learning rates such that a step in the direction of the exact natural gradient improves the parameters in the expected fitness. We see from the close relation between the CMA-ES and natural gradient learning that the default setting of learning rates in the CMA-ES seems suitable in terms of monotone improvement in expected fitness. Then, we discuss the relation to the expectation-maximization framework and provide an information geometric interpretation of the CMA-ES.
Non-null Infinitesimal Micro-steps: a Metric Temporal Logic Approach
Venue: arXiv cs.LO 2012
Year: 2012

Many systems include components interacting with each other that evolve with possibly very different speeds. To deal with this situation many formal models adopt the abstraction of "zero-time transitions", which do not consume time. These however have several drawbacks in terms of naturalness and logic consistency, as a system is modeled to be in different states at the same time. We propose a novel approach that exploits concepts from non-standard analysis to introduce a notion of micro- and macro-steps in an extension of the TRIO metric temporal logic, called X-TRIO. We use X-TRIO to provide a formal semantics and an automated verification technique to Stateflow-like notations used in the design of flexible manufacturing systems.
Fuzzy Knowledge Representation Based on Possibilistic and Necessary Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

Within the framework proposed in this paper, we address the issue of extending the certain networks to a fuzzy certain networks in order to cope with a vagueness and limitations of existing models for decision under imprecise and uncertain knowledge. This paper proposes a framework that combines two disciplines to exploit their own advantages in uncertain and imprecise knowledge representation problems. The framework proposed is a possibilistic logic based one in which Bayesian nodes and their properties are represented by local necessity-valued knowledge base. Data in properties are interpreted as set of valuated formulas. In our contribution possibilistic Bayesian networks have a qualitative part and a quantitative part, represented by local knowledge bases. The general idea is to study how a fusion of these two formalisms would permit representing compact way to solve efficiently problems for knowledge representation. We show how to apply possibility and necessity measures to the problem of knowledge representation with large scale data. On the other hand fuzzification of crisp certainty degrees to fuzzy variables improves the quality of the network and tends to bring smoothness and robustness in the network performance. The general aim is to provide a new approach for decision under uncertainty that combines three methodologies: Bayesian networks certainty distribution and fuzzy logic.
Iterated tabu search for the circular open dimension problem
Venue: arXiv cs.OH 2012
Year: 2012

This paper mainly investigates the circular open dimension problem (CODP), which consists of packing a set of circles of known radii into a strip of fixed width and unlimited length without overlapping. The objective is to minimize the length of the strip. An iterated tabu search approach, named ITS, is proposed. ITS starts from a randomly generated solution and attempts to gain improvements by a tabu search procedure. After that, if the obtained solution is not feasible, a perturbation operator is subsequently employed to reconstruct the incumbent solution and an acceptance criterion is implemented to determine whether or not accept the perturbed solution. This process is repeated until a feasible solution has been found or the allowed computation time has been elapsed. Computational experiments based on well-known benchmark instances show that ITS produces quite competitive results with respect to the best known results. For 18 representative CODP instances taken from the literature, ITS succeeds in improving 13 best known results within reasonable time. In addition, for another challenging related variant: the problem of packing arbitrary sized circles into a circular container, ITS also succeeds in improving many best known results. Supplementary experiments are also provided to analyze the influence of the perturbation operator, as well as the acceptance criterion.
Memetic Artificial Bee Colony Algorithm for Large-Scale Global Optimization
Venue: arXiv cs.NE 2012
Year: 2012

Memetic computation (MC) has emerged recently as a new paradigm of efficient algorithms for solving the hardest optimization problems. On the other hand, artificial bees colony (ABC) algorithms demonstrate good performances when solving continuous and combinatorial optimization problems. This study tries to use these technologies under the same roof. As a result, a memetic ABC (MABC) algorithm has been developed that is hybridized with two local search heuristics: the Nelder-Mead algorithm (NMA) and the random walk with direction exploitation (RWDE). The former is attended more towards exploration, while the latter more towards exploitation of the search space. The stochastic adaptation rule was employed in order to control the balancing between exploration and exploitation. This MABC algorithm was applied to a Special suite on Large Scale Continuous Global Optimization at the 2012 IEEE Congress on Evolutionary Computation. The obtained results the MABC are comparable with the results of DECC-G, DECC-G*, and MLCC.
Zwei Anwendungen des Paillier-Kryptosystems: Blinde Signatur und Three-Pass-Protocol
Venue: arXiv cs.CR 2012
Year: 2012

Englisch: In this paper we study the paillier cryptosystem and derive form it to new schemes. First we transform the signature of paillier in a Blind signature. Secondly we propose a three-pass protocol wich use the homomorphic property instead of the commutativity as the Shamir protocol does. German: Basierend auf dem Kryptosystem von Paillier und dem damit eingeführten Problem der zusammengesetzten Residuenklasse werden in diesem Artikel zwei kryptographische Verfahren vorgeschlagen. Zunächst wird die Signatur von Paillier in ein blindes Signaturverfahren umgewandelt. Des Weiteren wird mit der homomorphen Eigenschaft des Kryptosystems von Paillier ein sogenanntes Three-Pass-Protocol - auch No-Key-Protocol genannt - entwickelt.
Dynamic Verification for File Safety of Multithreaded Programs
Venue: arXiv cs.LO 2012
Year: 2012

In this paper, we present a new semantics to check file safety of multithreaded programs. A file-safe program is one that reaches a final configuration under the proposed semantics. We extend the While language with file operations and multi-threading commands, and call the new language whilef. This paper shows that the file safety is an un-decidable property for whilef. The file safety becomes a decidable property in a special case shown in this paper. The case happens when users provide pointer information. If the file is safe we call it a strongly safe file program. We modify the syntax and the semantic of the language and called it SafeWhilef.
Comparison of the C4.5 and a Naive Bayes Classifier for the Prediction of Lung Cancer Survivability
Venue: arXiv cs.LG 2012
Year: 2012

Numerous data mining techniques have been developed to extract information and identify patterns and predict trends from large data sets. In this study, two classification techniques, the J48 implementation of the C4.5 algorithm and a Naive Bayes classifier are applied to predict lung cancer survivability from an extensive data set with fifteen years of patient records. The purpose of the project is to verify the predictive effectiveness of the two techniques on real, historical data. Besides the performance outcome that renders J48 marginally better than the Naive Bayes technique, there is a detailed description of the data and the required pre-processing activities. The performance results confirm expectations while some of the issues that appeared during experimentation, underscore the value of having domain-specific understanding to leverage any domain-specific characteristics inherent in the data.
Heavy Traffic Optimal Resource Allocation Algorithms for Cloud Computing Clusters
Venue: arXiv cs.PF 2012
Year: 2012

Cloud computing is emerging as an important platform for business, personal and mobile computing applications. In this paper, we study a stochastic model of cloud computing, where jobs arrive according to a stochastic process and request resources like CPU, memory and storage space. We consider a model where the resource allocation problem can be separated into a routing or load balancing problem and a scheduling problem. We study the join-the-shortest-queue routing and power-of-two-choices routing algorithms with MaxWeight scheduling algorithm. It was known that these algorithms are throughput optimal. In this paper, we show that these algorithms are queue length optimal in the heavy traffic limit.