Fairness in clustering has received significant attention. Dickerson et al. in 2023 first proposed the doubly constrained fair clustering problem that aims two fairness constraints, namely, (1) the Group Fairness (GF), which requires that different groups within each cluster have a certain degree of representation, and (2) the Diversity in Center Selection fairness (DS), which requires that the selected centers represent a diverse range of different groups. However, their algorithm only focuses on the k-center objective. In this paper, we generalize the doubly constrained fair clustering to $$\ell _p$$ norm objectives with general p, thus including k-Center, k-Median, and k-Means as special cases. We propose the first approximation algorithm for the doubly constrained fair clustering problem with general p-norms. In polynomial time, our algorithm finds an $$O(\Delta ^{\frac{1}{p}})$$ -approximate clustering that violates the GF constraint by an additive factor of 5 and satisfies the DS constraint, where $$\Delta $$ is the largest size of clusters in the solution. Our main contribution is a novel method to select centers using the min cost network flow approach. Finally, we conduct experiments to validate our algorithm. The experimental results show that the clustering cost of our algorithm, while simultaneously considering both of the GF and DS constraints, is nearly identical to that of the clustering algorithm which only considers the GF constraint.

The rooted max tree coverage (MTC) problem has wide applications in areas, such as network design and vehicle routing. Given a graph with non-negative costs defined on edges, a vertex used as the root, and a budget, the rooted MTC problem asks to find a tree containing the root and having total cost at most the budget, so that the number of vertices spanned by the tree is maximized. Rooted MTC is NP-hard and has constant factor approximation algorithms. However, the existing approximation algorithms for rooted MTC are very complicated and hard to be implemented practically. In this article, we formulate a polynomial size mixed integer linear program (MILP) for rooted MTC for the first time. Based on this, we develop a simple evolutionary algorithm for rooted MTC (called CMSA-MTC) using the CMSA meta-heuristic, where construct, merge, solve, and adapt (CMSA) is a meta-heuristic proposed recently. Experimental results show that CMSA-MTC has very good practical performance. For the small size instances of the problem, CMSA-MTC almost always finds the optimal solutions. For the large size instances, CMSA-MTC finds solutions better than that of CPLEX within the same running time and two additional greedy algorithms.

Computer networks are often multi-layered. For simplicity, let us focus on two-layered networks with logical layer and physical layer. Such a network can be modeled as a labeled graph$G = (V, E)$with a label set$L = \{\ell _{1}, \ell _{2}, {\dots }, \ell _{q} \}$, in which each edge (denotes logical connection)$e \in E$has a label (denotes physical link)$\ell (e)$from L. The key issue is that different edges may have the same label. In the weighted minimum Label s-t Cut problem, we are given a labeled graph$G=(V,E)$with label set L, where each label$\ell $has a nonnegative weight$w_{\ell } $, a source$s \in V$and a sink$t \in V$. The problem asks to find a minimum weight label subset$L'$(called a label s-t cut) such that the removal of all edges with labels in$L'$disconnects s and t. Label s-t cut depicts the connectivity bottleneck of a layered network. It is a natural generalization of the edge connectivity of a graph. In this paper, we provide an approximation algorithm for the weighted Label s-t Cut problem with ratio$O(n^{2/3})$, where n is the number of vertices. This is the first approximation algorithm for the problem whose ratio is given in terms of n. The key point of the algorithm is a mechanism to interpret label weight on an edge as both its length (as in the Shortest s-t Path problem) and capacity (as in the Min s-t Cut problem). Experiments on random graphs show that the algorithm has also good practical performance.

The maximum duo-preservation string mapping (Max-Duo) problem is the complement of the well studied minimum common string partition (MCSP) problem, both of which have applications in many fields including text compression and bioinformatics. k-Max-Duo is the restricted version of Max-Duo, where every letter of the alphabet occurs at most k times in each of the strings, which is readily reduced into the well known maximum independent set (MIS) problem on a graph of maximum degree \Delta \le 6(k-1). In particular, 2-Max-Duo can then be approximated arbitrarily close to 1.8 using the state-of-the-art approximation algorithm for the MIS problem. 2-Max-Duo was proved APX-hard and very recently a (1.6 + \epsilon)-approximation was claimed, for any \epsilon > 0. In this paper, we present a vertex-degree reduction technique, based on which, we show that 2-Max-Duo can be approximated arbitrarily close to 1.4.

A mobile ad hoc network (MANET) is a self-organised system comprised of mobile wireless nodes. All nodes act as both communicators and routers. Owing to multi-hop routing and absence of centralised administration in open environment, MANETs are vulnerable to attacks by malicious nodes. In order to decrease the hazards from malicious nodes, the authors incorporate the concept of trust to MANETs and build a simple trust model to evaluate neighbours’ behaviours – forwarding packets. Extended from the ad hoc on-demand distance vector (AODV) routing protocol and the ad hoc on-demand multipath distance vector (AOMDV) routing protocol, a trust-based reactive multipath routing protocol, ad hoc on-demand trusted-path distance vector (AOTDV), is proposed for MANETs. This protocol is able to discover multiple loop-free paths as candidates in one route discovery. These paths are evaluated by two aspects: hop counts and trust values. This two-dimensional evaluation provides a flexible and feasible approach to choose the shortest path from the candidates that meet the requirements of data packets for dependability or trust. Furthermore, the authors give a routing example in details to describe the procedures of route discovery and the differences among AODV, AOMDV and AOTDV. Several experiments have been conducted to compare these protocols and the results show that AOTDV improves packet delivery ratio and mitigates the impairment from black hole, grey hole and modification attacks.