With the prevalence of various social sites and the rapid development of Internet communication, the problem of team formation in social networks has aroused the enthusiasm of many scholars. Previous research concentr...
详细信息
ISBN:
(纸本)9783030000219;9783030000202
With the prevalence of various social sites and the rapid development of Internet communication, the problem of team formation in social networks has aroused the enthusiasm of many scholars. Previous research concentrates on raising the variants of this problem and most of them rely on designing approximation optimization algorithms, whose disadvantage is lacking extensibility. In this paper, we deal with the team formation problem for finding a cooperative team within a social network to perform a specific task that requires a set of skills and minimizing the communication cost among team members. In the light of its NP-hard nature, Imperialist competitive algorithm (ICA), an evolutionary algorithm for optimization inspired by the imperialistic competition, has been utilized for this problem with different ways of measuring the communication cost. We design a discrete version of ICA by introducing genetic operator in our application, imperialist mutation and imperialist crossover with similarity detection are proposed to avoid a local optimum. Comprehensive experiments on a real-world dataset indicate the performance of the ICA algorithm obtains high-quality results with the comparison of some state-of-the-art ones.
The edge searching problem is a generalization of the classical group testing problem. Chen and Hwang studied the problem of searching for many edges in a hypergraph with rank r. They provided a competitive algorithm ...
详细信息
The edge searching problem is a generalization of the classical group testing problem. Chen and Hwang studied the problem of searching for many edges in a hypergraph with rank r. They provided a competitive algorithm to identify all d defective edges in a hypergraph with d unknown. Recently, Hwang first gave a competitive algorithm to find all defective edges in a graph. Chen proposed a revised algorithm for the same problem requiring at most d left ceiling log2|E| right ceiling +d2+3d+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d \lceil \log _2 |E| \rceil + d<^>2 + 3d + 1$$\end{document} tests. In this paper, we will revisit the result proposed by Chen and give a more detailed analysis which implies that the revised algorithm actually requires at most d left ceiling log2|E| right ceiling +5d+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ d \lceil \log _2 |E| \rceil + 5d + 1$$\end{document} tests. Then we further study the edge searching problem in a hypergraph of rank r. Considering the special case of r=3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r=3$$\end{document}, we will present more efficient algorithms to identify all defective edges in hypergraphs of rank 3.
Two-sided assembly line balancing problems usually occur in plants producing large-sized high-volume products such as buses, trucks, or cars. Comparing to traditional simple assembly lines, the two-sided assembly line...
详细信息
Two-sided assembly line balancing problems usually occur in plants producing large-sized high-volume products such as buses, trucks, or cars. Comparing to traditional simple assembly lines, the two-sided assembly line can shorten the length of line, enhance the utilization of tools and fixtures, and improve the production rate of operators, etc. Whereas in a two-sided assembly line, due to a couple of constraints such as the operation direction constraint and the sequence-dependent finish time constraint, the balancing procedure is much more complex than for a simple assembly line. In this paper, besides some fundamental constraints of the two-sided assembly lines, we put forward additionally the restriction of operator number at each workstation, and take into account concurrently more constraints such as the positional constraints, zoning constraints, and the synchronous task constraints. A novel hybrid imperialist competitive algorithm (ICA) combined with the late acceptance hill-climbing (LAHC) algorithm is employed to solve the multiconstraint problem. For the evaluation of the proposed algorithm, the performance of the hybrid ICA is examined over benchmarks from the literature and compared with the LAHC algorithm and the lower bounds of the instances. Furthermore, a practical two-sided assembly line balancing problem from an engineering machinery company is solved with the proposed approach. The results confirm that the hybrid ICA can effectively shorten the line length and reduce the amount of operators for the existing two-sided assembly line.
We consider competitive algorithms for adaptive group testing problems. In the first part of the paper, we develop an algorithm with competitive constant c < 1.452 thus improving the up to now best known algorithms...
详细信息
We consider competitive algorithms for adaptive group testing problems. In the first part of the paper, we develop an algorithm with competitive constant c < 1.452 thus improving the up to now best known algorithms with constants 1.5 + epsilon from 2003. In the second part, we prove the first nontrivial lower bound for competitive constants, namely that c is always larger than 1.31.(c) 2023 Elsevier B.V. All rights reserved.
Data caching is an effective method to reduce traffic and improve the quality of service in network. Traditionally, users' requests are offloaded to the cloud for centralized computing. However, due to security an...
详细信息
Data caching is an effective method to reduce traffic and improve the quality of service in network. Traditionally, users' requests are offloaded to the cloud for centralized computing. However, due to security and privacy, these tasks are executed in the nearest server, so that the data and service needed by the task are also essential. After the task is completed, in case the next arriving request needs the same data, resulting in transmission cost, the data need to be stored for a period of time, because we know nothing about the coming request information under an online request stream. In this article, we study data caching problem by extending single data item to multiple data items among servers. About the homogeneous model and the submodular model with constraint, we propose a data caching strategy minimizing the total transfer and caching costs of the system. Moreover, we also solve the semiheterogeneous model by the anticipatory caching (AC) algorithm in Reference 21. Meanwhile we find it is more efficient for our three models in this article to improve the performance.
This paper studies the online Orthogonal Variable Spreading Factor (OVSF) code assignment problem with resource augmentation introduced by Erlebach et al. (in STACS 2004. LNCS, vol. 2996, pp. 270-281, 2004). We propos...
详细信息
This paper studies the online Orthogonal Variable Spreading Factor (OVSF) code assignment problem with resource augmentation introduced by Erlebach et al. (in STACS 2004. LNCS, vol. 2996, pp. 270-281, 2004). We propose a (1 + 1/alpha)-competitive algorithm with help of (1 + left perpendicular alpha right perpendicular) lg*h trees for the height h of the OVSF code tree and any alpha >= 1. In other words, it is a (1 + epsilon)-competitive algorithm with help of (1 + left perpendicular 1/epsilon right perpendicular)lg*h trees for any constant 0 < epsilon <= 1. In the case of alpha = 1 (or epsilon = 1), we obtain a 2-competitive algorithm with 2 lg* h trees, which substantially improves the previous resource of 3h/8 + 2 trees shown by Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358-367, 2009). In another aspect, if it is not necessary to bound the incurred cost for individual requests to a constant, an amortized (4/3+ delta)-competitive algorithm with (11/4 + 4/(3 delta)) trees for any 0 < delta <= 4/3 is also designed in Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358-367, 2009). The algorithm in this paper gives us a new trade-off between the competitive ratio and the resource augmentation when alpha >= 3 (or epsilon <= 1/3), although the incurred cost for individual requests is bounded to a constant.
Although Total Unduplicated Reach and Frequency (TURF) analysis has repeatedly demonstrated value in a variety of market research applications, TURF analyses on large problem sizes have historically either been unacce...
详细信息
Although Total Unduplicated Reach and Frequency (TURF) analysis has repeatedly demonstrated value in a variety of market research applications, TURF analyses on large problem sizes have historically either been unacceptably slow or approximate in their solutions. To resolve this dilemma, we begin by identifying and explaining the principle of non-synergy that is present in all situations for which TURF analyses apply. We use this principle to provide a competitive algorithm, called eTURF, for determining exact solutions to large TURF problems in reasonable time and we provide an illustrative example to demonstrate how eTURF can obtain considerable speed improvements. We then discuss how eTURF is useful not only in terms of providing optimal solutions but also in providing a metric by which to gauge the quality of heuristic TURF solutions. (C) 2011 Elsevier Ltd. All rights reserved.
Let G be a graph, ψ G be a source node and ψ G be a target node. The sequence of adjacent nodes (graph walk) visited by a routing algorithm is a c-competitive route if its length in G is at most c times the length o...
详细信息
Due to the frequent arrivals of real-time vessels beyond those being well planned in many container terminals, this paper studies an online over-list model of integrated allocation of berths and quay cranes in a conta...
详细信息
ISBN:
(纸本)9783319266268;9783319266251
Due to the frequent arrivals of real-time vessels beyond those being well planned in many container terminals, this paper studies an online over-list model of integrated allocation of berths and quay cranes in a container terminal. We consider a hybrid berth which consists of three adjacent small berths together with five quay cranes. The objective is to minimize the makespan or the maximum completion time of container vessels. Our focus is the case with two types of vessels in size which require different numbers of berths and QCs in service, and our main contribution is an optimal 4/3-competitive online algorithm.
In this paper, we proposed a novel localization algorithm in indoor Wireless Local Area Network (WLAN) environment. First of all, to conduct the Received Signal Strength (RSS) preprocessing, we eliminate the RSS outli...
详细信息
ISBN:
(纸本)9781479987955
In this paper, we proposed a novel localization algorithm in indoor Wireless Local Area Network (WLAN) environment. First of all, to conduct the Received Signal Strength (RSS) preprocessing, we eliminate the RSS outliers based on the density function of the difference of RSS. Second, to overcome the problem of the manual selection of the cluster number, as well as the number of the nearest neighbors in K nearest neighbor (KNN) algorithm, we propose to use the competitive Agglomeration (CA) algorithm to achieve the localization. Third, the extensive experimental results conducted in an actual Non-line-of-sight (NLOS) indoor WLAN environment, as well as in a simulated Line-of-sight (LOS) environment prove that the proposed approach performs well in localization accuracy.
暂无评论