1,721,007 research outputs found
On some Multicriteria Arborescence Problems: Complexity and Algorithms
No full textThe problems of finding an optimum arborescenceof a given digraph with respect to an objective function obtainedcombining linearly two (or more) objective functions of variouskinds are studied
Efficient algorithms for the assignment of OVSF codes in wideband CDMA
No full textThis paper proposes some novel techniques to accommodate users with different transmission rate requirements in a CDMA system which employs orthogonal variable spreading factor codes. Several static and dynamic code assignment strategies are put forth and their behavior investigated, in terms of call blocking probability and number of required call reassignments. Their efficiency in dealing with various traffic loads is demonstrated, quantitatively showing the superior performance of our dynamic scheme with respect to a so-called "optimal" code assignment strategy recently presented in the literature.This paper proposes some novel techniques to accommodate users with different transmission rate requirements in a CDMA system which employs orthogonal variable spreading factor codes. Several static and dynamic code assignment strategies are put forth and their behavior investigated, in terms of call blocking probability and number of required call reassignments. Their efficiency in dealing with various traffic loads is demonstrated, quantitatively showing the superior performance of our dynamic scheme with respect to a so-called "optimal" code assignment strategy recently presented in literature
Complexity of Spanning Tree Problems with Leaf-Dependant Objective Function
No full textWe consider the problem of finding an optimal spanning tree with respect toobjective functions which depend on the set of leaves of the tree. Weaddress 18 different such problems and determine their computational complexity.Only few of the problems examined have been given attention in theexisting literature
Solution of the cumulative assignment problem with a well-structured Tabu Search method
No full textThe Cumulative Assignment Problem is an NP-complete problem obtained by substituting the linear objective function of the classic Linear Assignment Problem, with a non-linear cumulative function. In this paper we present a first attempt to solve the Cumulative Assignment Problem with metaheuristic techniques. In particular we consider two standard techniques, namely the Simulated Annealing and the Multi-Start methods, and we describe the eXploring Tabu Search: a new structured Tabu Search algorithm which uses an iterative multi-level approach to improve the search. The new method is analyzed through extensive computational experiments and proves to be more effective than the standard methods
- …
