Theoretical Computer Science 412 (2011) 2503–2512
Contents lists available at ScienceDirect
Theoretical Computer Science
journal homepage: www.elsevier.com/locate/tcs
Improved deterministic algorithms for weighted matching and
packing problems
✩
Jianer Chen
a,b
, Qilong Feng
a
, Yang Liu
c
, Songjian Lu
b
, Jianxin Wang
a,∗
a
School of Information Science and Engineering, Central South University, Changsha 410083, PR China
b
Department of Computer Science and Engineering, Texas A&M University, College Station, TX 77843, USA
c
Department of Computer Science, University of Texas-Pan American, Edinburg, TX 78539, USA
a r t i c l e i n f o
Keywords:
rd-matching
r-set packing
Randomized divide-and-conquer
(n, k)-universal set
a b s t r a c t
Based on the method of (n, k)-universal sets, we present a deterministic parameterized
algorithm for the weighted rd-matching problem with time complexity O
∗
(4
(r−1)k+o(k)
),
improving the previous best upper bound O
∗
(4
rk+o(k)
). In particular, the algorithm applied
to the unweighted 3d-matching problem results in a deterministic algorithm with time
O
∗
(16
k+o(k)
), improving the previous best result O
∗
(21.26
k
). For the weighted r-set pack-
ing problem, we present a deterministic parameterized algorithm with time complexity
O
∗
(2
(2r−1)k+o(k)
), improving the previous best result O
∗
(2
2rk+o(k)
). The algorithm, when ap-
plied to the unweighted 3-set packing problem, has running time O
∗
(32
k+o(k)
), improv-
ing the previous best result O
∗
(43.62
k+o(k)
). Moreover, for the weighted r-set packing and
weighted rd-matching problems, we give a kernel of size O(k
r
), which is the first kernel-
ization algorithm for the problems on weighted versions.
© 2010 Elsevier B.V. All rights reserved.
1. Introduction
Matching and packing problems form an important class of NP-hard problems. In particular, the 3d-matching problem
is one of the six ‘‘basic’’ NP-complete problems [7]. In this paper, we are mainly focused on the weighted rd-matching and
weighted r-set packing problems, for r ≥ 3, which are formally defined as follows.
Weighted rd-matching: Given a collection S ⊆ A
1
× A
2
× · · · × A
r
of r-tuples and an integer k, where A
1
, A
2
, . . . , A
r
are pair-wise disjoint sets and each r-tuple in S has a weight value, find a subcollection S
′
of k r-tuples in S with the
maximum weight sum such that no two r-tuples in S
′
have common elements, or report that no such subcollection
exists.
Weighted r-set packing: Given a collection S of r-sets (i.e., sets that contain exactly r elements) and an integer k,
where each r-set in S has a weight value, find a subcollection S
′
of k r-sets in S with the maximum weight sum such
that no two r-sets in S
′
have common elements, or report that no such subcollection exists.
Parameterized algorithms for rd-matching and r-set packing have been an active research line, whose running time
are bounded by a polynomial of the input size n times a function f (k) of the parameter k. First note that the r-set packing
✩
A preliminary version of this work was reported in the Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation,
Lecture Notes in Computer Science, vol. 5532, 2009, pp. 211–220. This work is supported in part by the National Science Foundation of USA under grant
CCF-0830455, by the National Natural Science Foundation of China (No. 60773111, 61073036, 61070224), the Doctoral Discipline Foundation of Higher
Education Institution of China under Grant 20090162110056.
∗
Corresponding author.
E-mail address: jxwang@mail.csu.edu.cn (J. Wang).
0304-3975/$ – see front matter © 2010 Elsevier B.V. All rights reserved.
doi:10.1016/j.tcs.2010.10.042
剩余9页未读，继续阅读
资源评论
