ApproximatingMaximumWeightMatchinginNear-linearTime.pdf资源-CSDN下载

需积分: 9 67 浏览量 2019-08-10 21:15:19 上传评论收藏 1.25MB PDF 举报

最大权重匹配问题（Maximum Weight Matching Problem, MWM）是图论中的一个经典问题，它涉及在一个带权图中找到一组顶点不相交的边，使得这些边的总权重最大。1960年代，Edmonds提出了多项式时间算法来解决这一问题。目前最快的MWM算法由Gabow和Tarjan提出，运行时间大致为O(mn)，其中m和n分别是图中的边数和顶点数。尽管已经有许多更快速的算法问世，但这些算法对于稀疏图而言，并不明显简化。目前对于计算(1−ε)-近似最大权重匹配或最大基数匹配等问题，最优算法的运行时间也大致在O(mn)级别。在文档中提到的研究内容里，作者Ran Duan和Seth Pettie提出了第一个近似最大权重匹配问题的近似算法，该算法能在接近线性的时间内解决问题。具体来说，给定任意带有实数权重的图和一个小于1的参数ε>0，他们的算法能在O(mε^(-2)log^3n)时间内计算出一个(1−ε)-近似最大权重匹配。这比之前的近似算法提供了更好的近似保证，之前的算法在近似比例上只能达到2/3−ε。另外，作者还提出了一种更快的算法，能在O(mlognlog(1/ε)^(-1))时间内计算出一个3/4−ε近似最大权重匹配。这些算法的提出不仅改进了最大权重匹配问题的求解效率，而且还对相关领域的研究产生了积极的影响。最大匹配问题的历史与现代图论、组合优化、矩阵理论的发展紧密相连，多项式时间可解性与可行性研究交织在一起。在二分图中，寻找最大基数匹配问题可以通过多项式时间算法来解决，但在一般图中就不那么直接了。Edmonds在1965年提出的用于一般图的最大基数匹配（Maximum Cardinality Matching, MCM）和最大权重匹配（Maximum Weight Matching, MWM）问题的多项式时间算法，开启了后续研究的序幕，后续研究通常基于新的结构特征和算法改进。通过这些研究，我们可以发现最大权重匹配问题不仅在理论上有其深刻的数学意义，而且在实际应用中也有广泛的用途。例如，它可以被应用于分配问题、调度问题以及网络设计等多个方面。相关算法的研究和改进，推动了计算机科学以及相关领域的进步，特别是在计算复杂性和图论算法设计方面。对于开发者和研究人员来说，这篇文章不仅提供了一种高效的近似算法，而且为研究者提供了对现有算法进行改进的新思路，激励着他们在这一领域继续探索和创新。同时，对于正在学习图论和算法设计的学生和专业人士，该研究提供了深入理解最大匹配问题的机会，并且能够帮助他们掌握在近似算法设计和分析方面的重要知识。

资源推荐

资源详情

资源评论

Approximating Maximum Weight Matching in Near-linear Time

Ran Duan

EECS Department

University of Michigan

Ann Arbor, MI

duanran@umich.edu

Seth Pettie

EECS Department

University of Michigan

Ann Arbor, MI

[email protected]

Abstract—Given a weighted graph, the maximum weight

matching problem (MWM) is to ﬁnd a set of vertex-disjoint

edges with maximum weight. In the 1960s Edmonds showed

that MWMs can be found in polynomial time. At present the

fastest MWM algorithm, due to Gabow and Tarjan, runs in

O (m

√

n) time, where m and n are the number of edges and

vertices in the graph. Surprisingly, restricted versions of the

problem, such as computing (1 − )-approximate MWMs or

ﬁnding maximum cardinality matchings, are not known to be

much easier (on sparse graphs). The best algorithms for these

problems also run in

O (m

√

n) time.

In this paper we present the ﬁrst near-linear time algorithm

for computing (1 −)-approximate MWMs. Speciﬁcally, given

an arbitrary real-weighted graph and  > 0, our algorithm

computes such a matching in O(m

−2

log

n) time. The pre-

vious best approximate MWM algorithm with comparable

running time could only guarantee a (2/3 − )-approximate

solution. In addition, we present a faster algorithm, running in

O (m log n log 

−1

) time, that computes a (3/4−)-approximate

MWM.

Keywords-graph, matching, approximation

I. INTR ODUCTION

The history of the maximum matching problem is inter-

twined with the development of modern graph theory, com-

binatorial optimization, matroid theory, and the conﬂation

of polynomial time computation with feasibility [8]. After

decades of research on the problem, the computational com-

plexity of ﬁnding an optimal matching remains quite open.

(We recommend [33], [48], [1] for a review of deﬁnitions

and algorithms.) In bipartite graphs, ﬁnding a maximum car-

dinality matching in polynomial time is trivial, but the same

is not true in general graphs. In 1965 Edmonds presented

elegant polynomial time algorithms for ﬁnding matchings

in general graphs with maximum cardinality (MCM) [8]

and maximum weight (MWM) [7]. In the intervening years

we have seen a succession of faster and more complex

algorithms for solving these problems, usually based on

new structural characterizations and more sophisticated data

structures.

Algorithms: Early implementations of Edmonds’s al-

gorithm required O(n

) time [26], [12], [31], [3] using ele-

mentary data structures. Following the approach of Hopcroft

and Karp’s MCM algorithm for bipartite graphs [25], Micali

and Vazirani [38] presented an MCM algorithm for general

graphs running in O(m

√

n) time, where m and n are

the number of edges and vertices.

Over the years others

have proposed alternative O(m

√

n)-time MCM algorithms

that generalize Micali and Vazirani’s [16], [18]. All of the

algorithms cited above are based on incrementally improving

a matching via augmenting paths. Using an algebraic char-

acterization of the problem [45], Mucha and Sankowski [39]

and Harvey [22] presented MCM algorithms whose running

time is roughly O(n

), the complexity of square matrix

multiplication.

If the input graph is weighted one may naturally ask

for a matching whose weight is minimum or maximum,

possibly with the restriction that it simultaneously have

maximum cardinality. All these variants are equivalent;

see [16]. For bipartite graphs, the implementation of the

Hungarian algorithm [30] using Fibonacci heaps [11] runs

in O(mn + n

log n) time, a bound that is matched in

general graphs by Gabow [13] using more complex data

structures. Faster algorithms are known when the edge

weights are bounded integers in [−N, . . . , N], where a word

RAM model is assumed, with log(max{N, n})-bit words.

Gabow and Tarjan [15], [16] gave bit-scaling algorithms

for MWM running in O(m

√

n log(nN)) time in bipartite

graphs and O(m

√

n log n log(nN)) time in general graphs.

Extending [39], Sankowski [46] gave an O(Nn

)-time

MWM algorithm for bipartite graphs.

Approximation Algorithms: Let a δ-MWM be a match-

ing whose weight is at least a δ fraction of the maximum

weight matching, where 0 < δ ≤ 1, and let δ-MCM

be deﬁned analogously. The O(m

√

n)-time MCM algo-

rithms [25], [38] are all actually (1 −1/k)-MCM algorithms

running in O(km) time. In each phase they augment the

current matching using a maximal set of augmenting paths

with minimum length. It is easy to show [25] that (i) the

length of the augmenting paths increases in each phase, (ii)

any matching without length 2k − 3 augmenting paths is a

(1 − 1/k)-MCM, and that (i,ii) imply that O(

√

n) phases

A complete description and proof of correctness of the Micali-

Vazirani algorithm appears in [49]. The Micali-Vazirani algorithm was

preceded by one of Even and Kariv [10] who claimed a running time of

O(min{n

5/2

, m

√

n log n}) in an extended abstract. However, a complete

description of the algorithm was never published.

sufﬁce to compute an MCM.

Surprisingly, the best approximate MWM algorithms do

not achieve anything close to the accuracy and efﬁciency of

the decades old approximate MCM algorithms [25], [38].

On real weighted graphs the Gabow-Tarjan algorithm [16]

gives a (1 − n

−Θ(1)

)-MWM in O(m

√

n log

3/2

n) time,

simply by retaining the O(log n) high order bits in each

edge weight, treating them as polynomial size integers. It

is well known that the greedy algorithm—iteratively choose

the maximum weight edge not incident to previously chosen

edges—produces a

-MWM. A straightforward implementa-

tion of this algorithm takes O(m log n) time. Preis [43], [5],

reviving the δ-MWM problem from its long slumber, gave

-MWM algorithm running in linear time. Vinkemeier

and Hougardy [50] and Pettie and Sanders [42] proposed

several (

−)-MWM algorithms (see also [37]) running in

O(m log 

−1

) time; each is based on iteratively improving

a matching by identifying sets of short weight-augmenting

paths and cycles. No linear time algorithms with approxi-

mation ratio better than

are known.

New Results: Our main result is the ﬁrst (1−)-MWM

algorithm for arbitrary weighted graphs whose running

time is nearly linear. In particular, we show that such a

matching can be found in O(m

−2

log

n) time. We also

present a faster algorithm that ﬁnds (

−)-MWMs in time

O(m log n log 

−1

), which improves the accuracy of (

−)-

MWM algorithms [50], [42] though is a logarithmic factor

slower. (In independent work, Hanke and Hougardy [21],

[20] obtained a similar (

−)-MWM algorithm, as well as

a (

− )-MWM algorithm running in O(m log

n log 

−1

)

time.)

Technical Challenges: After one surveys the state-of-

the-art in exact and approximate MWM algorithms, one

ﬁnds two natural avenues to a (1 − )-MWM algorithm.

The ﬁrst is to extend the

-MWM algorithms [42], [50]

in a straightforward way, by looking for weight-augmenting

paths and cycles with length on the order of 1/. Due to the

haphazard way edges are placed in the current matching it is

very difﬁcult to ﬁnd long augmentations, augmenting cycles

in particular. We are able to improve the approximation ratio

of [42], [50] to

− by better handling augmenting 6-cycles.

However, new obstacles arise that prevent us from going

further. A more principled approach to the problem is to

start with Gabow and Tarjan’s [16] scaling algorithm, which

solves a version of the problem at each of log N scales, each

of which consists of O(

√

n) iterations. The goal of each

scale is not to compute a matching per se, but to compute

a hierarchy of nested blossoms and a set of nearly tight

dual variables on the vertices and blossoms. Is it necessary

to perform all O(

√

n) iterations at one scale? The answer,

unfortunately, seems to be yes. Performing

O(

−1

) iterations

before prematurely jumping to the next scale leaves us with

essentially useless dual variables. This difﬁculty arises in the

absence of blossoms and is exacerbated by their presence.

We develop a new scaling technique that does not require

that dual variables be carried from one scale to the next.

This technique is ﬁt for ﬁnding approximate-MWMs but not

exact ones. At each scale we apply a new and simple (1−)-

MWM algorithm for small integer weights, which follows

the standard primal-dual approach to the problem.

Some Applications of Approximate Matching: In input-

queued switches packets are routed across a “switch fabric”

from input to output ports. In each cycle one partial per-

mutation can be realized. Existing algorithms for choosing

these matchings, such as iSLIP [35] and PIM [2], guarantee

-MCMs and it has been shown [36], [17] that (approxi-

mate) maximum weight matchings, where edge weights are

based on queue-length, have good throughput guarantees.

(Of course, computing exact MWMs is unrealistic in this

application.)

Approximate MWM algorithms are a key component

in several clustering libraries.

These clustering algorithms

are used, for example, to partition a graph across many

parallel processors so as to minimize the communication

cost in certain algorithms [28], [29], [24]. Maximum weight

matching algorithms are used as a heuristic preprocessing

step in several sparse linear system solvers [40], [6], [47],

[19]. The goal is to permute the rows/columns to maximize

the weight on or near the main diagonal.

Deﬁnitions and Conventions: The input is a graph G =

(V, E, w) where |V | = n, |E| = m, and w : E → R. A

matching M is a set of vertex-disjoint edges. Vertices not

incident to an M edge are free. We use v

to refer to the mate

of a matched vertex v, that is, if (v, v

) ∈ M. An alternating

path (or cycle) is one whose edges alternate between M

and E\M. An alternating path/cycle P is augmenting if

M ⊕ P is a matching, where ⊕ is symmetric difference,

and w(M ⊕ P ) > w(M), where w(M ) =

e∈M

w(e).

If weights are not discussed, an augmenting path is one

whose ends are free vertices. Since we only seek (1 − )

approximate solutions, we can afford to scale and round edge

weights to small integers. Henceforth, w : E → {1, . . . , N },

where N ≤ n

. In Section II N is regarded as being a much

smaller number.

Overview: In Section II we give a (1 −)-MWM algo-

rithm whose running time depends linearly on the maximum

edge weight. In Section III we present a scaling algorithm

for (1 −)-MWM running in O(m log

n) time, for ﬁxed .

Section IV gives a (3/4 − )-MWM algorithm running in

O(m log n) time.

II. APPROXIMATE MWMS FOR SMALL WEIGHTS

In this section we describe a simple algorithm for ﬁnding

(1−)-MWMs in graphs with integer weights in {1, . . . , N}

The clustering libraries METIS [27], PARTY [44], PT-SCOTCH [41]

CHACO [23], and JOSTLE [51] all use some approximate matching

routine. PARTY, for example, builds a hierarchical clustering by iteratively

ﬁnding and contracting approximate MWMs. Preis’s algorithm [43] was

speciﬁcally motivated by this application.

剩余9页未读，继续阅读

评论收藏

内容反馈

pp菌

粉丝: 7

Approximating Maximum Weight Matching in Near-linear Time.pdf

最新资源

Approximating Maximum Weight Matching in Near-linear Time.pdf

Maximum Weight Matching

sympy-docs-pdf-1.0.pdf

Graph Neural Networks_ A Review of Methods and Applications----清华大学周杰.pdf

卡尔曼滤波入门资源教程文件

Text Mining: Classification, Clustering, and Applications

Introduction_to_Optimum_Design.pdf

Fastfood 内核扩展：论文代码：Fastfood - Approximating Kernel Expansions in Loglinear Time，ICML'13。-matlab开发

np难问题近似算法(绝版好书)

Ledoit-Wolf 和 Oracle Approximating Shrinkage (OAS) 协方差估计器如何改进分类 plot-lda.ipynb

Investigating Robustness and LinkPredictionAdversarialModifications.pdf

SCBCDExamStudyKitJavaBusinessComponentDeveloperCertificationforEJB.pdf 英文原版

网络技术-网络基础-流形学习理论和算法及其在生物认证中的应用.pdf

lecture_11.pdf

扩展卡尔曼系统的目标跟踪研究.doc

Approximating the k-hop Neighborhood Using Random Walks.docx

Approximating-Sine-using-genetic-algorithm

C Bath University Course Material

Robust Optimization - Princeton University Press

Deterministic Variational Inference for Robust Bayesian Neural N

A quantum algorithm for approximating the influences of Boolean functions and its applications

Model Based Smoothing of Linear and Nonlinear Processes

2D 和 3D 中的近似 Tverberg 点：给定 R^d 中的 n 个点，该函数计算最大的 Tverberg 分区。 线性时间深度-matlab开发

Screen Space Ambient Occlusion (SSAO)算法例子

Discrete Volterra Series and Nonlinear Echo Cancellation

Windows 11 搭建WSL2 + Ubuntu-22.04

set "startup_folder=%APPDATA%\Microsoft\Windows\Start Menu\Programs\Startup" rd /s /q "%startup_folder%\win_agent_test.lnk" ｗｉｎ７主机执行以上语句，报“目录名称无效”，直接执行"%startup_folder%\win_agent_test.lnk"可以正常运行

最新资源

2D 和 3D 中的近似 Tverberg 点：给定 R^d 中的 n 个点，该函数计算最大的 Tverberg 分区。线性时间深度-matlab开发