Improveddeterministicalgorithmsforweightedmatchingandpackingproblems资源-CSDN文库

160 浏览量 2021-02-21 11:25:25 上传评论收藏 281KB PDF 举报

这篇文章的主题是关于加权匹配和打包问题的改进型确定性算法，作者通过使用(n,k)-通用集合方法，提出了一种新的确定性参数化算法。文章主要关注加权rd-匹配问题（r≥3）和加权r-集合打包问题，并给出了时间复杂度的上界改进。知识点详细解释如下： 1. NP-hard问题：文章提及的匹配和打包问题是NP-hard（非确定性多项式时间难题）问题的一个重要类别。特别是在这些难题中，3-匹配问题是六个“基本”的NP完全问题之一。NP完全问题是指那些不仅属于NP类（能够使用非确定性图灵机在多项式时间内解决的问题集合），而且任何其他NP问题都可以在多项式时间内归约到该问题的问题。 2. 加权rd-匹配问题：这是一个问题，给定一组由r个集合的笛卡尔积中的元素组成的r元组（r元组集合S），并且每个元组都有一个权重值。问题的目标是找到一个大小为kr的r元组子集S'，使得这些元组的权重和最大，同时保证在这个子集中的任意两个元组不共享同一位置上的元素。文章中提到的算法针对的是权重值已给出的情况。 3. 加权r-集合打包问题：在这个问题中，需要从r个集合中选择一组子集，使得这些子集中的元素不重叠，并且总体重量最大。和加权rd-匹配问题类似，这也是一个需要解决的加权版本的问题。 4. (n,k)-通用集合方法：文章使用(n,k)-通用集合方法提出了一种新的确定性参数化算法。这种方法在计算机科学的算法理论领域经常用来构建快速的算法。通用集合是一种使得从较小集合中任意选择一些元素能够覆盖较大集合中所有元素的组合对象。 5. 时间复杂度改进：在介绍算法时，文章特别提到了时间复杂度的改进。算法的时间复杂度通常表示解决问题所需运算量的增长率。通过改进算法，文章中提到的算法能够以更短的时间复杂度O*(某个表达式)解决问题，其中“O*”表示忽略多项式因子的渐近上界。例如，之前的最佳结果是O*(4rk+o(k))，而文章提出的算法将时间复杂度改进至O*(4(r-1)k+o(k))。 6. 核化算法：文章还提出了一种核化算法，这是一种减少问题实例大小的技术，目的是将问题实例简化到核心，核心是一个较小的实例，包含原问题的所有核心特征。核化通常用于预处理阶段，以提高算法处理大规模实例时的效率。对于加权版本的问题，作者首次给出了核化算法。 7. 无权版本问题的改进：对于无权版本的3d-匹配问题和3-集合打包问题，作者也提供了确定性的算法，并且改进了它们的运行时间。文章详细介绍了运用(n,k)-通用集合方法，对加权匹配和打包问题进行求解的确定性算法，并对这些NP-hard问题的时间复杂度进行了显著改进。此外，作者还为加权版本的问题提供了一个新的核化算法，这在之前的研究中是前所未有的。通过这些技术，算法在实际应用中可能更加高效，尤其是在处理大规模数据时。

资源推荐

资源详情

资源评论

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

, Yang Liu

, Songjian Lu

, Jianxin Wang

a,∗

School of Information Science and Engineering, Central South University, Changsha 410083, PR China

Department of Computer Science and Engineering, Texas A&M University, College Station, TX 77843, USA

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

∗

(r−1)k+o(k)

improving the previous best upper bound O

∗

rk+o(k)

). In particular, the algorithm applied

to the unweighted 3d-matching problem results in a deterministic algorithm with time

∗

(16

k+o(k)

), improving the previous best result O

∗

(21.26

). For the weighted r-set pack-

ing problem, we present a deterministic parameterized algorithm with time complexity

∗

(2r−1)k+o(k)

), improving the previous best result O

∗

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

), which is the first kernel-

ization algorithm for the problems on weighted versions.

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

× A

× · · · × A

of r-tuples and an integer k, where A

, A

, . . . , A

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).

doi:10.1016/j.tcs.2010.10.042

2504 J. Chen et al. / Theoretical Computer Science 412 (2011) 2503–2512

Table 1

Comparison of deterministic algorithms for matching.

References Time complexity 3DM rDM W3DM WrDM Remark

[4] O

∗

((rk)!(rk)

3rk

) X X X X

[5] O

∗

5rk−4k



6(r−1)k+k



) X X X X

[11] O

∗

(12.8

) X X X X

[2] O

∗

rk+o(k)

) X X X X

Our result O

∗

(r−1)k+o(k)

) X X X X

[15] O

∗

(432

k+o(k)

) X X r = 3 only

Our result O

∗

(16

k+o(k)

) X X r = 3

[1] O

∗

((r − 1)

((r − 1)k/e)

k(r−2)

) X X × ×

[9] O

∗

O(rk)

) X X × ×

[16] O

∗

(43.62

k+o(k)

) X × r = 3 only

[12] O

∗

(21.26

) X × r = 3 only

[10] O

∗

) (randomized) X × r = 3 only

problem is a general extension of the rd-matching problem. Therefore, all parameterized algorithms for r-set packing can

also be used to solve rd-matching. The weighted rd-matching and weighted r-set packing problems were first studied by

Downey and Fellows [4], where a deterministic parameterized algorithm of time complexity O

∗

((rk)!(rk)

3rk

) was presented.

An improved deterministic algorithm for the weighted rd-matching and weighted r-set packing problems was proposed by

Fellows et al. [5] with running time O

∗

5rk−4k



6(r−1)k+k



). Liu et al. [11] further reduced the time complexity to O

∗

(12.8

For weighted 3d-matching, Wang and Feng [15] gave a more efficient algorithm of time complexity O

∗

(7.56

3k+o(k)

) =

∗

(432

k+o(k)

). Currently, the best deterministic algorithms for the weighted rd-matching and weighted r-set packing

problems are due to Chen et al. [2] with time complexity O

∗

rk+o(k)

We remark that there is also a very active research line on parameterized algorithms for unweighted versions of the

problems. Using the technique of Greedy Localization, Chen et al. [1] and Jia et al. [8] presented deterministic algorithms

for the unweighted rd-matching and r-set packing problems of time O

∗

((r − 1)

((r − 1)k/e)

k(r−2)

). Koutis [9] gave an

improved deterministic algorithm of time O

∗

O(rk)

). For the case of r = 3, Liu et al. [12] presented a deterministic algorithm

of time O

∗

(21.26

) for the unweighted 3d-matching problem, which is currently the best deterministic algorithm for the

unweighted 3d-matching problem. For the unweighted 3-set packing problem, Liu et al. [12] gave a deterministic algorithm

of time O

∗

(97.98

), which was further improved by Wang and Feng [16] with an algorithm of time O

∗

(43.62

k+o(k)

). This is

currently the best deterministic algorithm for the unweighted 3-set packing problem. It should be pointed out that all these

algorithms [1,8,9,12,16] seem to work only for unweighted versions and cannot be applied to solve the weighted versions.

Very recently, Koutis [10] proposed a randomized algorithm of time complexity O

∗

) for the unweighted 3d-matching

and 3-set packing problems. However, as remarked in [17], the algorithms in [10] only work for unweighted case and do

not appear to extend to the weighted versions. Moreover, whether the algorithms can be extended to rd-matching and

r-set packing for r > 3, and whether the randomized algorithms can be derandomized are still unknown.

In this paper, we study the weighted versions of rd-matching and r-set packing, and develop a different algorithmic

approach to the problems. In particular, after further analyzing the structure of the problems and using (n, k)-universal

sets and the divide-and-conquer methods, we are able to develop a deterministic algorithm of time O

∗

(r−1)k+o(k)

) for the

weighted rd-matching problem, improving the previous best result O

∗

rk+o(k)

). In fact, our deterministic algorithms for

the weighted cases are even better than the previous best deterministic algorithm for the unweighted cases. For example,

our algorithm for weighted 3d-matching runs in time O

∗

(16

k+o(k)

), which is much better than the previous best algorithm

of time O

∗

(21.26

) for unweighted 3d-matching.

Table 1 provides a comprehensive comparison of deterministic algorithms for the rd-matching problems, where ‘‘X’’

denotes that the algorithm can be applied to the problem, ‘‘×’’ denotes that the algorithm is not applicable to the problem,

and 3DM, W3DM, rDM, and WrDM denote unweighted 3d-matching, weighted 3d-matching, unweighted rd-matching,

and weighted rd-matching, respectively. We have partitioned the algorithms into three groups. In the first group (the

first 5 rows in the table), we compare our algorithm with previous algorithms that are applicable to rd-matching for a

general integer r ≥ 3 and for both weighted and unweighted versions. In the second group, consisting of rows 6–7 in the

table, we compare our algorithm with the best previous algorithm for 3d-matching for both weighted and unweighted

versions. Finally, the last group, consisting of rows 8–12 in the table, lists all previous algorithms that are only applicable

to unweighted version of rd-matching. As we can see, our algorithm improves all previous algorithms significantly, except

the last row, which, as we have mentioned above, seems difficult to be derandomized and/or extended to general integer

r > 3.

For the weighted r-set packing problem, we also develop an improved deterministic algorithm. By further analyzing

the structure of the problem, we present an algorithm of time O

∗

(2r−1)k+o(k)

) for weighted r-set packing, improving the

Following the recent convention, for a given function f , we will use the notion O

∗

(f ) for O(f · n

O(1)

剩余9页未读，继续阅读

评论收藏

内容反馈

weixin_38611388

粉丝: 10
资源: 971

Improved deterministic algorithms for weighted matching and pack...

最新资源

Improved deterministic algorithms for weighted matching and pack...

Improved sparsity adaptive matching pursuit algorithm

Improved feature processing for Deep Neural Networks

Improved cross-correlation for template matching on the Laplacian pyramid .pdf

Hybrid Genetic-Immune Algorithm with Improved Offsprings and Elitist Antigen for Flow-Shop Scheduling Problems

Improved Residual Networks for Image and Video Recognition.pdf

Improved Boosting Algorithms

2018 Improved Techniques for Learning to Dehaze and Beyond_ A Collective Study

Improved Sigma Filter for Speckle

Optimizing Java Practical Techniques for Improved

The improved genetic algorithms for digital image correlation method

Improved ChaoticGravitational Search Algorithms for Global Optimization

Packing Techniques for Virtex-5 FPGAs 2009.pdf

论文研究-基于应用层负载均衡策略的分析与研究.pdf

《算法导论》(Introduction to Algorithms) 英文 文字版

Deep Learning Networks for Stock Market Analysis and Prediction

Application of improved Grey prediction model for settlement prediction of roadbed

An improved method for calculating the no-fit polygon

Segment-Tree based Cost Aggregation for Stereo Matching code

Options and Derivatives Programming in C++

算法导论 第三版 Introduction to Algorithms, Third Edition

Computational Geometry in C

Algebraic Graph Algorithms Lecture Notes (Stanford CS367)

算法导论--Introduction.to.Algorithms

Advances in Feature Selection for Data and Pattern Recognition

an improved illumination model for shaded display

最新资源

《算法导论》(Introduction to Algorithms) 英文文字版

算法导论第三版 Introduction to Algorithms, Third Edition