The multi-objective portfolio optimization problem with fuzzy trapezoidal parameters involves a search for a subset of projects that, within the given available resources, maximizes the benefits while reducing the unc...
详细信息
The multi-objective portfolio optimization problem with fuzzy trapezoidal parameters involves a search for a subset of projects that, within the given available resources, maximizes the benefits while reducing the uncer-tainty. Traditionally, evolutionary algorithms are used to solve this problem;however, they do not exploit the locality structure of a solution or compute the values of its objective functions using the full set of n decision variables. As a result, the number of evaluations that can be computed within a fixed amount of time decreases as the size of the instances increases, yielding poor performance. This work proposes a new non-evolutionary GRASP/& UDelta;algorithm that includes a novel local search with an efficient localcomputation strategy. The use of localcomputation reduces the number of operations required to compute the values of the objective functions from O(n) to O(1). Consequently, the increment in evaluations performed in the proposed approach increases the quality of the obtained solutions, particularly as the search space grows. An experiment conducted with instances of different sizes demonstrates the overall competitiveness of GRASP/& UDelta;compared to other state-of-the-art al-gorithms. Our results show, as expected, that the differences in performance become statistically more significant when dealing with instances defined by large search spaces. These results were validated using non-parametric statistical tests.
locally finding a solution to symmetry-breaking tasks such as vertex-coloring, edge-coloring, maximal matching, maximal independent set, etc., is a long-standing challenge in distributed network computing. More recent...
详细信息
ISBN:
(纸本)9781509039333
locally finding a solution to symmetry-breaking tasks such as vertex-coloring, edge-coloring, maximal matching, maximal independent set, etc., is a long-standing challenge in distributed network computing. More recently, it has also become a challenge in the framework of centralized localcomputation. We introduce conflict coloring as a general symmetry-breaking task that includes all the aforementioned tasks as specific instantiations - conflict coloring includes all locally checkable labeling tasks from [Naor & Stockmeyer, STOC 1993]. Conflict coloring is characterized by two parameters l and d, where the former measures the amount of freedom given to the nodes for selecting their colors, and the latter measures the number of constraints which colors of adjacent nodes are subject to. We show that, in the standard local model for distributed network computing, if l/d > Delta, then conflict coloring can be solved in (O) over tilde(root Delta) + log* n rounds in n-node graphs with maximum degree Delta, where (O) over tilde ignores the polylog factors in Delta. The dependency in n is optimal, as a consequence of the Omega(log* n) lower bound by [Linial, SIAM J. Comp. 1992] for (Delta + 1)-coloring. An important special case of our result is a significant improvement over the best known algorithm for distributed (Delta + 1)-coloring due to [Barenboim, PODC 2015], which required (O) over tilde (Delta(3/4)) + log* n rounds. Improvements for other variants of coloring, including (Delta + 1)-list-coloring, (2 Delta - 1)-edge-coloring, coloring with forbidden color distances, etc., also follow from our general result on conflict coloring. Likewise, in the framework of centralized local computation algorithms (LCAs), our general result yields an LCA which requires a smaller number of probes than the previously best known algorithm for vertex-coloring, and works for a wide range of coloring problems.
暂无评论