Catálogo de publicaciones - libros

A new method for information retrieval based on relative entropy with different smoothing methods has been presented in this paper. The method builds a query language model and document language models respectively for the query and the documents. We rank the documents according to the relative entropies of the estimated document language models with respect to the estimated query language model. While estimating a document language, the efficiency of the smoothing method is considered, we select three popular and relatively efficient methods to smooth the document language model. The feedback documents are used to estimate a query model by the approach that we assume that the feedback documents are generated by a combined model in which one component is the feedback document language model and the other is the collection language model. Experimental results show that the method is effective and performs better than the basic language modeling approach.

We show how the process of passengers boarding an airplane and the process of optimal I/O scheduling to a disk drive with a linear seek function can be asymptotically modeled by 2-dimensional space-time geometry. We relate the space-time geometry of the models to important quantities such as total boarding time and total service time. We show that the efficiency of a boarding policy depends crucially on a parameter which depends on the interior design of the airplane. Policies which are good for small values of are bad for large values of and vice versa.

There are many non-probabilistic factors that affect the financial markets. In this paper, the possibilistic mean-variance model of portfolio selection is presented under the assumption that the returns of assets are fuzzy numbers, which can better integrate the experts’ knowledge and the managers’ subjective opinions to compare with conventional probabilistic mean-variance methodology. The possibilistic efficient frontier is derived explicitly when short sales are not allowed on all risky assets and a risk-free asset.

Differentiated service (DiffServ) is a mechanism to provide the Quality of Service (QoS) with a certain performance guarantee. In this paper, we study how to design DiffServ multicast when the participants (, relay links) are selfish. We assume that each link is associated with a cost coefficient such that the cost of to provide a multicast service with bandwidth demand is · . We first show that a previous approximation algorithm does not directly induce a truthful mechanism. We then give a new polynomial time 8-approximation algorithm to construct a DiffServ multicast tree. Based on this tree, we design a truthful mechanism for DiffServ multicast, , we give a polynomial-time computable payment scheme to compensate all chosen relay links such that each link maximizes its profit when it reports its privately cost coefficient truthfully.

Based on the unidirectional conversion model, we investigate a practical buy-and-hold trading problem. This problem is useful for long-term investors, we use competitive analysis and game theory to design some trading rules in the securities markets. We present an online algorithm, Mixed Strategy, for the problem and prove its competitive ratio , where is the trading horizon and is the daily fluctuations of securities prices. The Dynamic-Mixed Strategy is also presented to further reduce the competitive ratio. An investing example is simulated with the Mixed Strategy and Dollar Average Strategy based on the actual market data.

Given a pair of non-negative integers and , (,) denotes a square lattice graph with a vertex set {0,1,2,..., – 1} × {0,1,2,..., – 1}, where a pair of two vertices is adjacent if and only if the distance is equal to 1. A triangular lattice graph (,) has a vertex set {( + ) |  ∈ {0,1,2,..., − 1},  ∈ {0,1,2,..., − 1}} where , and an edge set consists of a pair of vertices with unit distance. Let (,) and (,) be the th power of the graph (,) and (,), respectively. Given an undirected graph = (,) and a non-negative vertex weight function , a multicoloring of is an assignment of colors to such that each vertex ∈ admits () colors and every adjacent pair of two vertices does not share a common color.

In this paper, we show necessary and sufficient conditions that [∀ , (,) is perfect] and/or [∀ , (,) is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring ((,),) and ((,),).

Link-bandwidth utilization and flow information are obviously critical for numerous network management tasks. The problem of efficiently monitoring the network flowing based on flow-conservation could be reduced to Weak Vertex Cover problem, which is NP-hard. In this paper, using the primal-dual method, we give an approximation algorithm with approximation ratio 2 to solve the problem. It is a near-optimal algorithm as it is very difficult to get an approximation algorithm with approximation ratio lower than 2 for Weak Vertex Cover problem. The effectiveness of our monitoring algorithm is validated by simulations evaluation over a wide range of network topologies. The practices indicate that our work is valuable to solve Weak Vertex Cover problem and its application in network management.

Usually network attackers conceal their real attacking paths by establishing interactive connections along a series of intermediate hosts (stepping stones) before they attack the final target. We propose two methods for detecting stepping stones by actively perturbing inter-packet delay of connections. Within the attacker’s perturbation range, the average value of the packets in the detecting window is set to increase periodically. The methods can construct correlations in attacking connection chains by analyzing the change of the average value of the inter-packet delay between the two connection chains. The methods can reduce the complexity of correlation computations and improve the efficiency of detecting stepping stones.

This paper considers due date assignment and sequencing for multiple jobs in a single machine shop. The processing time of each job is assumed to be uncertain and is characterized by a mean and a variance with no knowledge of the entire distribution. The objective is to minimize the combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. The earliness and tardiness penalties and the penalty associated with long due date assignment are all expressed quadratic functions. Heuristic procedures are developed for the objective function. The due dates and sequences obtained by these procedures depend not only on means but also variances of the job processing times. Our numerical examples indicate that the variance information of job processing times can be useful for sequencing and due date assignment decisions. In addition, the performance of the procedures proposed in this paper are robust and stable with respect to job processing time distributions.

In this paper we study the computational problem of arbitrage in a frictional market with a finite number of bonds and finite and discrete times to maturity. Types of frictions under consideration include fixed and proportional transaction costs, bid-ask spreads, taxes, and upper bounds on the number of units for transaction. We obtain some negative result on computational difficulty in general for arbitrage under those frictions: It is -complete to identify whether there exists a cash-and-carry arbitrage transaction and it is -hard to find an optimal cash-and-carry arbitrage transaction.