Journal of Combinatorial Optimization
Journal Prestige (SJR): 0.579 Citation Impact (citeScore): 1 Number of Followers: 7 Hybrid journal (It can contain Open Access articles) ISSN (Print) 15732886  ISSN (Online) 13826905 Published by SpringerVerlag [2467 journals] 
 Smart logistics with IoTbased enterprise management system using global
manufacturing
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Smart logistics will encourage replacing manual systems with the Internet of Things (IoT) or automated handling equipment taking care of repetitive tasks in the enterprise management system. Opportunities to address the issues arise from the development of smart logistics. When used with other quantitative analytic tools and techniques, today’s IoT may generate vast amounts of data and reveal intricate correlations between the many transactions represented by that data. Smart logistics can benefit from the inclusion of these features. The complication and variety of consumer orders necessitate a change in warehouse operations. There is a need for realtime data and contextual data on highly tailored orders' large diversity and small batch sizes. To achieve ontime order fulfilment, the synchronization of purchase orders to support production is critical to the frequent changes in customer needs. Order fulfilment suffers as a result of inefficient and erroneous order selection. Computational intelligence techniques are used in the research to provide an advanced data analysis methodology for Industry 4.0’s smart logistics through global manufacturing. Advanced data analysis methods for Industry 4.0’s smart logistics are developed using computational intelligence approaches. However, IoTSL can increase logistics productivity, picking accuracy, and efficiency based on data obtained from a case firm and is resilient to order unpredictability. Smart contracts, logistics planners, and asset condition monitoring are included in the paper's smart logistics system. A prototype solution is implemented to demonstrate responsibility, traceability, and obligation for asset management across the supply chain by multiple stakeholders participating in a logistics scenario. It is important to look at how IoT technologies are being used in the smart logistics industry from transportation, storage, loading/unloading, carrying, distributed processing and information transfer, thereby achieving realtime monitoring, increased logistics productivity, logistics management, increased delivery of goods and efficiency of 98.3%.
PubDate: 20230119

 ARX and ARMAX modelling of SBCNC60 machine for surface roughness and MRR
with optimization of system response using PSO
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In the process of attaining highend machines, control of machining systems via optimized machining parameters along with their transient responses is highly essential. By implementing system detection methodologies, a new methodology is proposed to introduce the best mathematical model, which subsumes the best FIT, fewer parameters, minimum MSE, and residuals amongst ARX and ARMAX models for an SBCNC60 Machine to gratify the controller’s design requirement. From the CNC machine, the realtime measurement data samples are obtained for model detection; then, they are simulated with the aid of MATLAB. Here, for the study of Metal Removal Rate (MRR), the multiple inputs with the singleoutput system are utilized; similarly, for tuning operation, the Surface Roughness (SR) is measured; subsequently, the MRR is utilized for drilling operation on P8 (H13, HighSpeedSteels) materials, which were detected by ARX and ARMAX for varying orders. To optimize the output MRR, the bestfit models were selected for control regarding the PID as well as FOPID controller; moreover, in the ‘3’ inputs’ SR, one input differs at a time whilst retaining the other 2 constants at their midlevels. Better timedomain characteristics were obtained by the PSO tuned FOPID controlled ARX 331 model than the PSOPID controller for MRR (tr = 6.86 s., Mp = 1.94%, ts = 8.93 s.) and SR (tr = 1.13 s., Mp = 2.47%, ts = 2.68 s.) in case of turning operation, the ARX 311 is the bestsuited model for MRR (tr = 0.0818 s., Mp = 1.8%, ts = 2.78 s.) while running for drilling operation. A prominent effect of the varied cutting speed input variable was illustrated by these models; thus, affecting the output performance like MRR and SR for various operations performed during the machining process.
PubDate: 20230119

 On streaming algorithms for maximizing a supermodular function plus a
MDRsubmodular function on the integer lattice
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, we provide a streaming algorithm for the problem of maximizing the sum of a supermodular function and a nonnegative monotone diminishing return submodular (MDRsubmodular) function with a knapsack constraint on the integer lattice. Inspired by the SIEVESTREAMING algorithm, we present a twopass streaming algorithm by using the threshold technique. Then, we improve the twopass streaming algorithm to onepass and further reduce its space complexity. The proposed algorithms are proved to have polynomial time and space complexity, and a performance guarantee dependent on the curvature of the supermodular function. Finally, we carry out numerical experiments to verify the performance of the algorithm.
PubDate: 20230117

 Two approximation algorithms for maximizing nonnegative weakly monotonic
set functions
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Many combinatorial optimization problems can be reduced to submodular optimization problems. However, many cases in practical applications do not fully comply with the diminishing returns characteristic. This paper studies the problem of maximizing weaklymonotone nonsubmodular nonnegative set functions without constraints, and extends the normal submodular ratio to weaklymonotone submodular ratio \(\widehat{\gamma }\) . In this paper, two algorithms are given for the above problems. The first one is a deterministic greedy approximation algorithm, which realizes the approximation ratio of \(\frac{\widehat{\gamma }}{\widehat{\gamma }+2}\) . When \(\widehat{\gamma }=1\) , the approximate ratio is 1/3, which matches the ratio of the best deterministic algorithm known for the maximization of submodular function without constraints. The second algorithm is a random greedy algorithm, which improves the approximation ratio to \(\frac{\widehat{\gamma }}{\widehat{\gamma }+1}\) . When \(\widehat{\gamma }=1\) , the approximation ratio is 1/2, the same as the best algorithm for the maximization of unconstrained submodular set functions.
PubDate: 20230111

 The mechanism and test of the impact of environmental regulation and
technological innovation on high quality development
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Environmental regulation and technological innovation are two important measures to realize highquality economic development under the current "double cycle" new development pattern in our country. Exploring the mechanism of environmental regulation and technological innovation on highquality economic development is of great significance to realize highquality economic development. Firstly, analyze the theoretical mechanism that technological innovation and environmental regulation affect the highquality development of economy, and put forward the theoretical hypothesis that technological innovation, environmental regulation and their interaction items can promote the highquality development of economy; Secondly, construct the measurement index system of the highquality development level of economy based on the new development concept, measure the highquality development level of economy, and find that the highquality development level of economy in the whole country is on the rise year by year, with great differences between regions, it presents the characteristics of the eastern region > the central region > the western region; Once again, the fixed effect model is adopted to explore the impact of environmental regulation and technological innovation on highquality economic development at the national level and the eastern, central and western regions. The results show that environmental regulation and technological innovation not only have independent effect, but also have synergistic effect of mutual promotion on highquality economic development, and the impact of the two on highquality economic development has regional heterogeneity. At last, some countermeasures and suggestions are put forward: increase the investment in technological innovation, improve the backward effect of environmental regulations on highquality economic development, at the same time, pay attention to the coordinated development of environmental regulations and technological innovation, and promote highquality economic development in both ways.
PubDate: 20230110

 Cycleconnected mixed graphs and related problems

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, motivated by applications of vertex connectivity of digraphs or graphs, we consider the cycleconnected mixed graph (CCMG, for short) problem, which is in essence different from the connected mixed graph (CMG, for short) problem, and it is modelled as follows. Given a mixed graph \(G=(V,A\cup E)\) , for each pair \( \{u, v\}\) of two distinct vertices in G, we are asked to determine whether there exists a mixed cycle C in G to contain such two vertices u and v, where C passes through its arc (x, y) along the direction only from x to y and its edge xy along one direction either from x to y or from y to x. Particularly, when the CCMG problem is specialized to either digraphs or graphs, we refer to the related version of the CCMG problem as either the cycleconnected digraph (CCD, for short) problem or the cycleconnected graph (CCG, for short) problem, respectively, where such a graph in the CCG problem is called as a cycleconnected graph. Similarly, we consider the weakly cycleconnected (in other words, circuitconnected) mixed graph (WCCMG, for short) problem, only substituting a mixed circuit for a mixed cycle in the CCMG problem. Moreover, given a graph \(G=(V,E)\) , we define the cycleconnectivity \(\kappa _c(G)\) of G to be the smallest number of vertices (in G) whose deletion causes the reduced subgraph either not to be a cycleconnected graph or to become an isolated vertex; Furthermore, for each pair \(\{s, t\}\) of two distinct vertices in G, we denote by \(\kappa _{sc}(s,t)\) the maximum number of internally vertexdisjoint cycles in G to only contain such two vertices s and t in common, then we define the strong cycleconnectivity \(\kappa _{sc}(G)\) of G to be the smallest of these numbers \(\kappa _{sc}(s,t)\) among all pairs \(\{s, t\}\) of distinct vertices in G. We obtain the following three results. (1) Using a transformation from the directed 2linkage problem, which is NPcomplete, to the CCD problem, we prove that the CCD problem is NPcomplete, implying that the CCMG problem still remains NPcomplete, and however, we design a combinatorial algorithm in time \(O(n^2m)\) to solve the CCG problem, where n is the number of vertices and m is the number of edges of a graph \(G=(V,E)\) ; (2) We provide a combinatorial algorithm in time O(m) to solve the WCCMG problem, where m is the number of edges of a mixed graph \(G=(V,A\cup E)\) ; (3) Given a graph \(G=(V,E)\) , we present twin combinatorial algorithms to compute cycleconnectivity \(\kappa _c(G)\) and strong cycleconnectivity \(\kappa _{sc}(G)\) , respectively.
PubDate: 20230110

 Online scheduling of twomachine flowshop with lookahead and incompatible
job families
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This paper considers online scheduling on two unit flowshop machines, which there exists unbounded parallelbatch scheduling with incompatible job families and lookahead intervals. The unit flowshop machine means that the processing time of any job on each machine is unit processing time. The objective is to minimize the maximum completion time. The lookahead model means that an online algorithm can foresee the information of all jobs arriving in time interval \((t,t+\beta ]\) at time t. There exist incompatible job families, that is, jobs belonging to different families cannot be processed in the same batch. In this paper, we address the lower bound of the proposed problem, and provide a best possible online algorithm of competitive ratio \(1+\alpha _f\) for \(0\le \beta <1\) , where \(\alpha _f\) is the positive root of the equation \({(f+1)} \alpha ^{2}+(\beta +2) \alpha +\beta f=0\) and f is the number of incompatible job families which is known in advance.
PubDate: 20230109

 Combinatorial approximation algorithms for the maximum bounded connected
bipartition problem
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, we study the maximum bounded connected bipartition problem: given a vertexweighted connected graph \(G=(V,E;w)\) and an upper bound B, the vertex set V is partitioned into two subsets \((V_1,V_2)\) such that the total weight of the two subgraphs induced by \(V_1\) and \(V_2\) is maximized, and these subgraphs are connected, where the weight of a subgraph is the minimum of B and the total weight of all vertices in the subgraph. In this paper, we prove that this problem is NPhard even when G is a completed graph, a grid graph with only 3 rows or an interval graph, and we present an \(\frac{8}{7}\) approximation algorithm. In particular, we present a \(\frac{14}{13}\) approximation algorithm for the case of grid graphs, and we present a fully polynomialtime approximation scheme for the case of interval graphs.
PubDate: 20230109

 On parameterized approximation algorithms for balanced clustering

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Balanced clustering is a frequently encountered problem in applications requiring balanced class distributions, which generalizes the standard clustering problem in that the number of clients connected to each facility is constrained by the given lower and upper bounds. It was known that both the problems of balanced kmeans and kmedian are W[2]hard if parameterized by k, implying that the existences of FPT(k)time exact algorithms for these problems are unlikely. In this paper, we give FPT(k)time \((9+\epsilon )\) approximation and \((3+\epsilon )\) approximation algorithms for balanced kmeans and kmedian respectively, improving upon the previous best approximation ratios of \(86.9+\epsilon \) and \(7.2+\epsilon \) obtained in the same time. Our main technical contribution and the crucial step in getting the improved ratios is a different random sampling method for selecting opened facilities.
PubDate: 20230108

 Modeling the relationship between fairness concern and customer loyalty in
dual distribution channel
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract With the rapid growth of the online market, the etailer platform has accumulated loyal consumers, which has caused etailers to be more concerned about fairness, especially by paying more attention to manufacturers’ profits earned from the ecommerce platform. We build a dualchannel model and consider whether an etailer and manufacturer should be fair minded. We find that the platform will care about fairness only when the proportion of loyal customers is at a medium level. When the proportion of loyal customers is greater, whether etailers are fair minded will make no difference. Given that the etailer cares about fairness, the manufacturer will also be fairminded when there is a moderate proportion of loyal customers. When the proportion of loyal customers is greater, the manufacturer will not be fair minded. When only the etailer is concerned about fairness, the loyal consumer will be worse off if there is a larger proportion of loyal consumers, and a case where both the etailer and manufacturer care about fairness shows the opposite trend. When only the etailer is concerned about fairness, the normal consumer will always be better off. When both supply chain members care about fairness, the normal consumer will be worse off if the proportion of loyal consumers is greater.
PubDate: 20230107

 Injective edge coloring of sparse graphs with maximum degree 5

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract A kinjectiveedge coloring of a graph G is a mapping \(c:E(G)\rightarrow \{1,2,\cdots ,k\}\) such that \(c(e_1)\ne c(e_3)\) for any three consecutive edges \(e_1,e_2,e_3\) of a path or a 3cycle. \(\chi _{i}'(G)=\min \{k G\) has a kinjectiveedge coloring \(\}\) is called the injective chromatic index of G. In this paper, we prove that for graphs G with \(\Delta (G)\le 5\) , (1) \(\chi _{i}'(G)\le 8\) if \(mad(G)<\frac{7}{3}\) ; (2) \(\chi _{i}'(G)\le 9\) if \(mad(G)<\frac{12}{5}\) ; (3) \(\chi _{i}'(G)\le 10\) if \(mad(G)<\frac{5}{2}\) ; (4) \(\chi _{i}'(G)\le 11\) if \(mad(G)<\frac{18}{7}\) .
PubDate: 20230107

 The rdynamic chromatic number of planar graphs without 4,5cycles

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Let G be a graph and k, r be two positive integers. A (k, r)dynamic coloring \(\varphi \) of G is a proper kcoloring such that \(\mid \varphi (N_{G}(v))\mid \ge \) \(\min \{d_{G}(v),r\}\) for each \(v\in V(G)\) . In this paper, we prove that the rdynamic chromatic number of planar graphs without 4,5cycles, and intersecting 3cycles is at most \(r+3\) if \(r\ge 14\) .
PubDate: 20230107

 Polynomial time algorithm for kvertexedge dominating problem in interval
graphs
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Let G be a connected interval graph with n vertices and m edges. For any positive integer k and any subset S of E(G), we design an \(O(k S +m)\) time algorithm to find a minimum kvertexedge dominating set of G with respect to S. This shows that the vertexedge domination problem and the double vertexedge domination problem can be solved in linear time. Furthermore, the kvertexedge domination problem can also be solved in O(km) time algorithm in interval graphs. Finally, we present a linear time algorithm to solve the independent vertexedge domination problem for unit interval graphs.
PubDate: 20230106

 A polyhedral approach to least cost influence maximization in social
networks
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract The least cost influence maximization problem aims to determine minimum cost of partial (e.g., monetary) incentives initially given to the influential spreaders on a social network, so that these early adopters exert influence toward their neighbors and prompt influence propagation to reach a desired penetration rate by the end of cascading processes. We first conduct polyhedral analysis on a substructure that describes influence propagation assuming influence weights are unequal, linear and additively separable. Two classes of facetdefining inequalities based on a mixed 0–1 knapsack set contained in this substructure are proposed. We characterize another exponential class of valid and facetdefining inequalities utilizing the concept of minimum influencing subset. We show that these inequalities can be separated in polynomial time efficiently. Furthermore, a polynomialtime dynamic programming recursion is presented to solve this problem on a simple cycle graph. For arbitrary graphs, we propose a new exponential class of valid inequalities that dominates the cycle elimination constraints and an efficient separation algorithm for them. A compact convex hull description for a special case is presented. We illustrate the effectiveness of these inequalities via a delayed cut generation algorithm in the computational experiments.
PubDate: 20230104

 Approximation algorithms for the lower bounded correlation clustering
problem
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Lower bounded correlation clustering problem (LBCorCP) is a new generalization of the correlation clustering problem (CorCP). In the LBCorCP, we are given an integer L and a complete labelled graph. Each edge in the graph is either positive or negative based on the similarity of its two endpoints. The goal is to find a clustering of the vertices, each cluster contains at least L vertices, so as to minimize the sum of the number of positive cut edges and negative uncut edges. In this paper, we first introduce the LBCorCP and give three algorithms for this problem. The first algorithm is a random algorithm, which is designed for the instances of the LBCorCP with fewer positive edges. The second one is that we let the set V itself as a cluster and prove that the algorithm works well on two specially instances with fewer negative edges. The last one is an LProunding based iterative algorithm, which is also provided for the instances with fewer negative edges. The above three algorithms can quickly solve some special instances in polynomial time and obtain a smaller approximation ratio. In addition, we conduct simulations to evaluate the performance of our algorithms.
PubDate: 20221231

 An optimal streaming algorithm for nonsubmodular functions maximization
on the integer lattice
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Submodular optimization problem has been concerned in recent years. The problem of maximizing submodular and nonsubmodular functions on the integer lattice has received a lot of recent attention. In this paper, we study streaming algorithms for the problem of maximizing a monotone nonsubmodular functions with cardinality constraint on the integer lattice. For a monotone nonsubmodular function \(f:{\textbf {Z}}^{n}_{+}\rightarrow {\textbf {R}}_{+}\) defined on the integer lattice with diminishingreturn (DR) ratio \(\gamma \) , we present a one pass streaming algorithm that gives a \((1\frac{1}{2^{\gamma }}\epsilon )\) approximation, requires at most \(O(k\epsilon ^{1}\log {k/\gamma })\) space and \(O(\epsilon ^{1}\log {k/\gamma }\cdot \) \(\log {\Vert {\textbf {B}}\Vert _{\infty }})\) update time per element. We then modify the algorithm and improve the memory complexity to \(O(\frac{k}{\gamma \epsilon })\) . To the best of our knowledge, this is the first streaming algorithm on the integer lattice for this constrained maximization problem.
PubDate: 20221229

 Envyfreeness and relaxed stability: hardness and approximation algorithms

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We consider the problem of computing matchings under twosided preferences in the presence of lower as well as upperquota requirements for the resources. In the presence of lowerquotas a feasible matching may not exist and hence we focus on critical matchings. Informally, a critical matching achieves the smallest deficiency. We first consider two wellstudied notions of optimality with respect to preferences, namely stability and envyfreeness. There exist instances that do not admit a critical stable matching or a critical envyfree matching. When critical matching satisfying the optimality criteria does not exist, we focus on computing a minimumdeficiency matching among all stable or envyfree matchings. To ensure guaranteed existence of an optimal critical matching, we introduce and study a new notion of optimality, namely relaxed stability. We show that every instance admits a critical relaxed stable matching and it can be efficiently computed. We then investigate the computational complexity of computing maximum size optimal matchings with smallest deficiency. Our results show that computing a maximum size minimumdeficiency envyfree matching and a maximum size critical relaxed stable matching are both hard to approximate within \(\frac{21}{19}\epsilon \) , for any \(\epsilon > 0\) unless P = NP. For envyfree matchings, we present an approximation algorithm for general instances and a polynomial time exact algorithm for a special case. For relaxed stable matchings, we present a constant factor approximation algorithm for general instances.
PubDate: 20221227

 Proper orientation, proper biorientation and semiproper orientation
numbers of graphs
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract An orientation D of G is proper if for every \(xy\in E(G)\) , we have \(d^_D(x)\ne d^_D(y)\) . An orientation D is a porientation if the maximum indegree of a vertex in D is at most p. The minimum integer p such that G has a proper porientation is called the proper orientation number pon(G) of G [introduced by Ahadi and Dehghan (Inf Process Lett 113:799–803, 2013)]. We introduce a proper biorientation of G, where an edge xy of G can be replaced by either arc xy or arc yx or both arcs xy and yx. Similarly to pon(G), we can define the proper biorientation number pbon(G) of G using biorientations instead of orientations. Clearly, \(\textrm{pbon}(G)\le \textrm{pon}(G)\) for every graph G. We compare pbon(G) with pon(G) for various classes of graphs. We show that for trees T, the tight bound \(\textrm{pon}(T)\le 4\) extends to the tight bound \(\textrm{pbon}(T)\le 4\) and for cacti G, the tight bound \(\textrm{pon}(G)\le 7\) extends to the tight bound \(\textrm{pbon}(G)\le 7.\) We also prove that there is an infinite number of trees T for which \(\textrm{pbon}(T)< \textrm{pon}(T).\) Let (H, w) be a weighted digraph with a weight function \(w: A(H)\rightarrow {\mathbb {Z}}_+.\) The inweight \(w^_H(v)\) of a vertex v of H is the sum of the weights of arcs towards v. A semiproper porientation (D, w) of an undirected graph G is an orientation D of G together with a weight function \(w: A(D)\rightarrow {\mathbb {Z}}_+\) , such that the inweight of any adjacent vertices are distinct and \(w^_D(v)\le p\) for every \(v\in V(D)\) . The semiproper orientation number spon(G) of a graph G (introduced by Dehghan and Havet in 2021) is the minimum p such that G has a semiproper porientation (D, w) of G. We prove that \(\textrm{spon}(G)\le \textrm{pbon}(G)\) and characterize graphs G for which \(\textrm{spon}(G)= \textrm{pbon}(G).\)
PubDate: 20221227

 Computing densest ksubgraph with structural parameters

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Densest kSubgraph is the problem to find a vertex subset S of size k such that the number of edges in the subgraph induced by S is maximized. In this paper, we show that Densest kSubgraph is fixed parameter tractable when parameterized by neighborhood diversity, block deletion number, distancehereditary deletion number, and cograph deletion number, respectively. Furthermore, we give a 2approximation \(2^{{{\texttt{tc}}(G)}/2}n^{O(1)}\) time algorithm where \({{\texttt{tc}}(G)}\) is the twin cover number of an input graph G.
PubDate: 20221223

 Diversifiedprofit maximization in competitive social advertising

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Due to the important role that social networks play in advertisements and propaganda, influence maximization (IM) problem which aims at finding some influential users as seeds to trigger large online cascading influence spread has been a hot research topic in the past two decades. As an extension of classical IM problem, profit maximization (PM) problem is inspired by product promotion and focuses on the profit generated by consumer. Given that competitive social advertising is more common in realworld, a series of studies propose some versions of PM problem. However, the competition happening in the information dissemination of imperfect substitutes and the influence of potential consumers’ preference have been mostly ignored. Besides, to the best of our knowledge, no research pays attention on the fact that some companies may snatch seeds to limit the profits of their opponents. Therefore, we propose a novel competitionbased diversifiedprofit maximization (CDM) problem and its adaptive version, i.e., adaptive competitionbased diversifiedprofit maximization (ACDM) problem. Different from prior works, these problems take seed’s preference into consideration and use social welfare to reflect it. These two problems aim at selecting seeds and allocating them to marketers such that the sum of profit generated by consumers for a special entity after information dissemination and social welfare with respect to seed allocation reaches maximum. To address these two problems, we design an algorithm which combines the method of online allocation and the concept of Shapley value. Experimental results on three realworld data sets demonstrate the effectiveness of our proposed algorithm.
PubDate: 20221221
