553 research outputs found
Efficient solutions for the Far From Most String Problem
No full textComputational molecular biology has emerged as one of the most exciting interdisciplinary
fields. It has currently benefited from concepts and theoretical results obtained
by different scientific research communities, including genetics, biochemistry, and
computer science. In the past few years it has been shown that a large number of molecular
biology problems can be formulated as combinatorial optimization problems, including
sequence alignment problems, genome rearrangement problems, string selection and comparison
problems, and protein structure prediction and recognition. This paper provides a
detailed description of string selection and string comparison problems. For finding goodquality
solutions of a particular class of string comparison molecular biology problems,
known as the far from most string problem, we propose new heuristics, including a Greedy
Randomized Adaptive Search Procedure (GRASP) and a Genetic Algorithm (GA). Computational
results indicate that these randomized heuristics find better quality solutions compared
with results produced by the best state-of-the-art heuristic approach
Spatial interaction models: facility location using game theory
No full textThis book aims to provide a comprehensive overview of facility location models that can be investigated in a game theoretical environment. Facility location theory develops the idea of locating one or more facilites optimizing suitable criteria such as minimizing transportation cost, capturing the largest market share, etc.. and a huge number of papers have been devoted to this reaserch.
In this volume we focus on situations where the location decision is faced by several decision makers, leading to a game theoretical framework in a noncooperative way, as well as in a cooperative one. Some chapters are surveys of models and methods regarding this part of the facility location using game theory, other chapters illustrate applications in dierent contexts such as economics, engineering, physics, etc. This makes the book useful for a broader audience of researchers working on theory, applications and computational aspects.
We would like to express our thanks to all the contributors of chapters and also the evaluable assistance of the Springer sta for the publication of this book
Feedback set problems
No full textIn recent years feedback set problems have been the subject of growing interest. They have found applications in many fields, including deadlock prevention, program verification, and Bayesian inference. Therefore, it is natural that in the past few years there have been intensive efforts on exact and approximation algorithms for these kinds of problems. It generalizes a number of problems, including the minimum feedback vertex (arc) set problem in both directed and undirected graphs, the subset minimum feedback vertex (arc) set problem and the graph bipartization problem, in which one must remove a minimum-weight set of vertices so that the remaining graph is bipartite. The scope of this article is to give a complete state-of-art survey of exact and approximation algorithms and to analyze a new practical heuristic method called GRASP for solving both feedback vertex and feedback arc set problems
Current Classification Algorithms for Biomedical Applications
No full textIn this study we report the advances in supervised learning methods that have been devised to analyze medical data sets. As mining of data sets produced by medical equipments is becoming an increasingly challenging task, due to the size of the databases and the gradient of their update, new methods need to provide classification models that can handle the complexity of the problems. We start describing standard methods and we show how kernel methods, incremental learning algorithms and feature reduction techniques, applied to standard classification techniques, can be successfully used to discriminate biological and medical data sets. Among existing methods, we describe those that have their foundations in the statistical learning theory and have been successfully applied to the field. We provide numerical experiments based on publicly available data sets, and discuss results in terms of classification accuracy. Finally, we draw conclusions and outline future research direction
On the chromatic number of graphs
No full textComputing the chromatic number of a graph is an NP-hard problem. For random graphs and some other classes of graphs, estimators of the expected chromatic number have been well studied. In this paper, a new 0–1 integer programming formulation for the graph coloring problem is presented. The proposed new formulation is used to develop a method that generates graphs of known chromatic number by using the KKT optimality conditions of a related continuous nonlinear program
On the chromatic number of graphs
No full textComputing the chromatic number of a graph is an NP-hard problem. For random graphs and some other classes of graphs, estimators of the expected chromatic number have been well studied. In this paper, a new 0–1 integer programming formulation for the graph coloring problem is presented. The proposed new formulation is used to develop a method that generates graphs of known chromatic number by using the KKT optimality conditions of a related continuous nonlinear program
On Very Large Maximum Clique Problems (Extended Abstract)
No full text) J. Abello Network Services Research, AT&T Labs Research, 180 Park Avenue Florham Park, NJ 07932-0971, USA e-mail: [email protected] P. M. Pardalos Center for Applied Optimization, University of Florida, 303 Weil Hall Gainesville, FL 32611, USA e-mail: [email protected] and M. G. C. Resende Information Sciences Research, AT&T Labs Research, 180 Park Avenue Florham Park, NJ 07932-0971, USA e-mail: [email protected] Abstract We present an approach to clique computations in very large multi-digraphs. We discuss graph decomposition schemes used to break up the problem into several pieces of manageable dimensions. A two-stage (out-of-memory and in-memory) greedy randomized adaptive search procedure (GRASP) for finding approximate solutions to the maximum clique problem in very large sparse graphs is presented. We experiment with this heuristic on real data sets collected in the telecomunications industry. These graphs contain on the order of millions of vertices and edges. Ke..
Neural network embeddings on corporate annual filings for portfolio selection
No full textIn recent years, there has been an increased interest from both academics and practitioners in automatically analyzing the textual part of companies’ financial reports to extract meaning rich in information for future outcomes. In particular, tracking textual changes among companies’ reports can have a large and significant impact on stock prices. This impact happens with a lag implying that investors only gradually realize the implications of the news hinted by document changes. However, the length of these documents as well as their complexity in terms of structure and language have been increasing dramatically making this process more and more difficult to perform. In this paper, we analyzed how to face this complexity by learning arbitrary dimensional vector representations for US corporate filings (10-Ks) from 1998 to 2018, exploiting and comparing different neural network embedding techniques which take into account words’ semantics through vectors proximity. We also compared their ability to capture changes associated with future risk-adjusted abnormal returns with other more commonly used approaches in literature. Finally, we propose a novel investment strategy named Semantic Similarity Portfolio (SSP) that exploits these neural network embeddings. We show that firms that do not change their 10-Ks in a semantically important way from the previous year tend to have large and statistically significant future risk-adjusted abnormal returns. We, also document an amplifying effect when we incorporate a momentum-related criterion, where the companies selected must also have had positive previous year returns. Specifically, a portfolio that buys “non-changers” based on this strategy earns up to 10% in yearly risk-adjusted abnormal returns (alpha)
Current Classification Algorithms for Biomedical Applications
No full textIn this study we report the advances in supervised learning methods that have been devised to analyze medical data sets. As mining of data sets produced by medical equipments is becoming an increasingly challenging task, due to the size of the databases and the gradient of their update, new methods need to provide classification models that can handle the complexity of the problems. We start describing standard methods and we show how kernel methods, incremental learning algorithms and feature reduction techniques, applied to standard classification techniques, can be successfully used to discriminate biological and medical data sets. Among existing methods, we describe those that have their foundations in the statistical learning theory and have been successfully applied to the field. We provide numerical experiments based on publicly available data sets, and discuss results in terms of classification accuracy. Finally, we draw conclusions and outline future research direction
Springer Optimization and Its Applications
No full textThis review proposes a proximal algorithm for difference of two monotone operators in finite dimensional real Hilbert space. Our route begins with reviewing some properties of DC (difference of convex functions) programming and DCA (DC algorithms). Next, we recall some main results about a proximal point algorithm for DC programming
- …
