Abstract: Abstract Let \(\mathcal {H}=(V,\mathcal {E})\) be a hypergraph with maximum edge size \(\ell \) and maximum degree \(\varDelta \) . For a given positive integers \(b_v\) , \(v\in V\) , a set multicover in \(\mathcal {H}\) is a set of edges \(C \subseteq \mathcal {E}\) such that every vertex v in V belongs to at least \(b_v\) edges in C. Set multicover is the problem of finding a minimum-cardinality set multicover. Peleg, Schechtman and Wool conjectured that for any fixed \(\varDelta \) and \(b:=\min _{v\in V}b_{v}\) , the problem of set multicover is not approximable within a ratio less than \(\delta :=\varDelta -b+1\) , unless \(\mathcal {P}=\mathcal {NP}\) . Hence it’s a challenge to explore for which classes of hypergraph the conjecture doesn’t hold. We present a polynomial time algorithm for the set multicover problem which combines a deterministic threshold algorithm with conditioned randomized rounding steps. Our algorithm yields an approximation ratio of \(\max \left\{ \frac{148}{149}\delta , \left( 1- \frac{ (b-1)e^{\frac{\delta }{4}}}{94\ell } \right) \delta \right\} \) for \(b\ge 2\) and \(\delta \ge 3\) . Our result not only improves over the approximation ratio presented by El Ouali et al. (Algorithmica 74:574, 2016) but it’s more general since we set no restriction on the parameter \(\ell \) . Moreover we present a further polynomial time algorithm with an approximation ratio of \(\frac{5}{6}\delta \) for hypergraphs with \(\ell \le (1+\epsilon )\bar{\ell }\) for any fixed \(\epsilon \in [0,\frac{1}{2}]\) , where \(\bar{\ell }\) is the average edge size. The analysis of this algorithm relies on matching/covering duality due to Ray-Chaudhuri (1960), which we convert into an approximative form. The second performance disprove the conjecture of Peleg et al. for a large subclass of hypergraphs. PubDate: 2021-01-09

Abstract: Abstract An offset discretization of a set \(X \subset {\mathbb {R}}^n\) is obtained by taking the integer points inside a closed neighborhood of X of a certain radius. In this work we determine a minimum threshold for the offset radius, beyond which the discretization of an arbitrary (possibly disconnected) set is always connected. The obtained results hold for a broad class of disconnected subsets of \({\mathbb {R}}^n\) and generalize several previous results. We also extend our results to infinite discretizations of unbounded subsets of \({\mathbb {R}}^n\) and consider certain algorithmic aspects. The obtained results can be applied to component topology preservation as well as extracting geometric features and connectivity control of very large object discretizations. PubDate: 2021-01-09

Abstract: Abstract The Minimum Dominating Set (MDS) problem is one of the well-studied problems in computer science. It is well-known that this problem is \(\mathsf {NP}\) -hard for simple geometric objects; unit disks, axis-parallel unit squares, and axis-parallel rectangles to name a few. An interesting variation of the MDS problem with rectangles is when there exists a straight line that intersects each of the given rectangles. In the recent past researchers have studied the maximum independent set, minimum hitting set problems on this setting with different geometric objects. We study the MDS problem with axis-parallel rectangles, unit-height rectangles, and unit squares in the plane. These geometric objects are constrained to be intersected by a straight line. For axis-parallel rectangles, we prove that this problem is \(\mathsf {NP}\) -hard. When the objects are axis-parallel unit squares, we present a polynomial time algorithm using dynamic programming. We provide a polynomial time algorithm for unit-height rectangles as well. For unit squares that touch the straight line at a single point from either side of the straight line, we show that there is an \(O(n\log n)\) -time algorithm. PubDate: 2021-01-08

Abstract: Abstract A secure dominating set of a graph G is a dominating set S satisfying that for every vertex \(v\in V(G){\setminus } S\) there exists a neighbour \(u\in S\) of v such that \((S\cup \{v\}){\setminus } \{u\}\) is a dominating set as well. The secure domination number, denoted by \(\gamma _s(G)\) , is the minimum cardinality among all secure dominating sets of G. This concept was introduced in 2005 by Cockayne et al. and studied further in a number of works. The problem of computing the secure domination number is NP-Hard. This suggests finding the secure domination number for special classes of graphs or obtaining tight bounds on this invariant. The aim of this work is to obtain closed formulas for the secure domination number of rooted product graphs. We show that for any graph G of order n(G) and any graph H with root v, the secure domination number of the rooted product graph \(G\circ _vH\) satisfies one of the following three formulas, \(\gamma _{s}(G\circ _vH)=n(G)(\gamma _{s}(H)-1)+\gamma (G)\) , \(\gamma _{s}(G\circ _vH)= n(G)(\gamma _{s}(H)-1)+\gamma _{s}(G)\) or \(\gamma _{s}(G\circ _vH)= n(G)\gamma _{s}(H)\) , where \(\gamma (G)\) denotes the domination number of G. We also characterize the graphs that satisfy each of these expressions. As a particular case of the study, we derive the corresponding results for corona graphs. PubDate: 2021-01-07

Abstract: Abstract An essential aspect of a closed-loop supply chain (CLSC) involves its optimization. In this context, systematizing the publications on optimization methods applied in CLSC constitutes this research's primary objective. In this sense, a comprehensive literature review was carried out on 354 papers published from January 2008 to October 2020 to find future directions involving CLSC optimization. It was found stochastic methods are the primary approach in the studies regarding CLSC optimization, being applied in 27.68% of the publications investigated, while hybrid methods appeared in 21.75%, and deterministic methods were used in 20.62%. It was verified that 49.71% of the publications were related exclusively to strategic decisions concerning organizational decision-making levels, 22.03% analyzed tactical decisions, and 13.56% studied operational aspects. Regarding the sustainability dimensions, it was found that only the economic dimension was investigated in 70.62% of the analyzed publications. The three dimensions (economic, environmental, and social) were investigated simultaneously in only 6.21% of the publications. As the main conclusion, a lack of research covering the whole spectrum of the CLSC environment was found, comprising the various levels of organization decisions and sustainability dimensions of the triple bottom line. PubDate: 2021-01-07

Abstract: Abstract We focus on energy complexity, a Boolean function measure related closely to Boolean circuit design. Given a circuit \(\mathcal {C}\) over the standard basis \(\{\vee _2,\wedge _2,\lnot \}\) , the energy complexity of \(\mathcal {C}\) , denoted by \({{\,\mathrm{EC}\,}}(\mathcal {C})\) , is the maximum number of its activated inner gates over all inputs. The energy complexity of a Boolean function f, denoted by \({{\,\mathrm{EC}\,}}(f)\) , is the minimum of \({{\,\mathrm{EC}\,}}(\mathcal {C})\) over all circuits \(\mathcal {C}\) computing f. Recently, K. Dinesh et al. (International computing and combinatorics conference, Springer, Berlin, 738–750, 2018) gave \({{\,\mathrm{EC}\,}}(f)\) an upper bound by the decision tree complexity, \({{\,\mathrm{EC}\,}}(f)=O({{\,\mathrm{D}\,}}(f)^3)\) . On the input size n, They also showed that \({{\,\mathrm{EC}\,}}(f)\) is at most \(3n-1\) . For the lower bound side, they showed that \({{\,\mathrm{EC}\,}}(f)\ge \frac{1}{3}{{\,\mathrm{psens}\,}}(f)\) , where \({{\,\mathrm{psens}\,}}(f)\) is called positive sensitivity. A remained open problem is whether the energy complexity of a Boolean function has a polynomial relationship with its decision tree complexity. Our results for energy complexity can be listed below. For the lower bound, we prove the equation that \({{\,\mathrm{EC}\,}}(f)=\varOmega (\sqrt{{{\,\mathrm{D}\,}}(f)})\) , which answers the above open problem. For upper bounds, \({{\,\mathrm{EC}\,}}(f)\le \min \{\frac{1}{2}{{\,\mathrm{D}\,}}(f)^2+O({{\,\mathrm{D}\,}}(f)),n+2{{\,\mathrm{D}\,}}(f)-2\}\) holds. For non-degenerated functions, we also provide another lower bound \({{\,\mathrm{EC}\,}}(f)=\varOmega (\log {n})\) where n is the input size. We also discuss the energy complexity of two specific function classes, \(\mathtt {OR}\) functions and \(\mathtt {ADDRESS}\) functions, which implies the tightness of our two lower bounds respectively. In addition, the former one answers another open question in Dinesh et al. (International computing and combinatorics conference, Springer, Berlin, 738–750, 2018) asking for non-trivial lower bound for energy complexity of \(\mathtt {OR}\) functions. PubDate: 2021-01-07

Abstract: Abstract In this paper, we show several results about the strict submodularity of the influence spread in a social network with general threshold model if at each node, the threshold function is strictly increasing and strictly submodular. PubDate: 2021-01-06

Abstract: Abstract Based on the sharing economy, crowdsourcing logistics services share social delivery freelancers instead of traditional full-time delivery employees. The optimal dynamic pricing model of crowdsourcing logistics services, which could be applied to adjust the social delivery capacity supply to meet the stochastic demand especially during the peak period, is established based on optimal control theory. We study optimal pricing strategies under both conditions when the supply and the demand is balanced and accumulated delivery orders are minimized. Moreover, the impact of delivery riders’ wage ratio on pricing and platforms’ expected revenue are analyzed. It is verified by numerical simulation results that optimal dynamic pricing strategies of crowdsourcing logistics services could effectively balance supply and demand, further maximize the expected revenue of platforms. The growth rate of optimal pricing of crowdsourcing logistics services is increasing with respect to the delivery riders’ wage ratio. However, the expected revenue of crowdsourcing logistics platforms declines as the wage ratio increases. PubDate: 2021-01-05

Abstract: Abstract Recycling of end-of-life (EOL) products has drawn much attention from both researchers and practitioners over the recent decades due to the environmental protection, sustainable development and economic benefits. For an EOL product recycling system, a core problem is to separate their useful and hazardous parts by an efficient disassembly line in which there exist uncertain factors, such as stochastic task processing time. The corresponding combinatorial optimization problems aim to optimally choose alternative task processes, determine the number of workstations to be opened, and assign the disassembly tasks to the opened workstations. In most existing studies, the probability distribution of task processing time is assumed to be known. However, the complete information of probability distribution is often unavailable due to various factors. In this study, we address a disassembly line balancing problem to minimize the total disassembly cost in which only limited information of probability distribution, i.e., the mean, lower and upper bounds of task processing time, is known. Based on problem analysis, some properties are derived for the construction of a new distribution-free model. Furthermore, an effective second-order cone program approximation-based method is developed to solve the proposed model. Experimental results of benchmark examples and newly generated instances demonstrate the effectiveness and efficiency of the proposed method in dealing with stochastic disassembly line balancing with limited distributional information. Finally, managerial insights and future research are discussed. PubDate: 2021-01-04

Abstract: Abstract Social media has become a tremendous source to bring in new clients. Sharing posts for new offers/products to get extensive client engagement can be predicted by grouping the users based on their previous interactions. In this paper, we improve existing state-of-the-art techniques to predict group-level popularity by extending the data clustering approach and constraint network prediction using stochastic Adam optimization. Various other topological properties of this two-level approach are also tested. The Adam optimization for clustered group prediction improves the relative error substantially. Overall, the proposed novel approach improved the prediction popularity accuracy by a significant difference of 18.21%. PubDate: 2021-01-03

Abstract: Abstract Privacy-preserving data aggregation is an important problem that has attracted extensive study. The state-of-the-art techniques for solving this problem is differential privacy, which offers a strong privacy guarantee without making strong assumptions about the attacker. However, existing solutions cannot effectively query data aggregation from high-dimensional datasets under differential privacy guarantee. Particularly, when the input dataset contains large number of dimensions, existing solutions must inject large scale of noise into returned aggregates. To address the above issue, this paper proposes an algorithm for querying differentially private approximate aggregates from high-dimensional datasets. Given a dataset D, our algorithm first develops a \(\varepsilon '\) -differentially private feature selection method that is based on a data sampling process over a kd-tree, which allows us to obtain a differentially private low-dimensional dataset with representative instances. After that, our algorithm samples independent samples from the kd-tree aiming at obtaining \((\alpha ', \delta ')\) -approximate aggregates. Finally, a model is proposed to determine the relevance between privacy and utility budgets such that the final aggregate still satisfies the accuracy requirements specified by data consumers. Intuitively, the proposed algorithm circumvents the dilemma of both dimensionality and the height threshold of kd-tree, as it samples a low-dimensional dataset S and queries aggregates from S, instead of the kd-tree. Satisfying user-specified privacy and utility budgets after multiple-stages approximation is significantly challenging, and we presents a novel model to determine the parameters’ relevance. PubDate: 2021-01-02

Abstract: Abstract This article studies scheduling problems with past-sequence-dependent delivery times (denoted by psddt) on a single-machine, i.e., the delivery time of a job depends on its waiting time of processing. We prove that the total (discounted) weighted completion time minimization can be solved in \(O(n\log n)\) time, where n is the number of jobs, and the weight is a position-dependent weight. For common (denoted by con) and slack (denoted by slk) due-date assignment and position-dependent weights (denoted by pdw), we prove that an objective cost minimization is solvable in \(O(n\log n)\) time. The model (i.e., psddt and pdw) can also be extended to position-dependent (time-dependent) processing times. PubDate: 2021-01-01

Abstract: Abstract Let \(G=(V,E)\) be a graph. A function \(f : V \rightarrow \{0, 1, 2\}\) is an outer independent Roman dominating function (OIRDF) on a graph G if for every vertex \(v \in V\) with \(f (v) = 0\) there is a vertex u adjacent to v with \(f (u) = 2\) and \(\{x\in V:f(x)=0\}\) is an independent set. The weight of f is the value \( f(V)=\sum _{v\in V}f(v)\) . An outer independent total Roman dominating function (OITRDF) f on G is an OIRDF on G such that for every \(v\in V\) with \(f(v)>0\) there is a vertex u adjacent to v with \(f (u)>0\) . The minimum weight of an OIRDF on G is called the outer independent Roman domination number of G, denoted by \(\gamma _{oiR}(G)\) . Similarly, the outer independent total Roman domination number of G is defined, denoted by \(\gamma _{oitR}(G)\) . In this paper, we first show that computing \(\gamma _{oiR}(G)\) (respectively, \(\gamma _{oitR}(G)\) ) is a NP-hard problem, even when G is a chordal graph. Then, for a given proper interval graph \(G=(V,E)\) we propose an algorithm to compute \(\gamma _{oiR}(G)\) (respectively, \(\gamma _{oitR}(G)\) ) in \({\mathcal {O}}( V )\) time. PubDate: 2021-01-01

Abstract: Abstract Multi-objective optimization for siting and sizing of Distributed Generations (DGs) is difficult because of the highly non-linear interactions of a large number of variables. Furthermore, effective optimization algorithms are often highly problem-dependent and need broad tuning, which limits their applicability to the real world. To address this issue, in this study, Multi-Objective Differential Evolution (MODE) algorithms have been proposed for siting and sizing of DGs. The site and size of DGs play a vital role in the minimization of real power losses and enhancement of voltage profile in distribution systems. This study intends to attain the technical, economic, and environmental benefits of DGs. Hence, the Objective Functions such as minimization of power losses, voltage deviation, energy cost, emissions while generating power, and enhancement of the Voltage Stability Index have been considered. The simulations of two different multi-objective operational cases have been carried out on IEEE 33 bus system, IEEE 69 bus system, and Tamil Nadu Generation and Distribution Corporation Limited, as a real part of 62 bus Indian Utility System. The simulation results of MODE have shown its superior performance and have ensured the economic and environmental benefits of integrating DGs. PubDate: 2020-12-21

Abstract: Abstract Undirected co-graphs are those graphs which can be generated from the single vertex graph by disjoint union and join operations. Co-graphs are exactly the \(P_4\) -free graphs (where \(P_4\) denotes the path on 4 vertices). The class of co-graphs itself and several subclasses haven been intensively studied. Among these are trivially perfect graphs, threshold graphs, weakly quasi threshold graphs, and simple co-graphs. Directed co-graphs are digraphs which can be defined by, starting with the single vertex graph, applying the disjoint union, order composition, and series composition. By omitting the series composition we obtain the subclass of oriented co-graphs which has been analyzed by Lawler in the 1970s. The restriction to linear expressions was recently studied by Boeckner. Until now, there are only a few versions of subclasses of directed co-graphs. By transmitting the restrictions of undirected subclasses to the directed classes, we define the corresponding subclasses for directed co-graphs. We consider directed and oriented versions of threshold graphs, simple co-graphs, co-simple co-graphs, trivially perfect graphs, co-trivially perfect graphs, weakly quasi threshold graphs and co-weakly quasi threshold graphs. For all these classes we give characterizations by finite sets of minimal forbidden induced subdigraphs. Additionally, we analyze the relations between these graph classes. PubDate: 2020-11-27

Abstract: Abstract We introduce the discount allocation problem to a new online social networks (OSNs) scenario where the nodes and the relationships between nodes are determined but the states of edges between nodes are unknown. We can know the states of all the edges centered on a node only when it becomes active. Different from most previous work on influence maximization discount allocation problem in OSNs, our goal is to minimize the discount cost that the marketer spends while ensuring at least Q customers who adopt the target product in the end in OSNs. We propose an online discount allocation policy to select seed users to spread the product information. The marketer initially selects one seed user to offer him a discount and observes whether he accepts the discount. If he accepts the discount, the marketer needs to observe how well this seed user contributes to the diffusion of product adoptions and how much discount he accepts. The remaining seeds are chosen based on the feedback of diffusion results obtained by all previous selected seeds. We propose two online discount allocation greedy algorithms under two different situations: uniform and non-uniform discounts allocation. We offer selected users discounts changing from the lowest to highest in the discount rate set until the users receive the discount and become seed users in non-uniform discount allocation situation, which saves the cost of firms comparing with the previous method that providing product to users for free. We present a theoretical analysis with bounded approximation ratios for the algorithms. Extensive experiments are conducted to evaluate the performance of the proposed online discount allocation algorithms on real-world online social networks datasets and the results demonstrate the effectiveness and efficiency of our methods. PubDate: 2020-11-26

Abstract: Abstract The group testing problem is that we are asked to identify all the defects with the minimum number of tests when given a set of n items with at most d defects. In this paper, as a generalization of Liu et al.’s construction in the paper (Liu and Gao in Discret Math 338:857–862, 2015), new pooling designs are constructed from singular linear spaces over finite fields. Then we make comparisons with Liu et al.’s construction in the aspects of parameters of pooling designs. By choosing appropriate parameters in our pooling designs, the performance of test efficiency in our pooling designs is better than that given by Liu et al. Finally, the analysis of parameters in our pooling designs is provided. PubDate: 2020-11-25

Abstract: Abstract Comparative genomics is a field of biology that aims at comparing genomes of different species. One major question of this field is to find the evolutionary distance between two given genomes. One way to estimate such distance is to use the rearrangement distance, which consists in finding a minimum cost sequence of rearrangements that transforms one genome into another. We use permutations to model the genomes being compared and, in this way, we can treat this problem as the problem of sorting a permutation with a minimum cost sequence of rearrangements. In the early works with rearrangement distance, it was considered that all rearrangements are equally likely to occur and, consequently, they use a unitary cost for all rearrangements. Some variations of the problem were motivated by the observation that rearrangements involving large segments of a genome rarely occur. One of these variants also uses a unitary cost, however it adds a constraint in the length of the operations allowed to estimate the distance. Another variant uses a cost function based on the rearrangement’s length. In this work, we study problems that combine both variants, that is, problems with a constraint in the rearrangement’s length and with a cost function based on the rearrangement’s length. We present approximation algorithms for five such problems involving reversals and/or transpositions for sorting signed and unsigned permutations. We also analyze the problems for specific parameters of the length restriction and for when the cost function is equal to \(\ell ^\alpha \) , where \(\ell \) is the rearrangement’s length and \(\alpha \ge 1\) is a real value parameter. PubDate: 2020-11-18

Abstract: Abstract Nurse rostering problem (NRP) or nurse scheduling problem is a combinatorial optimization problem that involves the assignment of shifts to nurses while managing coverage constraints, expertise categories, labor legislation, contractual agreements, personal preferences, etc. The focus on this problem serves to improve service quality, nurse health and their satisfaction, and reduction of hospital costs. The existence of uncertainties and inaccurate estimates of the workload leads to a non-optimal or an infeasible solution. In this study, due to the importance of human resource management and crisis management in the health care system, a sustainable approach was developed with a robust scenario-based optimization method. Since NRP is a NP-hard problem, it is impossible to solve it in medium and large sizes in reasonable time. In this paper, a well-known metaheuristic algorithm, namely the differential evolution (DE) algorithm was proposed due to its sound structural features for searching in binary space. Then its performance was compared against the genetic algorithm. The results show that the DE algorithm has good performance. PubDate: 2020-11-17

Abstract: Abstract This paper studies several new multiple routing path computation problems in failure-interdependent complex networks such as smart grid communication network, each of which exhibits unique failure interdependency. Despite the difference of the formulation of the problems, we show that each of the problems can be reduced to another within polynomial time, and therefore they are equivalent in terms of hardness. Then, we show that they are not only \(\mathcal {NP}\) -hard, but also cannot be approximated within a certain bound unless \({\mathcal {P}}=\mathcal {NP}\) . Besides, we show that their decision versions to determine if there exist two failure independent paths between two given end nodes are still \(\mathcal {NP}\) -complete. Finally, a series of heuristic algorithms are proposed to deal with the daunting hardness of the problems. Most importantly, this paper opens a new series of research problems with daunting complexity based on important real world applications. PubDate: 2020-11-17