Catálogo de publicaciones - libros

Since the apparition of Simulated Annealing algorithm (SA) it has shown to be an efficient method to solve combinatorial optimization problems. Due to this, new algorithms based on two looped cycles (temperatures and Markov chain) have emerged, one of them have been called Threshold Accepting (TA). Classical algorithms based on TA usually use the same Markov chain length for each temperature cycle, these methods spend a lot of time at high temperatures where the Markov chain length is supposed to be small. In this paper we propose a method based on the neighborhood structure to get the Markov chain length in a dynamic way for each temperature cycle. We implemented two TA algorithms (classical or TACM and proposed or TADM) for SAT. Experimentation shows that the proposed method is more efficient than the classical one since it obtain the same quality of the final solution with less processing time.

We propose an efficient and accurate randomized approximation algorithm for pricing a European-Asian option on the binomial tree model. For an option with the strike price on an -step binomial tree and any positive integer , our algorithm runs in O() time with the error bound O(/) which is independent of . Our algorithm is a modification of the approximation algorithm developed by Aingworth, Motwani, and Oldham (2000) into a randomized algorithm, which improves the accuracy theoretically as well as practically.

The key issue concerning with Topic-driven Web resource discovery is how to increase the harvest rate, and the crawler should learn from the crawled online information such as the Web pages and the hyperlink structure. We address this problem by endowing a crawler with an incremental learning ability, and propose an online incremental leaning algorithm (IncL). IncL can effectively utilize the multi-feature characteristics of Web pages to enhance their link evaluation accuracy and reliability. We take into account not only a hyperlink’s positive source pages but also its negative source pages in its score that is used to rank the Web pages. Many current crawling approaches ignore the negative pages’ effect on the page ranking. Experiments show IncL gets high harvest rate.

This paper mainly focuses on a new continuous method for solving multiuser detection in CDMA using the NCP function. This approach is completely different from the relaxation method in the sense that it is an equivalent conversion. The resulting nonlinear programming problem of multiuser detection is then solved using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied, and numerical experiments show this method is very effective.

In this paper, we study how to, given a set of pre-routed requests in an all-optical network and a set of wavelengths available on each link, assign a subset of requests with maximal size such that no wavelength constraint on links is violated. While all previous studies on the wavelength assignment problem with the same objective assume the same set of wavelengths available on all links, our work does not make such an assumption. We first prove that this problem is -hard even in bus networks, and then propose some approximation algorithms for the problem with guaranteed performance ratios in networks with some special and general topologies.

In this article we propose, for any > 0, a 2(1 + )-approximation algorithm for a facility location problem with stochastic demands. At open facilities, inventory is kept such that arriving requests find a zero inventory with (at most) some pre-specified probability. The incurred costs are the expected transportation costs from the demand points to the facilities, the operating costs of the facilities and the investment in inventory.

68W25, 90B06, 60K30.

The utilization of pseudo-random proportional rule to balance between the exploitation and exploration of the search process was shown in Ant Colony System (ACS) algorithm. In ACS, this rule is governed by a parameter so-called exploiting parameter which is always set to a constant value. Besides, all ACO-based algorithm either omit this rule or applying it with a fixed value of the exploiting parameter during the runtime of algorithms. In this paper, this rule is adopted with a simple dynamical updating technique for the value of that parameter. Moreover, experimental analysis of incorporating a technique of dynamical updating for the value of this parameter into some state-of-the-art Ant-based algorithms is carried out. Also computational results on Traveling Salesman Problem benchmark instances are represented which probably show that Ant-based implementations with local search procedures gain a better performance if the dynamical updating technique is used.

In this paper, we investigate a manpower planning problem with single job type over a long planning horizon. Dynamic demands of jobs must be fulfilled by allocating enough number of regular and temporal workers and each regular worker has a minimal employment contract period. A cost objective is concerned where costs for workforce include salaries of regular and temporal workers, and recruitment and dismissal costs of regular workers. We first formulate the problem as a multi-period decision model. Then we derive several properties of the optimal solution and develop an improved dynamic programming algorithm with polynomial computational complexity. Finally, numerical results are presented to illustrate several managerial insights.

In this paper we study the set cover games when the elements are selfish agents. In this case, each element has a privately known valuation of receiving the service from the sets, , being covered by some set. Each set is assumed to have a fixed cost. We develop several approximately efficient truthful mechanisms, each of which decides, after soliciting the declared bids by all elements, which elements will be covered, which sets will provide the coverage to these selected elements, and how much each element will be charged. For set cover games when both sets and elements are selfish agents, we show that a cross-monotonic -sharing scheme does not necessarily induce a truthful mechanism.

Graph bandwidth minimization (GBM) is a classical and challenging problem in graph algorithms and combinatorial optimization. Most of existing researches on this problem have focused on unweighted graphs. In this paper, we study the bandwidth minimization problem of weighted caterpillars, and propose several algorithms for solving various types of caterpillars. More specifically, we show that the GBM problem of caterpillars with hair-length at most 2 and the GBM problem of star-shape caterpillars are NP-complete, and give a lower bound of the graph bandwidth for general weighted graphs. For caterpillars with hair-length at most 1, we present an ( log log ())-time algorithm to compute an optimal bandwidth layout, where is the total number of vertices in the graph and is the maximum edge weight. For caterpillars with hair-length at most , we give a -approximation algorithm. For arbitrary caterpillars and general graphs, we give a heuristic algorithm. Experiments show that the solutions obtained by our heuristic algorithm are roughly within a factor of log (2) of the lower bound.