排序方式: 共有5条查询结果,搜索用时 15 毫秒
1
1.
2.
Zheng Hongye Gao Suogang Liu Wen Wu Weili Du Ding-Zhu Hou Bo 《Journal of Combinatorial Optimization》2022,44(1):343-353
In this paper, we consider the parallel-machine scheduling problem with release dates and submodular rejection penalties. In this problem, we are given m identical parallel machines and n jobs. Each job has a processing time and a release date. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalty of the rejected jobs which is determined by a submodular function. Our main work is to design a 2-approximation algorithm based on the primal-dual framework.
相似文献3.
Locating source of information diffusion in networks has very important applications such as locating the sources of epidemics, news/rumors in social networks or online computer virus. In this paper, we consider detecting multiple rumor sources from a deterministic point of view by modeling it as the set resolving set (SRS) problem. Let G be a network on n nodes. A node subset K is an SRS of G if all detectable node sets are distinguishable by K. The problem of multiple rumor source detection (MRSD) in the network can be modeled as finding an SRS K with the smallest cardinality. In this paper, we propose a polynomial-time greedy algorithm for finding a minimum SRS in a general network, achieving performance ratio \(O(\ln n)\). This is the first work establishing a relation between the MRSD problem and a deterministic concept of SRS, and a first work to give the minimum SRS problem a polynomial-time performance-guaranteed approximation algorithm. Our framework suggests a robust and efficient approach for estimating multiple rumor sources independent of diffusion models in networks. 相似文献
4.
5.
1