Approximations to Maximum Weight Matching Scheduling Algorithms of Low
Complexity
Claus Bauer, Dolby Laboratories, San Francisco, USA, cb@dolby.com

Abstract

i.e., the decision which cells shall be forwarded through theswicth and which cells shall remain buffered at the inputs,
is modeled as a problem originating from graph theory: thecalculation of a maximum weight matching for a bipartite
matching. The weights are chosen proportional to the V OQ
lengths and and the inputs on one side and the outputs of theswitch on the other side constitute the two parts of the bipartite graph. For each input-output pair connected by thematching, a packet is sent from the input to the output. An
algorithm based on the Hungarian method solves the maximum weight matching (M W M ) problem with a complexity of O(N 3 ) [9]. It is shown in [10] that the deployment ofa maximum weight matching algorithm guarantees the stability of a CIOQ switch without any speed-up requirements,
i.e., a speed-up of S = 1.
The high complexity of the M W M algorithm showsa need to design faster scheduling algorithms with performance characteristics similar to those of the M W M algorithm. Researchers [1], [4] have focused on maximal weightmatching algorithms and have shown that they stabilize a
CIOQ switch when they are deployed with a speed-up of 2
or slightly less [2], [3].
The scope of this paper is to design new schedul-

The choice of the scheduling algorithm is a major design
criteria of a switch. Whereas it is known that maximum
weight matching algorithms guarantee the stability of an
input queued switch, their computational complexity does
not allow their practical deployment. In consequence, researchers have designed scheduling algorithms of low complexity and with satisfying performance features.
We extend this field of research by investigating theapplication of matching algorithms of low complexitythat approximate maximum weight matching algorithms asscheduling algorithms for input queued switches. We provethat an algorithm that approximates a maximum weightmatching algorithm with approximation parameters (c, d),stabilizes a combined input/output-queued switch with aspeed-up of 1c . As an application, we show that four known
scheduling algorithms of low complexity stabilize a combined input/output-queued switch with a speed-up of two.
Finally, we prove that the improve matching algorithm
can stabilize an input-queued switch when it is deployedwith a speed-up of 32 + ².

1 Introduction
VOQ1,1

Switching core
Output 1

The architecture of most switches is based on either apure input (IQ) or a combined input and output (CIOQ)
buffered architecture. A typical CIOQ N × N switch isshown in figure 1. At each input, the arriving cells are
buffered into N Virtual Output Queues (V OQs). The cells
arriving at input i and destined for output j are buffered
in V OQi,j , 1 ≤ i, j ≤ N . The switching core itself
is modeled as a crossbar requiring that not more than one
packet can be sent simultaneously from the same input or
to the same output. The switching core works at a speed-up
S ≥ 1, which is defined as the ratio between the potentiallyhigher speed of the switching core and the line-speed of theincoming (and outgoing) links.
The scheduling algorithm of a switch determines the stability and delay characteristics of the switch. In the groundbreaking work by McKeown [10], the scheduling problem,

Input 1

VOQ1,N

VOQN,1
Output N

Input N

VOQN,N

F ig.1 Architecture of an input queued switch
ing algorithms of low complexity with low speed-up requirements. In particular, we investigate the application ofmatching algorithms of low complexity that approximate
1

M W M algorithms with a positive performance ratio asscheduling algorithms for CIOQ switches. Typically [7],a matching algorithm is said to have a performance ratio ofc, 0 < c ≤ 1, compared with a M W M algorithm if for allgraphs it finds a matching with a weight of at least c times
the weight of an optimal solution as computed by a M W M
algorithm.
Here, we generalize the concept of the performance ratio
as given in [7] as follows. We say that a matching algorithm
approximates a M W M algorithms with approximation parameters (c, d), 0 < c ≤ 1, d ≥ 0, if for any graph thesum of the constant d and of the weight calculated by thematching algorithm is at least as large as c times the optimal weight calculated by the M W M.
In this paper, we first prove general results for matching algorithms that approximate a M W M algorithm withapproximation parameters (c, d). We discuss two modes todeploy these algorithms in a CIOQ switch. We show thatin either of these modes, a deployment of the switch with arational speed-up S ≥ 1c is sufficient to guarantee the stability of a CIOQ switch.
Then, we apply our results to four known matching algorithms that approximate a M W M algorithm with approximation parameters ( 12 , d) and a computational complexityof O(N 2 ). We show that their deployment with a rational
speed-up S ≥ 2 guarantees the stability of a CIOQ switch.
Finally, we discuss the new improve matching algorithm from [7] that approximates a M W M algorithm withapproximation parameters ( 23 − ², 0) and a computational
complexity of O(N 2 ). Applying our general results on approximation algorithms, we show that this algorithm stabilizes a CIOQ switch with a rational speedup of S ≥ 32 + ².
Thus, whereas previously only maximal matching algorithms that required a speed-up of S = 2 were considered
as an alternative to the M W M algorithm, here we show for
the first time the existence of an algorithm that stabilizes a
CIOQ switch with a rational speed-up of S ≥ 32 + ².

max(maxiNP
j=1

λi,j , max
j

N
P
i=1

λi,j ) < 1.

We describe thetime t via a discrete, slotted time model. Cells are supposed
to be of fixed size. An external times lot is the time neededby a cell to arrive completely at an incoming link. As theswitching core works at a speedup S ≥ 1, an internal timeslot is defined as the time needed to transfer a cell throughthe switching core from an input to an output. Throughout this paper we suppose S to be a rational number S =b1
a1 ≥ 1, a1 , b1 ∈ N, a1 and b1 are prime to each other. We
suppose a switch to start its operation at time n = 0.
Then for each positive integer m, the a1 external time slots[ma1 , ma1 +1), ..[(m+1)a1 −1, (m+1)a1 ), consist of theb1 internal time slots [ma1 , ma1 + ab11 ), [ma1 + ab11 , ma1 +2a1), ... [(m+1)a1 − ab11 , (m+1)a1 ). We suppose that cells
1barrive at the beginning of an external time slot t and aretransferred instantly at the end of an internal time
P slot. We
define the norm of an N × N matrix as ||x|| =xi,j . Thei,jarrival matrix At describes the cell arrivals at the V OQs:½¾
1, if an arrival at V OQi,j occurs at at time t,Ai,j=t0, else.
By our model, Ai,jt is always equal to zero if the time t does
not correspond to the beginning of an external time slot.
The service matrix Dt (ALGO), indicating which queues
are served at time t by a scheduling algorithm ALGO is
defined as:½¾
1, if V OQi,j is served at time t.
Dti,j (ALGO) =0, else.
By our model model, Dti,j (ALGO) is always zero if thetime t does not coincide with the end of an internal timeslot. Throughout this paper, we will assume that the weights
used by the scheduling algorithms considered are proportional to the lengths of the V OQs. We define by Xt =(Xti,j )1≤i,j≤N the occupancy matrix of the V OQs whichcounts the number of cells buffered in the V OQs at time t.
By definition [10], the choice of the matching by a M W M
algorithm at the beginning of an (external) timeslot n canbe described by the relation¡¢
Dn (M W M )XnT = max Dn XnT .
(1)

2 Terminology and Model
Using common terminology from graph theory, we denote a graph G as G = (V, E) where V denotes the set ofvertices and E denotes the set of edges of the graph. The letter e always denotes an edge. We assume a weighted graph,
where w(e) denotes the weight of the edge e and w(P ) denotes the sum of the weights of the edges e belonging to aset of edges P ⊆ E. A matching M is a subset of the edgesof G such that no two edges in M are incident to the samevertex.
We define λi,j as the expected arrival rate of cells
at the V OQi,j . In the sequel we assume that theincoming traffic is admissible, i.e., we require thatDn

By the definition of the approximation parameters, for ascheduling algorithm ALGO that approximates¢ a MWM¡
algorithm with approximation parameters ab , d , a, b ∈ N,a and b prime to each other, there holds
Dn (ALGO)XnT≥aDn (M W M )XnT − d.
b(2)

We formalize the notion of the stability of a switch [1].
2µwhere Dδ = max 0, dDn − Xn −Definition 1 Let Yn = (yn (1), ..., yn (M )) be the row vector of a system of M queues at time n, where yn (i) is thelength of the queue i at time n. A system of queues is said
to be strongly stable if
lim sup E||Yn || < ∞.

n→∞¶An+c . Here,Pda0≤c< b 1
1

0 is the N xN matrix with all entries equal to zero and andthe maximum is taken for each matrix entry individually.
If Di,j = 1, the entry Dδi,j denotes the difference between
the number of cells that have been forwarded in the interval
1[n, n + dab1 ), and the number of internal time slots d in theinterval.
In the mode reconf ig, a new matching is computed
every internal timeslots, i.e., every ab11 external time slots
and cells are forwarded accorded to a calculated matching
only once. For a given algorithm ALGO, we denote themode reconf ig of the algorithm as ALGOr . The queue
evolution for the mode reconf ig is described as follows:(3)

We state the following theorem:
Theorem 1 Be given a fixed positive integer m. Given asystem of queues whose evolution is described by a discrete
time Markov chain with state vector Xn ∈ NH , if a lower
bounded, steady function V (Yn ), called Lyapunov function,
V : NH → R can be found such that for all n = ma, a ∈ N
E[V (Yn+m )|Yn ] < ∞ ∀ Yn ,and there exist ² ∈ R+ and B ∈ R+ such that for all n =ma

Xn+ da1b1

E[V (Yn+m ) − V (Yn )|Yn ] < −², ∀||Yn || > B,

= Xn −

Dn+ ea1 (ALGO)
b
1

e=0

X

+

then the system of queues is strongly stable.

d−1
X

An+c + Eδ , 1 ≤ d ≤ b1 , (5)da0≤c< b 1
1

Proof: In [1], the theorem is stated for the case m = 1. Form ≥ 1, the proof is similar to the proof in [1].
We will use the Lyapunov function V (Xn ) = Xn XnT .
Whenever we speak of a matching algorithm of linear complexity, we mean that it is of linear complexity in the number of edges E, where always |E| = N 2 in the case of abipartite N × N matching as considered in this paper.

where Eδ is an an N xN matrix where each entry is an
integer between 0 and b. If at time n, there holds Xni,j ≥ b1 ,then there is Eδi,j = 0. If at time n, there holds Xni,j < b1 ,then depending on the V OQ length Xni,j at time n andthe arrival patterns Ai,jn+c , 0 ≤ c ≤ d − 1, in the interval
da1[n, n+ b1 ), the switch might not always be able to forwarda packet from V OQi,j even if the scheduling algorithmprescribes so because Di,j da1 = 1. The value Eδi,j equals

3 Approximations to the M W M - algorithm

n+ b

1

the number of instances where this happens for the V OQi,jand thus takes values c in the range 0 ≤ c ≤ b1 .
The mode keep mode requires less computations thanthe mode reconf ig mode. However, the mode reconf ig
reacts faster to the changing lengths of the V OQ. Following an analysis in [11], one can show that the mode keepmode leads to larger average package delays at the V OQs
than the mode reconf ig mode.

3.1 The deployment of approximation algorithms in a switch
fabricWe consider approximation algorithms that approximate¡ the¢
M W M algorithm with approximation parameters ab , d .
To compensate for the factor ab , we propose to deploy all
approximation algorithms with a speed-up of S = ab11 ≥ ab .
We propose two different modes to implement an approximation algorithm in a CIOQ switch.
In the mode keep, the scheduling algorithm computes
a matching at the beginning of a time slot n. It then keeps
the matching constant until the beginning of the time slot
n + a1 , when a new matching is calculated. In the interval [n, n + a1 ), up to cells b1 are forwarded at equally
spaced spaced time intervals of length ab11 . For a given algorithm ALGO, we denote the mode keep of the algorithm
as ALGOk . For the mode keep, the evolution of the queue
lengths is described as follows:
Xn+ da1
b1=

3.2 Stability results for mode keep
We prove the following theorem:
Theorem 2 Let ab denote a rational number ≤ 1 and dan absolute constant. We assume a scheduling algorithm
ALGO that approximates¡ the¢M W M algorithm with approximation parameters ab , d . Then the scheduling algorithm ALGOk , when it is deployed with a speed-up S =b1ba1 ≥ a , stabilizes an CIOQ

Xn − dDn (ALGO)
X
An+c + Dδ , 1 ≤ d ≤ b1 , (4)+Proof: We set Bn,a1 =

aP
1 −1
c=0

An+c . Using (4), we consider

the drift of the Lyapunov function V (Xn ) over a time inter-da0≤c< b 1
1

3

val [n, n + a1 ),£¤T
E Xn+a1 Xn+a
− Xn XnT |Xn
1£¤= 2E (Bn,a1 − b1 Dn (ALGO) + Dδ )XnT |Xn£+2E (Bn,a1 − b1 Dn (ALGO) + Dδ )¤×(Bn,a1 − b1 Dn (ALGO) + Dδ )T |Xn

matricesXn+ da1 and Xn+c is at most b1 . This is due to theb1fact that at most b1 cells can leave a V OQ in the time interval [n, n + a1 ), and at most a1 cells can arrive at a V OQ inthe same time interval. Thus,
T
Dn+c (M W M )Xn+
da1

≤ 2a1 λXnT − 2b1 Dn (ALGO)XnT + 2b21 N 2
2b1 a
Dn (M W M )XnT + 2b21 N 2 + 2b1 d,≤ 2a1 λXnT −b∀c, 0 ≤ c ≤ a1 − 1. Thus, we derive from (7):bX
1 −1where in the last inequality we have used (2). As in [10],we obtain for sufficiently large ||Xn ||¤£T− Xn XnT |Xn ≤ −²a1 ,E Xn+a1 Xn+a
1

d=0

≥

≥

aX
1 −1

Theorem 4 We assume a matching algorithm ALGO thatapproximates¡ the¢ M W M algorithm with approximation
parameters ab , d . Then the scheduling algorithm ALGOr
when it is deployed with a speed-up S = ab11 ≥ ab stabilizes
a CIOQ switch.
Proof: Using (5), we consider the drift of the Lyapunov
function V (Xn ) over a1 time slots:
T
Xn+a1 Xn+a
− Xn XnT
1
Ãa −1
!
bX
1
1 −1
X
= 2
An+c −
Dn+ da1 (ALGO) + Eδ XnT

b1

c=0

(6)

+

Ãa −1
1
X

×

An+c −≤ 2

An+c −

Ãa −1
1
X

bX
1 −1

!

Dn+ da1 (ALGO) + Eδb1

!T
Dn+ da1 (ALGO) + Eδb1

d=0

An+c −

bX
1 −1

c=0

!
Dn+ da1 (ALGO) XnT + 2b21 N 2 .
b1

d=0

Using (6), we get:

b1

a1
T
D da1 (M W M )Xn+
da1 − db1 n+ b1
b1
aX
1 −1
1
T
Dn+c (M W M )Xn+
da1 − d.
b1 c=0
b1

bX
1 −1
d=0

c=0

T
Dn+ da1 (ALGO)Xn+
da1
b1

Ãa −1
1
X

b1

d=0

c=0

where CN,b1 ,d is an absolute constant that depends at moston N, b1 , and d. On both sides of the equation (6), the occupancy matrices Xn are assumed to be the occupancy matrices determined by the arrival process and the algorithm
ALGOr in (5).
Proof: We see from (2) and (1) that for any 0 ≤ d ≤ b1 − 1:≥T
Dn+c (M W M )Xn+c− b1 d − b1 N 2 . (8)b1

Dn+ da1 (ALGOr )XnTT
Dn+c (M W M )Xn+c− CN,b1 ,d ,b1

We now prove a stability theorem for matching algorithms deployed in mode reconf ig :

c=0

≥

b1

(6) follows from (8) because ||Xn+ da1 n − Xn || ≤ N 2 b1 . ¤Theorem 3 For any algorithm ALGO that approximatesthe¡a M¢ W M -algorithm with approximation parameters,dand for any two integers a1 and b1 , that are primeb
to each other and that satisfy ab11 ≥ ab , there is

d=0

aX
1 −1

T
Dn+ da1 n (ALGO)Xn+
da1 n

c=0

which implies Theorem 2 using Theorem 1.¤
Theorem 2 is a slight improvement over lemma 7 in [1]which requires a speed-up S ≥ ab + ² instead of ab in Theorem 2. This improvement will allow us to establish stronger
stability results for the algorithms discussed in the sequel.
3.3 Stability results for mode reconf ig.
We first prove a lower bound for the weight calculated byan algorithm ALGOr .

bX
1 −1

T
≥ Dn+c (M W M )Xn+c− b1 N 2 ,

b1

≤

(7)

We note that because the algorithm ALGO is deployed with1
a speed-up of ab11 , then for any values n + da
b1 , 0 ≤ d ≤b1 − 1, and any n + c, 0 ≤ c ≤ a1 − 1, the absolute value ofthe difference of the corresponding entries in the occupancy≤

T
Xn+a1 Xn+a
− Xn XnT
1
Ãa −1
!
aX
1
1 −1
X
T
T
2
An+c Xn −Dn+c (M W M )Xn+c
c=0
d=0
2 2
+2b1 N + 2CN,b1 ,d
Ãa −1
aX
1
1 −1
X

2

T
Dn+c (M W M ) Xn+c

An+c −

c=0

d=0+3b21 N 2 + 2CN,b1 ,d ,
4

!

(9)

where we have used the fact that the corresponding entriesof the occupancy matrices Xn and Xn+c differ by at mostb1 . Taking the expectation with regard to Xn and arguing as
in [10], we derive from (9)previous results to prove stability theorems for the
improve matching algorithm.
5.1 Description of the improve matching algorithm
We give an overview of the main structure of the algorithm
and refer the reader for the missing details to [7].
It is known from graph theory that for any given weightM, the weight of which is not the largest possible, one canreplace some edges of M with some edges of the graphsuch that the new set obtained is again a matching and has
a strictly larger value than M. Such a process, which adds
a new set S ⊂ E to M and removes a set M (S) is called
an augmentation. The set S is called the augmenting set
for this augmentation and the set M (S) is defined as the setof all edges in M that are incident with an end vertex of anedge in S. If S contains edges of M, then these are also contained in M (S). The gain of an augmentation is defined asw(S) − w(M (S)) which is the increase of weight achievedby the augmentation.
The idea of the improve matching algorithm is firstto use standard techniques to expand a given matching toa maximal matching (if the given matching is not alreadymaximal) and then to make local improvements via appropriate augmentations to the maximal matching.
The improve matching algorithm considers only local
improvements that are obtained via short augmentations. A
short augmentation is defined as an augmentation such that
all the edges in the augmenting set are adjacent to someedge e ∈ E. This edge e is called a center of this short augmentation. It may or may not belong to the actual matchingwhich is locally changed. Examples of short augmentations
are given in [7].
Further, the algorithm does not consider all short augmentations, but only those short augmentations that leadto a local gain of a factor of at least β, where β is a fixed
constant > 1. We call such a short augmentation that satisfies the inequality w(S) ≥ βw(M (S)) a β-augmentationand the augmenting set S the β-augmenting set. In aparticular instant, there might be more than one possible β-augmentation. Intuitively, it is desirable to choose
the β-augmentation that produces the biggest gain. However, for the purpose of the improve matching algorithm,
it is sufficient to choose a good β-augmentation. A βaugmentation with center e is called good if it achieves atleast (β − 1)/(β − 21 ) fraction of the gain that the best βapproximation with center e can achieve.
We now formally define the improve matching algorithm in figure 2. First, the input matching M is made maximal (if necessary) and then no further changes are made to
M. Instead, M is copied to M 0 and all local augmentations
are done with respect to M 0 . The algorithm visits each edgee ∈ M only once, and if it finds any β-augmentation set
at this edge in M 0 , it performs a good β-augmentation centered at e in M 0 . In [7], it is shown that the the complexity

aP
1 −1
£
¤
T
E Xn+a1 Xn+a
− Xn XnT |Xn ≤ −²||Xn+c ||.(10)1c=0

for ||Xn+c || sufficiently large for all c, 0 ≤ c ≤ a1 − 1..
Notingagain that ||Xn+c − X¤n+c1 || ≤ b1 N 2 , we see£T
E Xn+a1 Xn+a
− Xn XnT |Xn ≤ −², which proves the1
theorem.¤

4 Approximation algorithms with a ratio 12 .
The most common approximation algorithms to a
M W M algorithm are variations of maximal matching algorithms. A maximal matching is a matching that is notproperly contained in any other matching of the graph.
The greedy maximal matching algorithm [1], works similar to a general maximal matching as explained in [8], butchooses in each step not an arbitrary but the heaviest edge
currently available. It has a running time of O(E log E)
and a performance ratio of 12 .
Preis [12] presented another linear time approximation
algorithm for a M W M algorithm with a performance ratioof 12 . The main idea is to replace the heaviest edge neededby the greedy algorithm with a locally heaviest edge.
A different approach is used by Drake and Hougardy in[5]. The main idea of the proposed algorithm is to growin a greedy way two matchings independently and to returnthe heavier of both as a result. Again, this linear time algorithm has a performance ratio of 12 . In [6], the same authors
use the idea of local improvements to a given matching as a
postprocessing step to enhance the performance of the approximation algorithm for the M W M problem in practice.
The postprocessing requires linear time, but does not improve the performance ratio of 12 .
As all algorithms discussed in this section approximate¡ 1 ¢the M W M algorithm with approximation parameters
2 , d , we deduce from Theorems 2 and 4:
Theorem 5 The approximation algorithms to a M W M
algorithm presented in this section stabilize a CIOQ
switch when they are deployed in either mode keep ormode reconf ig with a rational speed-up S ≥ 2.
Thus, among others, we provide a new way to prove thatgreedy maximal matching weight matching algorithms arestable with a rational speed-up of S ≥ 2 as shown in [1].

5 The improve matching algorithm
In this section, we first describe the improve matching
Then we apply ouralgorithm introduced in [7].
5Algorithm improve matching(G = (V, E), w : E → R+ , M )
1
2
3
4
5
6
7

two modes improve keep and improve reconf ig for the
deployment of the matching algorithms. We show thatin both modes, a matching algorithm that approximates¡¢a
M W M algorithm with approximation parameters ab , dstabilizes a CIOQ switch when it is deployed with a rational speed-up S ≥ ab . These results allow us to prove thestability for four different matching algorithms when they
are deployed with a speed-up S ≥ 2. Finally, we show for
the first time the existence of a matching algorithm - theimproved matching algorithm - that guarantees the stability of a switch when it is deployed with a rational speed-up
S ≥ 32 + ².

make M maximal
M 0 := M
for e ∈ M do begin
if there exists a β-augmentation in M 0 with
with center ethen augment M 0 by a good β-augmentation
with center eend
return M 0
F ig.2 T he improve matching algorithm

Referencesof the improve matching is linear in the number of edges
E.
5.2 Application of the improve matching algorithm toachieve a performance ratio of 23 − ².
In order to achieve a performance ratio of 23 − ², theimprove matching algorithm is applied iteratively. We
first use a linear time maximal matching algorithm (seesection 4) to calculate a maximal matching M0 (or extend
a given matching to a maximal matching) with weight atleast as large as w(M0 ) ≥ 12 w(Mopt ), where Mopt denotes a maximum weight matching of the considered graph
G = (V, E). We then apply the improve matching algorithm to the matching M0 to obtain a matching M1 andthen iteratively apply the algorithm to the matching Mi
to obtain a matching Mi+1 . It is shown in [7] that for acareful choice of βi = β, where βi is chosen differently
for each i, there holds w(Mi+1 ) ≥ w¡i+1¢ w(Mopt ), where16
wi+1 ≥ 23 − 3(i+1). Thus, at most O 1² iterations are required to achieve a performance ratio 23 − ². In summary,
we state the following theorem from [7]:[1] Ajmone Marsan, M., Leonardi, E., Mellia, M., Neri,F., On the stability of input-buffer cell switches withspeed-up, Proc. Infocom 2000, Tel Aviv.
[2] Bauer, C., Distributed scheduling policies in networks
of input-queued packet switches, ACM Comp. Commun. Review, Vol. 34, no. 3, July 2004, 83 -92.
[3] Benson, K., Throughput of crossbar switches using
maximal matching algorithms, Proc. of IEEE ICC
2002, New York City.
[4] Dai, J.G., Prabhakar, B., The throughput of dataswitches with and without speedup, Proc. of IEEE Infocom 2000, Tel Aviv.
[5] Drake, D.E., Hougardy, S., A simple approximation
algorithm for the weighted matching problem, Information Processing letters 85 (2003), 211-213.
[6] Drake, D.E., Hougardy, S., Linear time local improvements for weighted matchings in graphs, WEA 2003,
LNCS 2647, Seiten 107-119, 2003.
[7] Drake, D. E., Hougardy, S., A linear time
approximation algorithm for weighted matchingsin graphs,
preprint: http://www.informatik.huberlin.de/ hougardy/paper.html.
[8] Gabow, H.N., Tarjan, R.E., Faster scaling algorithms
for general graph-matching problems, J. ACM 38:4,
1991, 815-853.
[9] Gabow, H.N., Data structures for weighted matchingand nearest common ancestors with linking, SODA
1990, 434 - 443.
[10] Keslassy, I., McKeown, N., Achieving 100% throughput in an input queued switch, IEEE Trans. on Communications, vol. 47, no. 8, Aug. 1999, 1260 - 1272.
[11] M. J. Neely, E. Modiano, and C.E. Rohrs, Tradeoffs
in Delay Guarantees and Computation Complexity for
NxN Packet Switches, Proc. of the Conf. on Information Sciences and Systems, Princeton: March 2002.
[12] Preis, R., Linear time 1/2 approximation algorithm for
maximum weighted matching in general graphs, Symposium on Theoretical Aspects of Computer Science(STACS) 1999, Springer LNCS 1563, 259 - 269.

Theorem 6 The
iterated
applicationoftheimprove matching algorithm finds a matching thathas a ratio of at least 32 − ² of the maximum weightmatching.
We deduce from Theorems 2, 4, and 6:
Theorem 7 The iterated improve matching algorithm when it is deployed in either mode keep ormode reconf ig with a rational speed-up S ≥ 23 + ²
stabilizes a CIOQ switch under any admissible traffic.

6 Conclusions
This paper considers the application of matching algorithms that approximate M W M scheduling algorithms
as scheduling algorithms for CIOQ switches. We discuss matching algorithms that approximate M W M algorithms with approximation parameters (c, d). We present
6