This paper addresses the scheduling problem in mobile social networks, an$\mathcal {NP}$-hard problem. First, we identified a gap in the approximation analysis of Zhanget al(IEEE Transactions on Mobile Computing, 2025) and provided a revised bound. Furthermore, when the required service time for a task exceeds the total contact time between the requester and the crowd worker, we demonstrate that the approximation ratio of the Largest-Ratio-First task scheduling algorithm can reach$2 - \frac{1}{m}$. Next, we introduce a randomized approximation algorithm to minimize mobile social networks' total weighted completion time. This algorithm achieves an expected approximation ratio of$1.5 + \epsilon$for$\epsilon \gt 0$. Finally, we present a deterministic approximation algorithm that minimizes mobile social networks' total weighted completion time. This deterministic algorithm achieves an approximation ratio of$\max \lbrace 2.5,1+\epsilon \rbrace$for$\epsilon \gt 0$. Additionally, when the task's required service time or the total contact time between the requester and the crowd worker is sufficiently large, this algorithm can reach an approximation ratio of$1.5+\epsilon$for$\epsilon \gt 0$.

This paper addresses the scheduling problem of coflows in identical parallel networks, a well-known N P-hard problem. We consider both flow-level scheduling and coflow-level scheduling problems. In the flow-level scheduling problem, flows within a coflow can be transmitted through different network cores, while in the coflow-level scheduling problem, flows within a coflow must be transmitted through the same network core. The key difference between these two problems lies in their scheduling granularity. Previous approaches relied on linear programming to solve the scheduling order. In this paper, we enhance the efficiency of solving by utilizing the primal-dual method. For the flow-level scheduling problem, we propose an approximation algorithm that achieves approximation ratios of$6-\frac{2}{m}$and$5-\frac{2}{m}$for arbitrary and zero release times, respectively, where m represents the number of network cores. Additionally, for the coflow-level scheduling problem, we introduce an approximation algorithm that achieves approximation ratios of 4m + 1 and 4m for arbitrary and zero release times, respectively. The algorithm presented in this paper has practical applications in data centers, such as those operated by Google or Facebook. The simulated results demonstrate the superior performance of our algorithms compared to previous approach, emphasizing their practical utility.

This paper focuses on the problem of coflow scheduling with precedence constraints in identical parallel networks, a well-known$\mathcal {NP}$-hard problem. Coflow is a relatively new network abstraction that characterizes communication patterns in data centers. When considering workload sizes and weights that are dependent on the network topology in the input instances, the proposed algorithm for the flow-level scheduling problem achieves an approximation ratio of$O(\chi )$where$\chi$is the coflow number of the longest path in the directed acyclic graph (DAG). Additionally, when taking into account topology-dependent workload sizes, the algorithm achieves an approximation ratio of$O(R\chi )$, where$R$represents the ratio of maximum weight to minimum weight. For the coflow-level scheduling problem, the proposed algorithm achieves an approximation ratio of$O(m\chi )$, where$m$is the number of network cores when considering workload sizes and weights that are topology-dependent. Moreover, when considering topology-dependent workload sizes, the algorithm achieves an approximation ratio of$O(Rm\chi )$. In the coflows of multi-stage job scheduling problem, the proposed algorithm achieves an approximation ratio of$O(\chi )$. Although our theoretical results are based on a limited set of input instances, experimental findings show that the results for general input instances outperform the theoretical results.

Coflow is a network abstraction used to represent communication patterns in data centers. The coflow scheduling problem encountered in large data centers is a challenging NP-hard problem. Many previous studies on coflow scheduling mainly focus on the single-core model. However, with the growth of data centers, this single-core model is no longer sufficient. This paper addresses the coflow scheduling problem within heterogeneous parallel networks, which feature an architecture consisting of multiple network cores running in parallel. In this paper, two polynomial-time approximation algorithms are developed for the flow-level scheduling problem and the coflow-level scheduling problem in heterogeneous parallel networks, respectively. For the flow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O(log⁡m/log⁡log⁡m) when all coflows are released at arbitrary times, where m represents the number of network cores. On the other hand, in the coflow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O(m(log⁡m/log⁡log⁡m)2) when all coflows are released at arbitrary times. Moreover, we propose a heuristic algorithm for the flow-level scheduling problem. Simulation results using synthetic traffic traces validate the performance of our algorithms and show improvements over the previous algorithm.

Abstract In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be $${\mathsf {NP}}$$ NP -complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is $${\mathsf {NP}}$$ NP -complete on graphs with minimum degree two. In this paper, we show that, for any given constant $$c>1$$ c > 1 , Matching Cut is $${\mathsf {NP}}$$ NP -complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant $$\epsilon >0$$ ϵ > 0 , Matching Cut remains $${\mathsf {NP}}$$ NP -complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree $$\delta >n^{1-\epsilon }$$ δ > n 1 - ϵ . We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree $$\delta \ge 3$$ δ ≥ 3 in $$O^*(\lambda ^n)$$ O ∗ ( λ n ) time, where $$\lambda$$ λ is the positive root of the polynomial $$x^{\delta +1}-x^{\delta }-1$$ x δ + 1 - x δ - 1 . Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is $$O^*(1.0099^n)$$ O ∗ ( 1 . 0099 n ) on graphs with minimum degree $$\delta \ge 469$$ δ ≥ 469 . Complementing our hardness results, we show that, for any two fixed constants $$1< c <4$$ 1 < c < 4 and $$c^{\prime }\ge 0$$ c ′ ≥ 0 , Matching Cut is solvable in polynomial time for graphs with large minimum degree $$\delta \ge \frac{1}{c}n-c^{\prime }$$ δ ≥ 1 c n - c ′ .

The problem of scheduling malleable tasks with precedence constraints is one of the most important strongly NP-hard problems, given m identical processors and n tasks. A malleable task is one that runs in parallel on a varying number of processors. In addition, the processing sequences of tasks are constrained by the precedence constraints. The goal is to find a feasible schedule that minimizes the makespan (maximum completion time). This article presents an iterative method for improving the performance ratio of scheduling malleable tasks. The proposed algorithm achieves an approximation ratio of 4.4841 after 2 iterations. This improves the so far best-known factor of 4.7306 due to Jansen and Zhang. For a large number of iterations (> 100), the approximation ratio of the proposed algorithm is tends toward 2 + √2 ≈ 3.4143.

This work investigates the problem of a non-linear divisible load distribution on a homogeneous linear network. A novel computational model of non-linear loads that includes complete steps for processing them, is proposed. This model solves the problem of the classical model, whose performance degrades by separating the load. This work also presents an algorithm S (Single-installment) that uses single-installment processing to distribute a non-linear divisible load on a homogeneous linear network. An algorithm M (Multi-installment) that applies multi-installment processing to reduce the initial distribution time for load is also proposed. Closed-form expressions for the parallel processing time and speed-up of the proposed algorithms are derived. The speed-up of algorithm S is much better than that of the classical algorithm that is based on the classical model. Algorithm M outperforms algorithm S in terms of speed-up when the load to be processed is very large or when the start-up costs are small.

Machine and network failures worsen the results of executing applications on system. Therefore, the reliability of applications on system is an important issue. The recovery of failed machines may increase processing time. This work studies the expected makespan to schedule tasks in heterogeneous distributed systems. A task may be replicated many times to reduce the expected execution time. A two-phase algorithm is proposed. The first phase uses a linear program formulation and a rounding procedure to obtain a favorable allotment to minimize the expected makespan. The second phase applies a scheduling method that is based on the expected executed time and the communication time. During execution, two strategies are considered. In the first strategy, no replication of a task on a set of processors can be stopped. In the second strategy, once a replication of a task has been completed, the other replications of the task are immediately aborted. A comparison reveals that the proposed algorithm significantly outperformed previously proposed algorithms in terms of schedule length ratio, reliability and speedup.

This work investigates divisible load distribution using multi-installment processing on completeb-ary tree networks. Classic methods of distributing a divisible load divide the computation and communication processes into multiple time intervals in a pipelined fashion. The algorithm$\mathbb {M}$(multi-installment) herein uses multi-installment processing with pipelined communication to reduce the initial distribution time and to improve the performance. Closed-form expressions for the parallel processing time and speed-up are derived. This work reveals that the asymptotic speed-up of the proposed algorithm is$b\beta +1$where$\beta$is the computation-to-communication ratio of a node in the system. Algorithm$\mathbb {M}$outperforms the classic algorithm in all cases. The algorithm$\mathbb {S}$(start-up cost) that is developed herein includes the computation and communication start-up costs. Finally, two algorithms$\mathbb {M}$and$\mathbb {S}$are combined to form algorithm$\mathbb {MS}$with even better performance than each.

Scheduling malleable tasks under general precedence constraints involves finding a minimum makespan (maximum completion time) by a feasible allotment. Based on the monotonous penalty assumptions of Blayo et al. [2], this work defines two assumptions concerning malleable tasks: the processing time of a malleable task is nonincreasing in the number of processors, while the work of a malleable task is nondecreasing in the number of processors. Additionally, the work function is assumed herein to be convex in the processing time. The proposed algorithm reformulates the linear program of [11], and this algorithm and associated proofs are inspired by the ones of [11]. This work describes a novel polynomial-time approximation algorithm that is capable of achieving an approximation ratio of 2+√2≈3.4142. This work further demonstrates that the proposed algorithm can yield an approximation ratio of 2.9549 when the processing time is strictly decreasing in the number of the processors allocated to the task. This finding represents an improvement upon the previous best approximation ratio of 100/63+100(√6469+137)/5481≈3.2920 [12] achieved under the same assumptions.

In the divisible load distribution, the classic methods on linear arrays divide the computation and communication processes into multiple time intervals in a pipelined fashion. Li (2003) has proposed a set of improved algorithms for linear arrays which can be generalized to k-dimensional meshes. In this paper, we first propose the algorithm M (multi-installment) that employs the multi-installment technique to improve the best algorithm Q proposed by Li. Second, we propose the algorithm S (start-up cost) that includes the computation and communication start-up costs in the design. While the asymptotic speedups of our algorithms M and S derived from the closed-form solutions are the same as algorithm Q, our algorithms approach the optimal speedups considerably faster than algorithm Q as the number of processors increases. Finally, we combine algorithms M and S and propose the algorithm MS. While algorithm MS has the same the asymptotic performance as algorithms Q and S, it achieves a better speedup when the load to be processed is very large and the number of processors is fixed or when the load to be processed is fixed and the number of processors is small.