Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Let \(G = (V, E, w)\) be an undirected connected edge-weighted graph, where V is the n-vertices set, E is the m-edges set, and \(w: E \rightarrow \mathbb {R}^+\) is a positive edge-weight function. Given \(G = (V, E, w)\) , a subset \(X \subseteq V\) of p terminals, and a subset \(F \subseteq E\) of candidate edges, the Absolute 1-Center Problem (A1CP) aims to find a point on some edge in F to minimize the distance from it to X. This paper revisits this classic and polynomial-time solvable problem from a novel perspective and finds some new and nontrivial properties of it, with the highlight of establishing the relationship between the A1CP and the saddle point of distance matrix. In this paper, we prove that an absolute 1-center is just a vertex 1-center if the all-pairs shortest paths distance matrix from the vertices covered by the candidate edges in F to X has a (global) saddle point. Furthermore, we define the local saddle point of edge and demonstrate that we can sift the candidate edge having a local saddle point. By incorporating the method of sifting edges into the framework of the well-known Kariv and Hakimi’s algorithm, we develop an \(O(m + p m^*+ n p \log p)\) -time algorithm for A1CP, where \(m^*\) is the number of the remaining candidate edges. Specifically, it takes \(O(m^*n + n^2 \log n)\) time to apply our algorithm to the classic A1CP when the distance matrix is known and \(O(m n + n^2 \log n)\) time when the distance matrix is unknown, which are smaller than \(O(mn + n^2 \log n)\) and \(O(mn + n^3)\) of Kariv and Hakimi’s algorithm, respectively. PubDate: 2022-05-13

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A hypergraph has a complex structure, which is why some re- searchers seek to transform the hypergraph into a graph. In this paper, we present two corresponding graphs for each hypergraph and naming them in the Clique graph and the Persian graph. They have a simpler structure than the graph, and it is easier to work with these graphs. Using these graphs, we are looking for minimal spanning hypertree for the hypergraph. PubDate: 2022-05-12

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Research in assembly optimisation is presently inclined towards integrative measures. Several benefits of simultaneously optimised Assembly Sequence Planning (ASP) and Assembly Line Balancing (ALB) have been highlighted by researchers to have better solution quality, shorter time-to-market, and minimalised error during planning. Recently, several efforts have been made to realise integrated assembly optimisation. However, none of the published research considered the two-sided assembly line problem. This paper presents an integrated ASP and ALB optimisation in a two-sided assembly environment (2S-ASPLB), which is mainly adopted in automotive assembly process. In this study, the 2S-ASPLB problem was formulated and optimised using Multi-Objective Multi-Verse Optimiser (MOMVO) by considering line efficiency, reorientation penalty, and tool change as the optimisation objectives. The computational experiments were conducted in a few stages, beginning with the identification of the best decoding approach for 2S-ASPLB. Next, the best MOMVO coefficient was studied, followed by comparing MOMVO performance with well-established multi-objective optimisation algorithms. Finally, a case study problem was presented to demonstrate applicability of the proposed model and algorithm in real-life problem. The results indicated that the priority factor (PF) decoding approach had better performance compared with others. Meanwhile, in comparison with well-established algorithms, MOMVO performed better in convergence and solution distribution. The case study results indicated the applicability of proposed 2S-ASPLB model and algorithm to improve line efficiency in assembly line. The main contribution of the research is a new 2S-ASPLB model and optimisation scheme, which can assist manufacturer in designing better assembly layout. PubDate: 2022-05-11

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. Scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081. PubDate: 2022-05-11

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Let \({\mathcal {T}}=\{T_1,T_2,\ldots ,T_k\}\) be a set of \(k\geqslant 2\) spanning trees in a graph G. The k spanning trees are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices x and y in any two trees have neither vertex nor edge in common except for x and y. Particularly, \({\mathcal {T}}\) is called a dual-CIST (resp. tri-CIST) provided \(k=2\) (resp. \(k=3\) ). From an algorithmic point of view, the problem of finding a dual-CIST in a given graph is known to be NP-hard. For data transmission applications in reliable networks, the existence of a dual-CIST can provide a configuration of fault-tolerant routing called protection routing. The presence of a tri-CIST can enhance the dependability of transmission and carry out secure message distribution for confidentiality. Recently, the construction of a dual-CIST has been proposed in a shuffle-cube \(SQ_n\) , which is an innovative hypercube-variant network that possesses both short diameter and connectivity advantages. This paper uses the CIST-partition technique to construct a tri-CIST of \(SQ_6\) , and shows that the diameters of three CISTs are 22, 22, and 13. Then, by the hierarchical structure of \(SQ_n\) , we propose a recursive algorithm for constructing a tri-CIST for high-dimensional shuffle-cubes. When \(n\geqslant 10\) , the diameters of \(T_i\) , \(i=1,2,3\) , we constructed for \(SQ_n\) are as follows: \(2n+11\) , \(2n+9\) , and \(2n+1\) . PubDate: 2022-05-09

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A single trusted entity known as a Key Server is in charge of key generation, distribution, and management in centralized key management schemes. To prevent eavesdropping and protect the exchange content, a group key is used to encrypt the group communication. This management mechanism is typically based on a binary tree structure. When the membership of a group changes dynamically, the group key must be changed, triggering a certain updated cost. This paper addresses an important problem in centralized dynamic group key management. It consists in finding a set of leaf nodes in a binary key tree to insert new members with minimal insertion cost and keeping the tree as balanced as possible. The two mentioned important objectives are combined into a unified (deterministic) optimization model whose objective function contains discontinuous step functions with binary variables, which is known to be NP-hard. We then reformulate the problem as a combinatorial optimization program with continuous objective by introducing new binary variables. Applying penalty techniques, it results in a standard DC (Difference of Convex functions) program that can be solved efficiently by DCA (DC algorithm). Besides, the insertion nodes must be the leaf nodes, we introduce a two-step algorithm to reduce the model complexity: the first is to find the set of leaf nodes, while the second is to solve the simplified optimization problem. Numerical experiments have been studied intensively to justify the merit of our proposed model as well as the corresponding DCA. PubDate: 2022-05-06

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Dynamic multi-objective optimization algorithms are used as powerful methods for solving many problems worldwide. Diversity, convergence, and adaptation to environment changes are three of the most important factors that dynamic multi-objective optimization algorithms try to improve. These factors are functions of exploration, exploitation, selection and adaptation operators. Thus, effective operators should be employed to achieve a robust dynamic optimization algorithm. The algorithm presented in this study is known as spread-based dynamic multi-objective algorithm (SBDMOA) that uses bi-directional mutation and convex crossover operators to exploit and explore the search space. The selection operator of the proposed algorithm is inspired by the spread metric to maximize diversity. When the environment changed, the proposed algorithm removes the dominated solutions and mutated all the non-dominated solutions for adaptation to the new environment. Then the selection operator is used to select desirable solutions from the population of non-dominated and mutated solutions. Generational distance, spread, and hypervolume metrics are employed to evaluate the convergence and diversity of solutions. The overall performance of the proposed algorithm is evaluated and investigated on FDA, DMOP, JY, and the heating optimization problem, by comparing it with the DNSGAII, MOEA/D-SV, DBOEA, KPEA, D-MOPSO, KT-DMOEA, Tr-DMOEA and PBDMO algorithms. Empirical results demonstrate the superiority of the proposed algorithm in comparison to other state-of-the-art algorithms. PubDate: 2022-05-06

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The matching game is a cooperative profit game defined on an edge-weighted graph, where the players are the vertices and the profit of a coalition is the maximum weight of matchings in the subgraph induced by the coalition. A population monotonic allocation scheme is a collection of rules defining how to share the profit among players in each coalition such that every player is better off when the coalition expands. In this paper, we study matching games and provide a necessary and sufficient characterization for the existence of population monotonic allocation schemes. Our characterization implies that whether a matching game admits population monotonic allocation schemes can be determined efficiently. PubDate: 2022-05-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We consider cooperatives games (TU-games) enriched by a system of a priori unions and a communication forest graph which are independent from each other. These two structures reflect the limitations of cooperation possibilities. In this framework, we introduce four Owen-type allocation rules, which are defined by a two-step application of an allocation rule à la Owen (in: Henn R, Moeschlin O (eds) Essays in mathematical economics and game theory, Springer, Berlin, 1977) to TU-games with a priori unions where the TU-game is replaced by Myerson’s (Math Oper Res 2:225–229, 1977) graph-restricted TU-game. The four possibilities arise by applying, at each step, either the Myerson value (Myerson 1977) or the average tree solution (Herings et al. in Games Econ Behav 62:77–92, 2008). Our main result offers comparable axiomatizations of these four allocation rules. PubDate: 2022-05-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The adjacent vertex distinguishing edge coloring of a graph G is a proper edge coloring in which each pair of adjacent vertices is assigned different color sets. The smallest number of colors for which G has such a coloring is denoted by \(\chi '_a(G)\) . An important conjecture due to Zhang et al. (Appl Math Lett 15:623–626, 2002) asserts that \(\chi '_a(G)\le \Delta (G)+2\) for any connected graph G with order at least 6. By applying the discharging method, we show that this conjecture is true for any IC-planar graph G with \(\Delta (G)\ge 16\) . PubDate: 2022-05-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper, equilibrium strategies and optimal balking strategies of customers in a constant retrial queue with multiple vacations and the N-policy under two information levels, respectively, are investigated. We assume that there is no waiting area in front of the server and an arriving customer is served immediately if the server is idle; otherwise (the server is either busy or on a vacation) it has to leave the system to join a virtual retrial orbit waiting for retrials according to the FCFS rules. After a service completion, if the system is not empty, the server becomes idle, available for serving the next customer, either a new arrival or a retried customer from the virtual retrial orbit; otherwise (if the system is empty), the server starts a vacation. Upon the completion of a vacation, the server is reactivated only if it finds at least N customers in the virtual orbit; otherwise, the server continues another vacation. We study this model at two levels of information, respectively. For each level of information, we obtain both equilibrium and optimal balking strategies of customers, and make corresponding numerical comparisons. Through Particle Swarm Optimization (PSO) algorithm, we explore the impact of parameters on the equilibrium and social optimal thresholds, and obtain the trend in changes, as a function of system parameters, for the optimal social welfare, which provides guiding significance for social planners. Finally, by comparing the social welfare under two information levels, we find that whether the system information should be disclosed to customers depends on how to maintain the growth of social welfare. PubDate: 2022-05-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Multiprocessor open shop makes a generalization to classical open shop by allowing parallel machines for the same task. Scheduling of this shop environment to minimize the makespan is a strongly NP-Hard problem. Despite its wide application areas in industry, the research in the field is still limited. In this paper, the proportionate case is considered where a task requires a fixed processing time independent of the job identity. A novel highly efficient solution representation is developed for the problem. An ant colony optimization model based on this representation is proposed with makespan minimization objective. It carries out a random exploration of the solution space and allows to search for good solution characteristics in a less time-consuming way. The algorithm performs full exploitation of search knowledge, and it successfully incorporates problem knowledge. To increase solution quality, a local exploration approach analogous to a local search, is further employed on the solution constructed. The proposed algorithm is tested over 100 benchmark instances from the literature. It outperforms the current state-of-the-art algorithm both in terms of solution quality and computational time. PubDate: 2022-05-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study undirected multiple graphs of any natural multiplicity \(k>1\) . There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or \((k+1)\) vertices, correspondingly. The linked edges should be used simultaneously. The multiple tree is a multiple graph with no multiple cycles. The number of edges may be different for multiple trees with the same number of vertices. We prove lower and upper bounds on the number of edges in an arbitrary multiple tree. Also we consider spanning trees of an arbitrary multiple graph. Special interest is paid to the case of complete spanning trees. Their peculiarity is that a multiple path joining any two selected vertices exists in the tree if and only if such a path exists in the initial graph. We study the properties of complete spanning trees and the problem of finding the minimum complete spanning tree of a weighted multiple graph. PubDate: 2022-05-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper considers the bandwidth reduction problem for large-scale sparse matrices in serial computations. A heuristic for bandwidth reduction reorders the rows and columns of a given sparse matrix. Thus, the method places entries with a nonzero value as close to the main diagonal as possible. Bandwidth optimization is a critical issue for many scientific and engineering applications. This manuscript proposes two heuristics for the bandwidth reduction of large-scale matrices. The first is a variant of the Fast Node Centroid Hill-Climbing algorithm, and the second is an algorithm based on the iterated local search metaheuristic. This paper then experimentally compares the solutions yielded by the new reordering algorithms with the bandwidth solutions delivered by state-of-the-art heuristics for the problem, including tests on large-scale problem matrices. A considerable number of results for a range of realistic test problems showed that the performance of the two new algorithms compared favorably with state-of-the-art heuristics for bandwidth reduction. Specifically, the variant of the Fast Node Centroid Hill-Climbing algorithm yielded the overall best bandwidth results. PubDate: 2022-05-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper, we introduce a novel interpreting framework that learns an interpretable model based on an ontology-based sampling technique to explain agnostic prediction models. Different from existing approaches, our interpretable algorithm considers contextual correlation among words, described in domain knowledge ontologies, to generate semantic explanations. To narrow down the search space for explanations, which is exponentially large given long and complicated text data, we design a learnable anchor algorithm to better extract local and domain knowledge-oriented explanations. A set of regulations is further introduced, combining learned interpretable representations with anchors and information extraction to generate comprehensible semantic explanations. To carry out an extensive experiment, we first develop a drug abuse ontology (DAO) on a drug abuse dataset on the Twittersphere, and a consumer complaint ontology (ConsO) on a consumer complaint dataset, especially for interpretable ML. Our experimental results show that our approach generates more precise and more insightful explanations compared with a variety of baseline approaches. PubDate: 2022-04-26

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Given a simple graph \(G=(V,E)\) , a subset of E is called a triangle cover if it intersects each triangle of G. Let \(\nu _t(G)\) and \(\tau _t(G)\) denote the maximum number of pairwise edge-disjoint triangles in G and the minimum cardinality of a triangle cover of G, respectively. Tuza (in: Finite and infinite sets, proceedings of Colloquia Mathematica Societatis, Janos Bolyai, p 888, 1981) conjectured in 1981 that \(\tau _t(G)/\nu _t(G)\le 2\) holds for every graph G. In this paper, we consider Tuza’s Conjecture on dense random graphs. Under \(\mathcal {G}(n,p)\) model with a constant p, we prove that the ratio of \(\tau _t(G)\) and \(\nu _t(G)\) has the upper bound close to 1.5 with high probability. Furthermore, the ratio 1.5 is nearly the best result when \(p\ge 0.791\) . In some sense, on dense random graphs, these conclusions verify Tuza’s Conjecture. PubDate: 2022-04-25

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The minimum dominating set of graph has been widely used in many fields, but its solution is NP-hard. The complexity and approximation accuracy of existing algorithms need to be improved. In this paper, we introduce rough set theory to solve the dominating set of undirected graph. First, the adjacency matrix of undirected graph is used to establish an induced decision table, and the minimum dominating set of undirected graph is equivalent to the minimum attribute reduction of its induced decision table. Second, based on rough set theory, the significance of attributes (i.e., vertices) based on the approximate quality is defined in induced decision table, and a heuristic approximation algorithm of minimum dominating set is designed by using the significance of attributes (i.e., vertices) as heuristic information. This algorithm uses forward and backward search mechanism, which not only ensures to find a minimal dominating set, but also improves the approximation accuracy of minimum dominating set. In addition, a cumulative strategy is used to calculate the positive region of induced decision table, which effectively reduces the computational complexity. Finally, the experimental results on public datasets show that our algorithm has obvious advantages in running time and approximation accuracy of the minimum dominating set. PubDate: 2022-04-24

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Motivated by the practical applications in solving plenty of important combinatorial optimization problems, this paper investigates the Budgeted k-Submodular Maximization problem defined as follows: Given a finite set V, a budget B and a k-submodular function \(f: (k+1)^V \mapsto \mathbb {R}_+\) , the problem asks to find a solution \(\mathbf{s }=(S_1, S_2, \ldots , S_k) \in (k+1)^V \) , in which an element \(e \in V\) has a cost \(c_i(e)\) when added into the i-th set \(S_i\) , with the total cost of \(\mathbf{s }\) that does not exceed B so that \(f(\mathbf{s })\) is maximized. To address this problem, we propose two single pass streaming algorithms with approximation guarantees: one for the case that an element e has only one cost value when added to all i-th sets and one for the general case with different values of \(c_i(e)\) . We further investigate the performance of our algorithms in two applications of the problem, Influence Maximization with k topics and sensor placement of k types of measures. The experiment results indicate that our algorithms can return competitive results but require fewer the number of queries and running time than the state-of-the-art methods. PubDate: 2022-04-18

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In the multiprocessor scheduling problem to minimize the total job completion time, an optimal schedule can be obtained by the shortest processing time rule and the completion time of each job in the schedule can be used as a guarantee for scheduling revenue. However, in practice, some jobs will not arrive at the beginning of the schedule but are delayed and their delayed arrival times are given to the decision-maker for possible rescheduling. The decision-maker can choose to reject some jobs in order to minimize the total operational cost that includes three cost components: the total rejection cost of the rejected jobs, the total completion time of the accepted jobs, and the penalty on the maximum tardiness for the accepted jobs, for which their completion times in the planned schedule are their virtual due dates. This novel rescheduling problem generalizes several classic NP-hard scheduling problems. We first design a pseudo-polynomial time dynamic programming exact algorithm and then, when the tardiness can be unbounded, we develop it into a fully polynomial time approximation scheme. The dynamic programming exact algorithm has a space complexity too high for truthful implementation; we propose an alternative to integrate the enumeration and the dynamic programming recurrences, followed by a depth-first-search walk in the reschedule space. We implemented the alternative exact algorithm in C and conducted numerical experiments to demonstrate its promising performance. PubDate: 2022-04-08

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract With the booming development of sharing economy, decision makers must consider the effect when making decisions with uncertain demands. In the leasing problem, people are faced with several leasing options. Participating in the shared leasing option can reduce the cost of the lessee, which makes it a good choice. This paper considers the online leasing option under sharing economy. By applying competitive analysis to the two-option online leasing problem, the optimal competitive ratios of the deterministic and randomized strategies with market interest rate are obtained, respectively. The theoretical results show that the strategies’ competitive performance is improved under sharing economy. Furthermore, numerical examples are performed to illustrate that considering the shared option has a significant influence on the two-option online leasing problem. PubDate: 2022-04-04