Catálogo de publicaciones - libros

In this paper, we propose principle factor analysis method to reduce the dimensions of a high dimensional random vector in calculating portfolio’s Value at Risk. The theoretical foundation, algorithm and numerical example of the method are given. This method outperforms the principle component analysis method. Especially, the advantages of the method are marked, while the factors ’s multicollinearity is serious.

We study the problem of embedding a directed hypergraph on a ring that has applications in optical network communications. The undirected version (MCHEC) has been extensively studied. It was shown that the undirected version was NP-complete. A polynomial time approximation scheme (PTAS) for the undirected version has been developed. In this paper, we design a polynomial time approximation scheme for the directed version.

The field of supply chain management has been growing at a rapid pace in recent years, both as a research area and as a practical discipline. In this paper, we study the computational complexity of product covering problems in 3-tier supply chain models, and present natural complete problems for the classes [3] and [4] in parameterized complexity theory. This seems the first group of natural complete problems for higher levels in the parameterized intractability hierarchy (i.e., the -hierarchy), and the first precise complexity characterizations of certain optimization problems in the research of supply chain management. Our results also derive strong computational lower bounds and inapproximability for these optimization problems.

In this paper we study the problem in static ad-hoc networks with arbitrary structure, where the transmission distances can violate triangle inequality. We consider two versions of the problem, where the communication graph has to fulfill either the -strong connectivity condition () or the -broadcast condition (). Both homogeneous and non-homogeneous cases are studied. By approximating arbitrary edge-weighted graphs by paths, we present probabilistic (log )-approximation algorithms for and , which improves the previous best ratios (log loglog ) and (log loglog ), respectively [21]. The result for matches the lower bound [20] for the case that triangle inequality for transmission distance holds (which is a special case of our model). Furthermore, we show that if the network fulfils certain property and the distance power gradient is sufficiently small, the approximation ratio is improved to ((loglog )).

The Knapsack problem and integer programming are NP-complete problems. In this paper we show that the inverse problem of Knapsack problem can be solved with a pseudo-polynomial algorithm. We also show that the inverse problem of integer programming with fixed number of constraints is pseudo-polynomial.

Level of Repair Analysis (LORA) is a prescribed procedure for defence logistics support planning. For a complex engineering system containing perhaps thousands of assemblies, sub-assemblies, components, etc. organized into several levels of indenture and with a number of possible repair decisions, LORA seeks to determine an optimal provision of repair and maintenance facilities to minimize overall life-cycle costs. For a LORA problem with two levels of indenture with three possible repair decisions, which is of interest in UK and US military and which we call LORA-BR, Barros (1998) and Barros and Riley (2001) developed certain branch-and-bound heuristics. The surprising result of this paper is that LORA-BR is, in fact, polynomial-time solvable. To obtain this result, we formulate the general LORA problem as an optimization homomorphism problem on bipartite graphs, and reduce a generalization of LORA-BR, LORA-M, to the maximum weight independent set problem on a bipartite graph. We prove that the general LORA problem is NP-hard by using an important result on list homomorphisms of graphs. We introduce the minimum cost graph homomorphism problem and provide partial results. Finally, we show that our result for LORA-BR can be applied to prove that an extension of the maximum weight independent set problem on bipartite graphs is polynomial time solvable.

In this paper, we develop a new and effective schedule algebra based algorithm to determine the K-best solutions of a knapsack problem with a single constraint. Computational experience with this algorithm is also reported and it is shown to dominate both the dynamic programming and branch and bound based procedures when applied to this problem.

Consider a finite point set in -dimensional space and the polyhedral hulls it generates from constrained linear combinations of its elements. There are several interesting management problems that are modelled using these point sets and the resulting polyhedral objects. Examples include efficiency/performance evaluation, ranking and ordering schemes, stochastic scenario generation, mining for the detection of fraud, etc. These applications require the identification of frames; that is, the extreme elements of the polyhedral sets, a computationally intensive task. Traditional approaches require the solution of an LP for each point in the point set. We discuss this approach as well as a new generation of faster, output-sensitive, algorithms.

This work extends the existing parallel- and serial-episode data mining algorithms to that for parallel connection of serial (PoS) episodes. The PoS-episodes can model more general situations and preserve the sequence information as well. The PoS-episode mining algorithm can provide episode-mining users a powerful mining tool and make the episode mining more flexible. To use the PoS-episode mining algorithm, users need to decide reasonable parameters like window width and minimum frequency ratio. Concepts and methods are provided by using Web log mining as example to illustrate the applicability of the PoS-episode mining and show how to decide reasonable parameters as well as evaluate the mining process.

The idea of active networks has been emerged in recent years to increase the processing power inside the network. The intermediate nodes such as routers will be able to host mobile agents and many management tasks can be handled using autonomous mobile agents inside the network. One of the important limitations, which should be considered in active networks, is the restricted processing power of active nodes. In this paper, we define an optimal location problem for monitoring mobile agents in a scalable active network as a p-median problem, which is indeed a kind of facility location problem. The agents are responsible to monitor and manage the performance of all of the network nodes such that the total monitoring traffic overhead is minimized. Then we proposed two methods of finding an appropriate sub set of intermediate nodes for hosting mobile agents. In our first method, we have not considered the limited processing power of active nodes, which host mobile agents. In our second method, we have solved the problem so that the processing loads of host nodes do not exceed a predefined threshold. Since p-median problems are NP-complete and the search space of these problems is very large, our methods are based on genetic algorithms. We have tested our two methods for finding mobile agents optimal locations on four network topologies with different number of nodes and compared the obtained location. By this comparison, we have shown the importance of considering processing load limitation for active nodes as a parameter in choosing them as hosts of mobile agents in a scalable active network. The proposed locations in our second method eliminates the probability of CPU overload in the active nodes hosting the mobile agents and reduces the processing time required for finding the optimal locations of mobile agents.