This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing ...
详细信息
This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modularity that enhances its effectiveness. We formulate community detection as an integer programming problem of an equivalent yet more compact counterpart model of the revised Max-Min Modularity maximization problem. Using a row generation technique alongside the heuristic approach, we then provide a hybrid procedure for near-optimally solving the model and discovering high-quality communities. Through a series of experiments, we demonstrate the success of our algorithm, showcasing its efficiency in detecting communities, particularly in extensive networks.
Among various variants of the traveling salesman problem (TSP), the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this...
详细信息
Among various variants of the traveling salesman problem (TSP), the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomialtime algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3/2 -approximation algorithm in [A. Seb\H o and J. Vygen, Combinatorica, 34 (2014), pp. 597--629], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics).
Maximizing a submodular function has a wide range of applications in machine learning and data mining. One such application is data summarization whose goal is to select a small set of representative and diverse data ...
详细信息
Maximizing a submodular function has a wide range of applications in machine learning and data mining. One such application is data summarization whose goal is to select a small set of representative and diverse data items from a large dataset. However, data items might have sensitive attributes such as race or gender, in this setting, it is important to design fairness-aware algorithms to mitigate potential algorithmic bias that may cause over- or under- representation of particular groups. Motivated by that, we propose and study the classic non-monotone submodular maximization problem subject to novel group fairness constraints. Our goal is to select a set of items that maximizes a non-monotone submodular function, while ensuring that the number of selected items from each group is proportionate to its size, to the extent specified by the decision maker. We develop the first constant-factor approximation algorithms for this problem. We also extend the basic model to incorporate an additional global size constraint on the total number of selected items.
We combine two fundamental optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency and minimally resolved supertree into a new problem, which we call q-maximu...
详细信息
We combine two fundamental optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency and minimally resolved supertree into a new problem, which we call q-maximum rooted triplets consistency (q-MAXRTC). It takes as input a set R of rooted, binary phylogenetic trees with three leaves each and asks for a phylogenetic tree with exactly q internal nodes that contains the largest possible number of trees from R. We prove that q-MAXRTC is NP-hard to approximate within a constant, develop polynomial-time approximation algorithms for different values of q, and show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much branching information. To demonstrate the algorithmic advantage of using trees with few internal nodes, we also propose a new algorithm for computing the rooted triplet distance that is faster than the existing algorithms when restricted to such trees.
We consider the problem of finding a low-cost allocation and ordering of tasks between a team of robots in a d-dimensional, uncertain, landscape, and the sensitivity of this solution to changes in the cost *** algorit...
详细信息
We consider the problem of finding a low-cost allocation and ordering of tasks between a team of robots in a d-dimensional, uncertain, landscape, and the sensitivity of this solution to changes in the cost *** algorithms have been shown to give a 2-approximation to the MIN$UM allocation problem. By analysing such an auction algorithm, we obtain intervals on each cost, such that any fluctuation of the costs within these intervals will result in the auction algorithm outputting the same solution.& COPY;2023 Published by Elsevier Ltd.
A k-submodular function is a generalization of a submodular function. The definition domain of a k-submodular function is a collection of k-disjoint subsets instead of simple subsets of ground set. In this paper, we c...
详细信息
A k-submodular function is a generalization of a submodular function. The definition domain of a k-submodular function is a collection of k-disjoint subsets instead of simple subsets of ground set. In this paper, we consider the maximization of a ksubmodular function with the intersection of a knapsack and m matroid constraints. When the k-submodular function is monotone, we use a special analytical method to get an approximation ratio m/1+2 (1 -e(-(m+2))) for a nested greedy and local search algorithm. For non-monotone case, we can obtain an approximate ratio 1/m+3 (1 - e(-(m+3))).
In this paper, the properties of quartic linear normal (LN) curves are studied. In particular, we present necessary and sufficient conditions for quartic LN curves to be regular. Using these conditions, we obtain an a...
详细信息
In this paper, the properties of quartic linear normal (LN) curves are studied. In particular, we present necessary and sufficient conditions for quartic LN curves to be regular. Using these conditions, we obtain an approximation method for convex curves by quartic regular LN curves which are G2 Hermite interpolation of convex curves. We show that the approximation order of our approximation method is six. In the approximation method, a convex curve is approximated by a piecewise G2 quartic regular LN curve. Each of the pieces approximates the convex curve as long as possible within the tolerance. Consequently, the G2 spline curves consist of the minimum number of quartic regular LN curves that approximate the convex curve. The algorithm for our approximation method has been implemented and has been used to approximate convex curves. (c) 2022 Elsevier B.V. All rights reserved.
In this paper, we study the non-monotone DR-submodular function maximization over integer lattice. Functions over integer lattice have been defined submodular property that is similar to submodularity of set functions...
详细信息
In this paper, we study the non-monotone DR-submodular function maximization over integer lattice. Functions over integer lattice have been defined submodular property that is similar to submodularity of set functions. DR-submodular is a further extended submodular concept for functions over the integer lattice, which captures the diminishing return property. Such functions find many applications in machine learning, social networks, wireless networks, etc. The techniques for submodular set function maximization can be applied to DR-submodular function maximization, e.g., the double greedy algorithm has a 1/2-approximation ratio, whose running time is O (nB), where n is the size of the ground set, B is the integer bound of a coordinate. In our study, we design a 1/2-approximate binary search double greedy algorithm, and we prove that its time complexity is O (n log B), which significantly improves the running time. Specifically, we consider its application to the profit maximization problem in social networks with a bipartite model, the goal of this problem is to maximize the net profit gained from a product promoting activity, which is the difference of the influence gain and the promoting cost. We prove that the objective function is DR-submodular over integer lattice. We apply binary search double greedy algorithm to this problem and verify the effectiveness. Published by Elsevier B.V.
In a graph G = (V, E) without an isolated vertex, a dominating set D c V is a paired dominating set if the graph G[D] induced by D has a perfect matching. Further, a set D c V is a disjunctive dominating set of G if f...
详细信息
In a graph G = (V, E) without an isolated vertex, a dominating set D c V is a paired dominating set if the graph G[D] induced by D has a perfect matching. Further, a set D c V is a disjunctive dominating set of G if for each vertex v E V, either NG[v] n D =⠆ 0 or there are at least two vertices in D whose distance from v is two in G. We introduce the notion of paired disjunctive domination in graphs. A disjunctive dominating set D c V in the graph G is a paired disjunctive dominating set if G[D] has a perfect matching. The minimum cardinality of a paired disjunctive dominating set of G is the paired disjunctive domination number, denoted by & gamma;prd (G). In this article, we compute the exact value of & gamma;prd(G) when G is a path, cycle, cograph, chain graph, and split graph. We prove that the decision version of the problem is NP -complete for planar graphs, bipartite graphs, and chordal graphs and design a polynomial -time algorithm to compute a minimum cardinality paired disjunctive dominating set in interval graphs. Further, we obtain lower and upper bounds on the approximation ratio of the problem and proved that the problem is APX-complete for the graphs with maximum degree 4.& COPY;2023 Elsevier B.V. All rights reserved.
We propose a randomized approximation scheme for the Euclidean Steiner Multi Cycle problem which runs in quasilinear time. In this problem, we are given a set ofnpairs of points (terminals) T = {t(i), t(i)'}(i=1)(...
详细信息
We propose a randomized approximation scheme for the Euclidean Steiner Multi Cycle problem which runs in quasilinear time. In this problem, we are given a set ofnpairs of points (terminals) T = {t(i), t(i)'}(i=1)(n) in the Euclidean plane, and the objective is to find a collection of cycles of minimum cost such that t(i) and t(i)' belong to a same cycle, for each i is an element of {1, ... ,n}. This problem extends the Steiner Cycle problem in the same way the Steiner Forest extends the Steiner Tree problem. Additionally, it has applications on routing problems with pickup and delivery locations. (c) 2020 Elsevier B.V. All rights reserved.
暂无评论