排序方式: 共有5条查询结果,搜索用时 15 毫秒
1
1.
Given a graph G=(V,E) with node weight w:V→R
+ and a subset S⊆V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard
and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NP⊆DTIME(n
O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a
polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs.
As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial
time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs. 相似文献
2.
Jun Guo Yuexuan Wang Suogang Gao Jiangchen Yu Weili Wu 《Journal of Combinatorial Optimization》2010,20(4):413-421
We construct a family of error-correcting pooling designs with the incidence matrix of two types of subspaces of symplectic
spaces over finite fields. We show that the new construction gives better ratio of efficiency compared with previously known
three constructions associated with subsets of a set, its analogue over a vector space, and the dual spaces of a symplectic
space. 相似文献
3.
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.
相似文献4.
Zengti Li Suogang Gao Hongjie Du Feng Zou Weili Wu 《Journal of Combinatorial Optimization》2010,20(4):325-334
In this paper, we construct two classes of t×n,s
e
-disjunct matrix with subspaces in orthogonal space
\mathbbFq(2n+1)\mathbb{F}_{q}^{(2\nu+1)}
of characteristic 2 and exhibit their disjunct properties. We also prove that the test efficiency t/n of constructions II is smaller than that of D’yachkov et al. (J. Comput. Biol. 12:1129–1136, 2005). 相似文献
5.
Let Γ be a d-bounded distance-regular graph with diameter d≥2. In this paper, we construct two new classes of error-correcting pooling designs from the posets consisting of the subspaces
of Γ. 相似文献
1