To address the issue that static densest subgraph mining algorithms often exhibit low efficiency when handling large scale dynamic graphs,this paper proposes a heuristic approximation algorithm.The algorithm approxima...To address the issue that static densest subgraph mining algorithms often exhibit low efficiency when handling large scale dynamic graphs,this paper proposes a heuristic approximation algorithm.The algorithm approximates the densest k-subgraphs of the entire graph through four steps:partitioning the large-scale dynamic graph,constructing a partial set of the densest k-subgraphs,heuristically merging the subgraph sets,and finally extracting the densest k-subgraphs.This approach significantly reduces the computational time for large-scale dynamic graphs while simultaneously improving the quality of the resulting subgraphs.This algorithm is applicable to various definitions of“density”and can accommodate diverse requirements on the number of edges.When integrated with existing static densest subgraph detection algorithms,it achieves scalability and computational efficiency.Theoretical analysis demonstrates that the optimal density of the densest k-subgraphs extracted by the proposed algorithm reaches 0.9.To evaluate the performance of the algorithm,experiments were conducted on four billion-scale datasets:Friendster,Orkut,YouTube,and DBLP.The results indicate that the proposed algorithm outperforms static methods in both runtime efficiency and subgraph quality on large-scale dynamic graphs.展开更多
There are a variety of joint job production and transportation scheduling problems that arise in modern manufacturing systems.In this paper,we study one of such problems that arises in a flowshop environment where the...There are a variety of joint job production and transportation scheduling problems that arise in modern manufacturing systems.In this paper,we study one of such problems that arises in a flowshop environment where there are two processing stages and a single transporter that is available to deliver the finished jobs from the first stage to the second.There is a single machine in the first stage and two parallel machines in the second stage.The transporter can carry only one job in each shipment.Each job is first processed on the single machine at stage one,then transported to and processed on one of the two parallel machines at stage two.The objective is to minimize the makespan,i.e.,the completion time of the last job in the second stage.Since this problem is strongly NP-hard,we propose a fast heuristic and show that the heuristic has a worst-case bound of 5/2.We also conduct1 numerical experiments to evaluate the average performance of this heuristic.展开更多
基金The National Natural Science Foundation of China(No.62172443).
文摘To address the issue that static densest subgraph mining algorithms often exhibit low efficiency when handling large scale dynamic graphs,this paper proposes a heuristic approximation algorithm.The algorithm approximates the densest k-subgraphs of the entire graph through four steps:partitioning the large-scale dynamic graph,constructing a partial set of the densest k-subgraphs,heuristically merging the subgraph sets,and finally extracting the densest k-subgraphs.This approach significantly reduces the computational time for large-scale dynamic graphs while simultaneously improving the quality of the resulting subgraphs.This algorithm is applicable to various definitions of“density”and can accommodate diverse requirements on the number of edges.When integrated with existing static densest subgraph detection algorithms,it achieves scalability and computational efficiency.Theoretical analysis demonstrates that the optimal density of the densest k-subgraphs extracted by the proposed algorithm reaches 0.9.To evaluate the performance of the algorithm,experiments were conducted on four billion-scale datasets:Friendster,Orkut,YouTube,and DBLP.The results indicate that the proposed algorithm outperforms static methods in both runtime efficiency and subgraph quality on large-scale dynamic graphs.
基金The research was supported by the National Natural Science Foundation of China Grants(No.11301327).
文摘There are a variety of joint job production and transportation scheduling problems that arise in modern manufacturing systems.In this paper,we study one of such problems that arises in a flowshop environment where there are two processing stages and a single transporter that is available to deliver the finished jobs from the first stage to the second.There is a single machine in the first stage and two parallel machines in the second stage.The transporter can carry only one job in each shipment.Each job is first processed on the single machine at stage one,then transported to and processed on one of the two parallel machines at stage two.The objective is to minimize the makespan,i.e.,the completion time of the last job in the second stage.Since this problem is strongly NP-hard,we propose a fast heuristic and show that the heuristic has a worst-case bound of 5/2.We also conduct1 numerical experiments to evaluate the average performance of this heuristic.
