>>> Complexity Seminar のお知らせ <<< 

題目： Fast Parallel Approximation Algorithms for Maximum Weight
       Matching Problem

発表者： 上原隆平（駒澤大学）

日時：１９９９年１１月１７日（水）４時〜
場所：電気通信大学西９号館３階ＡＶホール

内容：

Abstract:

We present four parallel approximation algorithms for finding a
maximum weight matching in a given edge-weighted graph.

The first algorithm deterministically runs in $O(\log n)$ time.
Its approximation ratio is $\frac{1}{3(Δ-1)}$, where $Δ$
is the maximum degree of the graph. 
This algorithm requires only operation to compare with each weight of
edge. Hence the algorithm only requires to know the total ordering of
the weights. 

The second algorithm is randomized
$\frac{1}{4(Δ-1)}$-approximation algorithm using only the
comparison operation. It runs in $O(\logΔ)$ time, not depending
on the size of the graph. Hence the algorithm can be performed on 
a large scale distributed system.

The third algorithm is $\frac{1}{2(Δ-1)}$-approximation algorithm
that runs deterministically in $O(\log n)$ time.
It requires the comparison and addition operations of weights.

The fourth algorithm is $\frac{1}{2(Δ-1)}$-approximation
algorithm that runs deterministically in $O(\log^2 n)$ time,
and that requires the comparison and addition operations of weights.
The approximation ratio of the last algorithm converges to about
$\frac{1}{Δ-1}$ under some restricted case.